深度优先遍历
1 program dfs;
2
3 type nodep=^node;
4 node=record adj:longint; next:nodep; end;
5 var g:array[1..10000]of nodep;
6 n,en,i:longint;
7 visited:array[1..10000]of boolean;
8 procedure init;
9 var i,x,y:longint;
10 p:nodep;
11 begin
12 fillchar(g,sizeof(g),0);
13 fillchar(visited,sizeof(visited),0);
14 read(n,en);
15 for i:=1 to en do
16 begin
17 read(x,y);
18 new(p); p^.adj:=y; p^.next:=g[x]; g[x]:=p;
19 new(p); p^.adj:=x; p^.next:=g[y]; g[y]:=p;
20 end;
21 end;
22 procedure dfs(k:longint);
23 var p:nodep;
24 begin
25 write(k,' ');
26 visited[k]:=true;
27 p:=g[k];
28 while (p<>nil) do
29 begin
30 if (not visited[p^.adj]) then
31 dfs(p^.adj);
32 p:=p^.next;
33 end;
34 end;
35
36 begin
37 repeat
38 init;
39 for i:=1 to n do
40 if not visited[i] then dfs(i);
41 writeln;
42 until eof;
43 end.
posted on 2011-11-03 19:11
龙在江湖 阅读(666)
评论(0) 编辑 收藏 引用 所属分类:
图论