图论1——图的遍历与图的最小生成树
一、图的遍历
图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visit[n]作为对顶点的标记，当顶点vi未被访问，visit[i]值为0；当vi已被访问，则visit[i]值为1。
有两种遍历方法（它们对无向图，有向图都适用）
深度优先遍历
广度优先遍历
1、深度优先遍历
从图中某顶点v出发：
1）访问顶点v；
2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；
对于给定的图G=（V，E），首先将V中每一个顶点都标记为未被访问，然后，选取一个源点vV，将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。
例：在下图中，从V0开始进行一次深度遍历的过程如图所示：
深度优先遍历得到的遍历序列为：
序列1：V0,V1,V3,V7,V4,V2,V5,V6
序列2：V0,V1,V4,V7,V3,V2,V5,V6
由于没有规定访问邻接点的顺序，深度优先序列不是唯一的。
但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。
例如：对下图（a）的邻接表存储（图b）的遍历过程如图（c）。
图a 图b
图c
DFS序列：c0 c1 c3 c4 c5 c2
英文翻译在线翻译采用邻接表存储结构的深度优先遍历算法实现：
Pascal语言：
procedure dfs(g:adjgraph;i:integer);
var
p:edgenode;
begin
writeln('visit vertex:',g伦敦奥运主题曲.adjlist[i]^.vertex);
visited[i]:=true;
p:=g.adjlist[i]^.firstedge;
while p<>nil do
begin
if not visited[p^.adjvex] then dfs(g,p^.adjvex);
p:=pchoir^.next;
end;
end;
procedure dfstraver(g:adjgraph);
口译笔译
var
i:integer;
begin
for i:=1 alpineto g.nneither nor的用法 do
visited[i]:=fal;
for i:=1 to g.n do
if not visited[i] then dfs(g,i);
end;
C语言：
/*********************************************************/
/* 图的深度优先遍历算法 */
/* 文件名：dfs.c 函数名：dfs()、dfstraver() */
/********************************************************/
int visited[m];
void dfs(adjgraph g,int i)
{ /*以vi为出发点深度优先遍历顶点vi所在的连通分量*/
edgenode *p;
开房屋租赁发票 printf("visit vertex: %c \n",g.adjlist[i].vertex); /*访问顶点i*/
visited[i]=1;
p=g.adjlist[i].firstedge;
while (p) /*从p的邻接点出发进行深度优先搜索*/
{ if (!visited[p->adjvex])
dfs(g,p->adjvex); /*递归*/
p=p->next;
}
}
void dfstraver(adjgraph g)
{moves like jagger歌词 /* 深度优先遍历图g */
int i;
for (i=0;i<g.n;i++)
visited[i]=0; /*初始化标志数组*/
for (i=0;i<g.n;i++)
textif (!visited[i]) /*vi未访问过*/
dfs(g,i);
}
图的深度优先遍历算法（邻接表表示法）
算法分析：
对于具有n个顶点和e条边的无向图或有向图，遍历算法dfstraver对图中每个顶点至多调用一次dfs。从dfstraver中调用dfs或dfs内部递归调用自己的最大次数为n。当访问某顶点vi时，dfs的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接表表示图时，需
搜索第i个边表上的所有结点，因此，对所有n个顶点访问，在邻接表上需将边表中所有O（e）个结点检查一遍。所以，dfstraver算法的时间复杂度为O（n+e）。
2、广度优先遍历
toroidal
图中某未访问过的顶点vi出发：
1）访问顶点vi；
2）访问 vi 的所有未被访问的邻接点w1 ,w2 , …wk ；
3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；
例如：求图G 的以V0起点的广度优先序列。
以V0起点的广度优先序列为：V0,V1,V2,V3,V4,V5,V6,V7
从C0出发的BFS序列为：c0 c1 c2 c3 c4 c5
