有向图与无向图
数据结构中的图(Graph)是对数学分支图论(Graph Theory)中的图的表示，通常用二元组\(G=(V,E)\)定义图\(G\)，其中\(V\)是顶点的集合(顶点集)，\(E\)是边的集合(边集)。边集的元素也是二元组\((x,y)\)且\(x,y\)是\(V\)的元素，由于二元组包含\(x,y\)的序，若不关心\(x,y\)的序或用集合\(\{x,y\}\)表示边，则\(G\)是无向图，否则是有向图。一般按上图的方式“画”有向图和无向图。
直观上图是对前面讨论过的树的推广，树不允许树边任意的加在两节点间，图边则没有这些限制，并且图中一般不会指定“树根”这样的顶点。所以图相比树会有更多更复杂的“边界情况”，给出与之相关的概念：
1) 重边：即重复的边。设\(u,v\)是图顶点，对于有向图，若存在2个以上的从\(u\)到\(v\)的边，则称从\(u\)到\(v\)有重边。对于无向图，若存在2个以上连接\(u\)和\(v\)的边，则称\(u\)与\(v\)间有重边。也就是边集中有“相同”的二元组；
2) 自环：即连向自己的边。设\(u\)是图顶点，对于有向图或无向图，若存在边\((u,u)\)，则称该边是自环。自环还能重复；
3) 路径：设\(u,v\)是图顶点，对于有向图或无向图，若通过1个由边组成的序列可达\(v\)，该序列就是\(u\)到\(v\)的其中1个路径，对于有向图这些边的“方向”必须是正确的。如果路径中的每个顶点都仅到达一次，则该路径为简单路径；
4) 环：起点和终点是同一顶点的路径，也称为圈、回路、环路。自环也是环的一种；
5) 度：对于无向图，顶点的度数是其所在的边的总数目，注意自环要当成2个边计数。对于有向图，则没有度但有出度和入度，前者指顶点发出的边数，后者指到达顶点的边数，注意自环会让出度和入度都+1；
对于所有涉及到图结构和图算法的文章，默认图是不允许出现重边和自环的。
图的表示与实现
图结构是较复杂的，但图的形式化定义是二元组，借用形式化定义可得到较简洁的物理实现：
1) 邻接矩阵：对于含N个顶点的图，可构造N*N矩阵A进行描述。由于有向图任意两顶点间至多有2条边，故对于有向图可用\(A_{ij}\)表示顶点i连向顶点j的边，\(A_{ij}\)的值刚好可表示权重(无权时用1/0表示有边/无边)。在处理无向图时通常用\(A_{ij}=A_{ji}\)的方式记录无向边。
2) 邻接表：邻接表是图的更一般化的表示方案，邻接表的KEY代表一个顶点，KEY对应的VALUE为记录这个顶点的所有邻接顶点。比如对于有向图的邻接表\(L\)，\(L[u]=[a,b,c]\)表示\(u\)顶点发出3条边分别指向\(a,b,c\)。对于无向图通常的处理方法是如果\(a\)在\(L[u]\)中那么就让\(u\)在\(L[a]\)中。对于有权图可通过继续嵌套表来实现，比如\(L[u][v] = 3\)的形式。
当图的顶点数远远大于边数时，如果使用邻接矩阵存储图的话会有大量空白，但使用邻接表不会有这种问题。所以图表示方案的选择常与图本身的特性有关系。用python字典模拟邻接表如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | """ Graph: addVertex(idx) 增加唯一标识为idx的顶点 addEdge(i1,i2,w) 在i1=>i2间加权重w的边 getWeight(i1,i2) 获得i1，i2间的边 getVertices(i) 获得i的所有邻接顶点 getEdges(i) 获得i的所有出边 vertices 获得图中所有顶点 edges 获得图中所有边 """ class Graph: def __init__(self): self.d = dict() def addVertex(self,i): self.d[i] = dict() def addEdge(self,i1,i2,w): self.d[i1][i2] = w def getWeight(self,i1,i2): return self.d[i1][i2] def getEdges(self,i): return self.d[i] def getVertices(self,i): return self.d[i].keys() def vertices(self): return self.d.keys() def edges(self): return self.d |
图的遍历
图的遍历有广度优先遍历与深度优先遍历两种策略，这两种策略与树的层次遍历和中序遍历十分的类似。最大的区别是遍历图时要用集合记录当前已到达的所有顶点，然后用该集合避免多次访问同个顶点。图的遍历和树的遍历还有一个区别是，树的遍历是从树根开始的，树上的所有节点都是可达的。而图没有根，所以遍历可从任何节点开始，并且不一定所有顶点都可达。
下面会给出“简化版”的广度优先遍历与深度优先遍历的算法，这个算法中的图是基于上述物理结构的。这两个简化版的算法的目标是从任意指定顶点\(x\)出发，按广度优先/深度优先这样的次序，“到达”且仅“到达”一次\(x\)的所有可达顶点。这里之所以用“简化版”这个称呼是因为在之后的文章中还要讨论“通用版”的广度优先搜索(BFS)和深度优先搜索(DFS)，通用版的BFS/DFS是很多其他图算法的框架，其远不止是一个“访问且仅访问一次所有顶点”的算法。
1 2 3 4 5 6 7 8 9 10 11 12 13 | def bfs(graph,vertex): visited = [vertex,] queue = [vertex,] while queue: vertex = queue.pop(0) for v in graph.getVertices(vertex): if v not in visited: queue.append(v) visited.append(v) print visited |
1 2 3 4 5 6 7 8 9 10 | def _dfs(graph,vertex,visited): for v in graph.getVertices(vertex): if v not in visited: visited.append(v) _dfs(graph,v,visited) return visited def dfs(graph,vertex): visited = _dfs(graph,vertex,[vertex,]) print(visited) |
简单分析算法的正确性，对于广度优先遍历而言，把“出队某顶点，扫描其全部邻接顶点，记录全部未访问顶点并入队这些顶点”这个过程称作一次“子遍历”。假设从\(u\)开始的广度优先遍历未到达\(v\)，但从\(u\)可达\(v\)。那么说明在任何子遍历中都没有到达过\(v\)，也就是任何连向\(v\)的边都没有访问过，那么说明所有有边连向\(v\)的顶点都没有发生过子遍历…这样一层层的反推，因为\(u\)有路径连向\(v\)最后会推得\(u\)没有发生过子遍历，导致矛盾。对于深度优先遍历而言，把“从某顶点开始执行子递归”当成一次“子遍历”。假设从\(u\)开始的深度优先遍历未到达\(v\)，但从\(u\)可达\(v\)，那说明任何“子遍历”都没有到达\(v\)，那么在所有有边连向\(v\)的顶点的子遍历在开始前\(v\)都未被到达，开始后\(v\)也未被到达，这就只可能是所有有边连向\(v\)的顶点都未被到达…这样一层层的反推也会得到\(u\)未发生过子遍历的矛盾。
简单分析算法代价，上面分析了所有可达顶点都会到达，然后\(visited\)保证这些顶点只到达一次(只发生一次“子遍历”)，无论广度优先还是深度优先，每个顶点\(u\)的“子遍历”一定会去访问这个顶点的发出边。所有可达顶点的所有发出边的上界是\(|E|\)，所以总代价一定不超过\(O(|V|+|E|)\)，总之代价是线性的。