基本数据结构的说明（四）

4.图
图(Graph)G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合,记为E(G)。
图一般可以采用三种方式来表示：使用一个二维数组；使用邻接表；使用边数组。图的遍历一般有深度优先的方式和广度优先的方式。
所谓深度优先：从图中某个初始顶点v出发,首先访问初始顶点v,然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点,再从w出发进行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。显然,这个遍历过程是个递归过程。
所谓广度优先：首先访问初始点vi,接着访问vi的所有未被访问过的邻接点vi1,vi2,…,vit,然后再按照vi1,vi2,…,vit的次序,访问每一个顶点的所有未被访问过的邻接点,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。
深度优先的伪码：
procedure dfs(G,v)
input: G=(V,E) is a graph;v∈V;
output: visited(u) is set to true for all nodes u reachable from v

visited(v)=true;
previsit(v);
for each edge(v,u) ∈E:
if not visited(u):dfs(u)
postvisit(v);
广度优先的伪码：
procedure dfs(G,s)
input: G=(V,E) is a graph;s∈V;
output: visited(u) is set to true for all nodes u reachable from v

Q=[s] (queue contains just s)
while Q is not empty
u=Q.remove();
visited(u)=true;
for all edges (u,v) ∈ E
if visited(v) is false
Q.insert(v);
小结：图的遍历算法DFS和BFS在实现时也就是采用的数据结构不一样而已，一个是采用栈（Stack），一个是采用队列（Queue），其实这里的数据结构都是采用一些特殊的数据结构而已。一个是FILO的Stack，一个是采用FIFO的Queue，未访问过的顶点都是放在Stack和Queue里的。对这些顶点的处理则采用FILO和FIFO的原则。OK，如果我们现在把未访问过的顶点的放进一个容器里，之后按照一定的规则取出这些顶点，那么就得到另一些图的算法了。如果是随机取出的，那么就是随机游走的算法了。后面的最小生成树，最短路径的算法都可以看作在这些基础上的算法。