Python如何用邻接矩阵实现图广度优先和深度优先搜索？

本文共计6146个文字，预计阅读时间需要25分钟。

图是一种抽象的数据结构，本质和树结构相同。与树相比，图具有封闭性，可以将树结构看作是图结构的一种前身。在树结构中，如果将兄弟节点之间或子节点之间的横向连接视为边，则便于构建图。

图是一种抽象数据结构，本质和树结构是一样的。

图与树相比较，图具有封闭性，可以把树结构看成是图结构的前生。在树结构中，如果把兄弟节点之间或子节点之间横向连接，便构建成一个图。

树适合描述从上向下的一对多的数据结构，如公司的组织结构。

图适合描述更复杂的多对多数据结构，如复杂的群体社交关系。

1. 图理论

借助计算机解决现实世界中的问题时，除了要存储现实世界中的信息，还需要正确地描述信息之间的关系。

如在开发地图程序时，需要在计算机中正确模拟出城市与城市、或城市中各道路之间的关系图。在此基础上，才有可能通过算法计算出从一个城市到另一个城市、或从指定起点到目标点间的最佳路径。

类似的还有航班路线图、火车线路图、社交交系图。

图结构能很好的对现实世界中如上这些信息之间的复杂关系进行映射。以此可使用算法方便的计算出如航班线路中的最短路径、如火车线路中的最佳中转方案，如社交圈中谁与谁关系最好、婚姻网中谁与谁最般配……

1.1 图的概念

顶点：顶点也称为节点，可认为图就是顶点组成的集合。顶点本身是有数据含义的，所以顶点都会带有附加信息，称作"有效载荷"。

顶点可以是现实世界中的城市、地名、站名、人……

边： 图中的边用来描述顶点之间的关系。