Pascal图的基本知识

Pascal图的基本知识
Pascal图的基本知识

Pascal图的基本知识
图是由顶点V的集合和边E的集合组成的二元组记G=（V,E）
完全图（每一对不同的顶点都有一条边相连,n个顶点的完全图共有n（n-1）/2条边）
顶点的度：与顶点关联的边的数目,有向图中等于该顶点的入度与出度之和.
入度——以该顶点为终点的边的数目和
出度——以该顶点为起点的边的数目和
度数为奇数的顶点叫做奇点,度数为偶数的点叫做偶点.
[定理1] 图G中所有顶点的度数之和等于边数的2倍.因为计算顶点的度数时.每条边均用到2次.
[定理2] 任意一个图一定有偶数个奇点.
图的存储
1.邻接矩阵
1(或权值) 表示 顶点i和顶点j有边(i和j的路程)
A(i,j)={
0 表示顶点i和顶点j无边
6.3图的遍历
1.深度优先遍历
遍历算法：
1)从某一顶点出发开始访问,被访问的顶点作相应的标记,输出访问顶点号.
2)从被访问的顶点出发,搜索与该顶点有边的关联的某个未被访问的邻接点
再从该邻接点出发进一步搜索与该顶点有边的关联的某个未被访问的邻接点,直到全部接点访问完毕.如图1从V1开始的深度优先遍历序列为V1,V2,V3,V4,V5.图2从V1开始的深度优先遍历序列为V1,V2,V4,V3.
算法过程：
procedure shendu(i);
begin
write(i);
v[i]:=true;
for j:=1 to n do
if (a[i,j]=1) and not(v[j]) then shendu(j);
end;
2.广度优先遍历
遍历算法：
1）从某个顶点出发开始访问,被访问的顶点作相应的标记,并输出访问顶点号；
2）从被访问的顶点出发,依次搜索与该顶点有边的关联的所有未被访问的邻接点,并作相应的标记.
3）再依次根据2）中所有被访问的邻接点,访问与这些邻接点相关的所有未被访问的邻接点,直到所有顶点被访问为止.如图3的广度优先遍历序列为C1,C2,C3,C4,C5,C6.
算法过程：
procedure guangdu(i);
begin
write(i);
v[i]:=true;
i进队;
repeat
队首元素出队设为k
for j:=1 to n do
if (a[k,j]=1) and (not v[j]) then
begin
write(j);
v[j]:=true;
j进队;
end;
until 队列q为空;
6.3 图的应用
例1:有A,B,C,D,E 5本书,要分给张、王、刘、赵、钱5位同学,每人只选一本.
用递归方式程序如下:
program allotbook;
type five=1..5;
const like:array[five,five] of 0..1=
((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1));
name:array[five] of string[5]=('zhang','wang','liu','zhao','qian');
var book:array[five] of five;
flag:set of five;
c:integer;
procedure print;
var i:integer;
begin
inc(c);
writeln('answer',c,':');
for i:=1 to 5 do
writeln(name[i]:10,':',chr(64+book[i]));
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to 5 do
if not(j in flag) and (like[i,j]>0) then
begin flag:=flag+[j];
book[i]:=j;
if i=5 then print else try(i+1);
flag:=flag-[j];
end
end;
begin
flag:=[];
c:=0;
try(1);
readln;
end.
用非递归方法编程如下:
program allotbook;
type five=1..5;
const like:array[five,five] of 0..1=
((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1));
name:array[five] of string[5]=('zhang','wang','liu','zhao','qian');
var book:array[five] of five;
flag:set of five;
c,dep,r:integer;
p:boolean;
procedure print;
var i:integer;
begin
inc(c);
writeln('answer',c,':');
for i:=1 to 5 do
writeln(name[i]:10,':',chr(64+book[i]));
end;
begin
flag:=[];
c:=0;dep:=0;
repeat
dep:=dep+1;
r:=0;
p:=false;
repeat
r:=r+1;
if not(r in flag) and (like[dep,r]>0) then
begin
flag:=flag+[r];
book[dep]:=r;
if dep=5 then print else p:=true
end
else if r>=5 then
begin
dep:=dep-1;
if dep=0 then p:=true else begin r:=book[dep];flag:=flag-[r] end;
end else p:=false;
until p=true;
until dep=0;
readln;
end.
例2: 中国象棋棋盘马自左下角往右上角跳.规定只许往左跳,不许往右跳编程找出所有跳法.
递归算法如下：
program tiaoma;
const
di:array[1..4] of integer=(1,2,2,1);
dj:array[1..4] of integer=(2,1,-1,-2);
var x,y:array[0..20] of integer;
c:integer;
procedure print(dep:integer);
var j:integer;
begin
c:=c+1;write(c,':');
for j:=0 to dep-1 do write('(',x[j],',',y[j],')->');
writeln('(',x[dep],',',y[dep],')');
end;
procedure try(dep,i,j:integer);
var r,ni,nj:byte;
begin
for r:=1 to 4 do
begin
ni:=i+di[r];
nj:=j+dj[r];
if (ni>0)and(ni<=8)and(nj>=0)and(nj<=4) then
begin
x[dep]:=ni;y[dep]:=nj ;
if (ni=8) and (nj=4) then print(dep) else try(dep+1,ni,nj)
end;
end;
end;
begin
x[0]:=0;y[0]:=0;
c:=0;
try(1,0,0);
readln;
end.
非递归算法如下：
program tiaom;
const
di:array[1..4] of integer=(1,2,2,1);
dj:array[1..4] of integer=(2,1,-1,-2);
var x,y:array[0..20] of integer;
b:array[0..20] of 0..4;
c,r,ni,nj,dep:integer;
p:boolean;
procedure print(dep:integer);
var j:integer;
begin
c:=c+1;write(c,':');
for j:=0 to dep-1 do write('(',x[j],',',y[j],')->');
writeln('(',x[dep],',',y[dep],')');
end;
begin
x[0]:=0;y[0]:=0;c:=0;
dep:=0;
repeat
dep:=dep+1;
r:=0;p:=false;
repeat
r:=r+1;
ni:=x[dep-1]+di[r];
nj:=y[dep-1]+dj[r];
if (ni>0)and(ni<=8)and(nj>=0)and(nj<=4) then
begin
x[dep]:=ni;y[dep]:=nj ;b[dep]:=r;
if (ni=8) and (nj=4) then print(dep) else p:=true;
end
else if r>=4 then begin dep:=dep-1;if dep=0 then p:=true else r:=b[dep]end
else p:=false;
until p=true;
until dep=0 ;
readln;
end.