pascal图的遍历问题(含题解)
- 格式：pdf
- 大小：77.47 KB
- 文档页数：4
end; for i:=1 to n-1 do write(b[i],' '); writeln(b[n]); end.
【本题小结】 本题考察了深度优先遍历和宽度优先遍历的使用。
3、广度（宽度）优先遍历 图的广度优先搜索类似于树的按层次遍历。从图中某个顶点 V0 出发，访问
此顶点，然后依次访问与 V0 邻接的、未被访问过的所有顶点，然后再分别从这 些顶点出发进行广度优先遍历，直到图中所有被访问过的顶点的相邻顶点都被访 问到。若此时图中还有顶点尚未被访问，则另选图中一个未被访问过的顶点作为 起点，重复上述过程，直到图中所有顶点都被访问到为止。如上左图从顶点 a 出发，进行广度优先遍历的结果为：a，b，d，e，f，c，g；如上右图从顶点 V1 出发，进行广度优先遍历的结果为：V1，V2，V3，V4，V5，V6，V7，V8。
（2）输出图的深度优先遍历结果(从节点 1 开始遍历，序号从小到大) （3）输出图的广度优先遍历结果（从节点 1 开始遍历，序号从小到大） 输入 第一行：节点总数 n(<=100) 下面 n 行：图 G 的邻接矩阵 输出 第一行：图的深度优先遍历 第二行：图的广度优先遍历 样例输入 8 01110000 10000100 10001000 10001110 00110000 01010000 00010001 00000010 样例输出 12645378 12346578 提示
二、图的遍历 1、概念
从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一 次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标 志数组 visited[i]，未访问时值为 false，访问一次后就改为 true。
图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。
2、深度优先遍历 图的深度优先搜索类似于树的先序遍历。从图中某个顶点 Vi 出发，访问此
顶点并作已访问标记，然后从 Vi 的一个未被访问过的邻接点 Vj 出发再进行深度 优先遍历，当 Vi 的所有邻接点都被访问过时，则退回到上一个顶点 Vk，再从 Vk 的另一个未被访问过的邻接点出发进行深度优先遍历，直至图中所有顶点都被访 问到为止。如下左图从顶点 a 出发，进行深度优先遍历的结果为：a，b，c，d， e，g，f；右图从 V1 出发进行深度优先遍历的结果为：V1，V2，V4，V8，V5，V3， V6，V7。
end; begin
read(n); for i:=1 to n do ｛初始化，如果是 1 就设成 true，代表可以走，是 0 就相 反处理｝
for j:=1 to n do begin read(x); if x=1 then f[i,j]:=true; end;
a[1]:=1;t:=1;c[1]:=true; ｛第一个点是 1，并把 1 设好标志位｝ sc(1); ｛开始深度优先遍历｝ fillchar(c,sizeof(c),false); ｛开始广度优先遍历｝ t:=1;w:=1;b[w]:=1; c[w]:=true; ｛与深度优先遍历的初始化一样｝ while t<=w do
【问题分析】 题目意思很简单，给出一个矩阵，分别用深度优先遍历和广度优先遍历求出
遍历的结果。
【算法分析】 第一次遍历就用深度优先遍历，从点 1 开始，如果 a[1,i]=1，就继续搜下去，
并把这个点的位置保存下来（a[t]=i）,设好标志位（c[i]=true）然后再搜 i 这个点，直到搜到底为，要 把当前这个点的所有儿子都找出来，并保存，设标志位，然后搜大儿子、二儿 子……直到底为止。
begin for i:=1 to n do ｛一个点一个点试过来｝ Begin x:=b[t]; if f[x,i] and (c[i]=false) then {与 x 相连接，并没走过就可以走｝ begin c[i]:=true; ｛设标志位｝ inc(w); b[w]:=i; ｛保存新的点｝ end; end; inc(t);
begin for i:=1 to n-1 do write(a[i],' '); writeln(a[n]);
end else
for i:=1 to n do ｛一个点一个点试过来｝ if f[k,i] and (c[i]=false) then ｛与 k 相连接，并没走过就可以走｝ begin inc(t); a[t]:=i; ｛保存新的点｝ c[i]:=true; ｛设标志位｝ sc(i); end;
两种遍历方法相比，深度优先遍历实际上是尽可能地走“顶点表”；而广度 优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进 行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行 广度优先遍历。 问题 B: 图的存储和遍历(图论) 时间限制: 1 Sec 内存限制: 128 MB 提交: 175 解决: 49 [提交][状态][讨论版] 题目描述 memb.pas 已知图 G 已用邻接矩阵存储。 （1）编写一个程序，将图 G 转化为邻接表
【参考程序】 var n,i,j,x,t,w:longint;
f:array[0..1000,0..1000] of boolean; c:array[0..1000] of boolean; a,b:array[0..1000] of longint; procedure sc(k:longint); var i:longint; begin if t=n then ｛搜完了，就输出｝
【本题小结】 本题考察了深度优先遍历和宽度优先遍历的使用。
3、广度（宽度）优先遍历 图的广度优先搜索类似于树的按层次遍历。从图中某个顶点 V0 出发，访问
此顶点，然后依次访问与 V0 邻接的、未被访问过的所有顶点，然后再分别从这 些顶点出发进行广度优先遍历，直到图中所有被访问过的顶点的相邻顶点都被访 问到。若此时图中还有顶点尚未被访问，则另选图中一个未被访问过的顶点作为 起点，重复上述过程，直到图中所有顶点都被访问到为止。如上左图从顶点 a 出发，进行广度优先遍历的结果为：a，b，d，e，f，c，g；如上右图从顶点 V1 出发，进行广度优先遍历的结果为：V1，V2，V3，V4，V5，V6，V7，V8。
（2）输出图的深度优先遍历结果(从节点 1 开始遍历，序号从小到大) （3）输出图的广度优先遍历结果（从节点 1 开始遍历，序号从小到大） 输入 第一行：节点总数 n(<=100) 下面 n 行：图 G 的邻接矩阵 输出 第一行：图的深度优先遍历 第二行：图的广度优先遍历 样例输入 8 01110000 10000100 10001000 10001110 00110000 01010000 00010001 00000010 样例输出 12645378 12346578 提示
二、图的遍历 1、概念
从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一 次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标 志数组 visited[i]，未访问时值为 false，访问一次后就改为 true。
图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。
2、深度优先遍历 图的深度优先搜索类似于树的先序遍历。从图中某个顶点 Vi 出发，访问此
顶点并作已访问标记，然后从 Vi 的一个未被访问过的邻接点 Vj 出发再进行深度 优先遍历，当 Vi 的所有邻接点都被访问过时，则退回到上一个顶点 Vk，再从 Vk 的另一个未被访问过的邻接点出发进行深度优先遍历，直至图中所有顶点都被访 问到为止。如下左图从顶点 a 出发，进行深度优先遍历的结果为：a，b，c，d， e，g，f；右图从 V1 出发进行深度优先遍历的结果为：V1，V2，V4，V8，V5，V3， V6，V7。
end; begin
read(n); for i:=1 to n do ｛初始化，如果是 1 就设成 true，代表可以走，是 0 就相 反处理｝
for j:=1 to n do begin read(x); if x=1 then f[i,j]:=true; end;
a[1]:=1;t:=1;c[1]:=true; ｛第一个点是 1，并把 1 设好标志位｝ sc(1); ｛开始深度优先遍历｝ fillchar(c,sizeof(c),false); ｛开始广度优先遍历｝ t:=1;w:=1;b[w]:=1; c[w]:=true; ｛与深度优先遍历的初始化一样｝ while t<=w do
【问题分析】 题目意思很简单，给出一个矩阵，分别用深度优先遍历和广度优先遍历求出
遍历的结果。
【算法分析】 第一次遍历就用深度优先遍历，从点 1 开始，如果 a[1,i]=1，就继续搜下去，
并把这个点的位置保存下来（a[t]=i）,设好标志位（c[i]=true）然后再搜 i 这个点，直到搜到底为，要 把当前这个点的所有儿子都找出来，并保存，设标志位，然后搜大儿子、二儿 子……直到底为止。
begin for i:=1 to n do ｛一个点一个点试过来｝ Begin x:=b[t]; if f[x,i] and (c[i]=false) then {与 x 相连接，并没走过就可以走｝ begin c[i]:=true; ｛设标志位｝ inc(w); b[w]:=i; ｛保存新的点｝ end; end; inc(t);
begin for i:=1 to n-1 do write(a[i],' '); writeln(a[n]);
end else
for i:=1 to n do ｛一个点一个点试过来｝ if f[k,i] and (c[i]=false) then ｛与 k 相连接，并没走过就可以走｝ begin inc(t); a[t]:=i; ｛保存新的点｝ c[i]:=true; ｛设标志位｝ sc(i); end;
两种遍历方法相比，深度优先遍历实际上是尽可能地走“顶点表”；而广度 优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进 行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行 广度优先遍历。 问题 B: 图的存储和遍历(图论) 时间限制: 1 Sec 内存限制: 128 MB 提交: 175 解决: 49 [提交][状态][讨论版] 题目描述 memb.pas 已知图 G 已用邻接矩阵存储。 （1）编写一个程序，将图 G 转化为邻接表
【参考程序】 var n,i,j,x,t,w:longint;
f:array[0..1000,0..1000] of boolean; c:array[0..1000] of boolean; a,b:array[0..1000] of longint; procedure sc(k:longint); var i:longint; begin if t=n then ｛搜完了，就输出｝
