图的两种遍历-课件·PPT.ppt

图的两种遍历
主讲人:山成虎
一、图的遍历
二、深度优先遍历
三、广(宽)度优先遍历
一、图的遍历
和树的遍历类似,可以从图的某个顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这个过程称为图的遍历。
图的遍历比树的遍历复杂。
树的遍历始于根结点,图中没有根结点。
图中可能存在回路。
常用的图遍历方法
深度优先遍历
宽度优先遍历
二、深度优先遍历
深度优先遍历类似于树的先根遍历,其基本思想为:
从图中某个顶点v0出发,访问此顶点。然后依次从v0未被访问的邻接结点出发深度优先遍历图,直到图中所有和顶点v0连通的顶点都被访问到。
若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直到图中所有顶点都被访问到为止。
注意:
1、图中可能包含回路,因此在遍历过程中,一个顶点有可能被重复访问,为此设置一个数组记录顶点是否被访问过。
2、图有可能不连通,必须保证图中所有顶点被访问。
var map:array[1..20,1..20] of integer;
for i:=1 to n do
if visited[i]=0 then
begin visited[i]:=1;work(i);end;
9 10
1 2
1 3
1 7
2 8
2 7
3 4
4 5
4 7
5 6
8 9
1 2 7 4 3 5 6 8 9
输入:
输出:
program xy;
var
map:array[1..20,1..20] of integer;
//邻接矩阵表示法(顺序存储)
visited:array[1..20] of integer;
//记录顶点是否被访问过
n,m,a,b,i:integer;
procedure work(x:integer);
var j:integer;
begin
write(x,' ');
for j:=1 to n do
if (map[x][j]=1) and (visited[j]=0) then
begin visited[j]:=1;work(j);end;
end;
深度优先遍历
图的深度优先遍历类似二叉树的先根遍历
begin
readln(n,m);
for i:=1 to m do
begin
readln(a,b);
map[a][b]:=1;
map[b][a]:=1;
end;
for i:=1 to n do
if visited[i]=0 then
begin visited[i]:=1;work(i);end;
end.
保证图中所有
顶点被访问
三、广(宽)度优先遍历
宽度优先遍历的基本思想为:
从图中某个顶点v0出发,访问此顶点。然后依次访问v0的各个未被访问过的邻接结点,然后分别从这些邻接结点出发宽度优先遍历图,直到图中所有和顶点v0连通的顶点都被访问到。
若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直到图中所有顶点都被访问到为止。
9 10
1 2
1 3
1 7
2 8
2 7
3 4
4 5
4 7
5 6
8 9
1 2 3 7 8 4 9 5 6
输入:
输出: