网上找的一些第四讲图及其应用

1、第四讲 图 一、 图的基本概念1、图的的定义 图是由顶点V的集合和边E的集合组成的二元组： 记G=（V，E） 2、无向图和有向图无向图： 在图G=（V，E）中，如果对于任意的a，bV，当(a，b)E时，必有（b，a）E（即关系R对称），对称此图为无向图。在一无向图中用不带箭头的边 V=V1,V2,V3,V4,V5 E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1) 有向图：如果对于任意的a，bV，当(a，b)E时 ，(b，a)E未必成立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点。V=V1,V2,V3,V4

2、 E=, 顶点的度：无向图：与顶点关联的边的数目。有向图：等于该顶点的入度与出度之和。入度以该顶点为终点的边的数目和出度以该顶点为起点的边的数目和 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。3、顶点的度4、 路径和连通集 在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1xk(k1) x1=a，xk=b (xi，xi+1)E i=1k-1则称结点序列x1=a，x2，xk=b为结点a到结点b的一条路径，而路径上边的数目k-1称为该路径的长度，并称结点集合x1，xk为连通集。V1, v2, v5, v45、简单路径和回路如果一条路径上的结点除起点x1和终点xk可以相同

3、外，其它结点均不相同，则称此路径为一条简单路径。图(a)中v1v2v3是一条简单路径，v1v3v4v1v3不是简单路径。x1=xk的简单路径称为回路（也称为环）。例如图(b)中，v1v2v1为一条回路。二、图的存储结构图的相邻矩阵表示法 相邻矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的相邻矩阵是如下定义的二维数组a，其规模为n*n 1(或权值) 表示 顶点i和顶点j有边(i和j的路程) A(i,j)= 0 表示顶点i和顶点j无边 上图中的图G1和图G2对应的相邻矩阵分别为： 邻接矩阵的特点： 1)无向图的相邻矩阵是对称的，而有向图则不是。 2)相邻矩阵方便度数

4、的计算。用相邻矩阵表示图: (1)容易判定任意两个结点之间是否有边相联; (2)并容易求得各个结点的度数。 (对于无权无向图的相邻矩阵，第i行元素值的和就是Vi的度数；对于无权有向图的相邻矩阵，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；)对于有权无向图的相邻矩阵，第i行（或第i列）中元素值0的元素个数就是Vi的度数；对于有权有向图的相邻矩阵，第i行中元素值0的元素个数就是Vi的出度；第i列元素值0的元素个数就是Vi的入度。三、图的遍历 给出一个图G和其中任意一个结点V0，从V0出发访问G中所有结点，每一个结点被访问一次，这就叫图的遍历。 通常有两种遍历方法： 深度优先搜索

5、dfs 广度优先搜索bfs 1、深度优先搜索DFS遍历算法： 1)从某一顶点出发开始访问,被访问的顶点作相应的标记,输出访问顶点号。 2)从被访问的顶点出发,搜索与该顶点有边的关联的某个未被访问的邻接点。 再从该邻接点出发进一步搜索与该顶点有边的关联的某个未被访问的邻接点,直到全部接点访问完毕1435678292、广度优先搜索(宽度优先搜索）BFS 广度优先搜索按层次遍历的过程，其搜索过程如下： 假设从图中某结点v0出发，在访问了v0之后依次访问v0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。依次访问和v0有路径相连且路径长

6、度为1，2，3的结点。14356782914356782输入：8 101 41 51 62 6 2 73 53 43 75 75 8编程实现：输入下图，按深度优先遍历和广度优先遍历输出图的结点。图的dfsconst max=100;var a:array1.max,1.max of integer; f:array1.max of 0.1; n,m,i:integer; procedure init; var i,j,x,y:integer; begin readln(n,m); fillchar(f,sizeof(f),0); for i:=1 to m do begin readln(x,

7、y); ax,y:=1; ay,x:=1; end; end;procedure dfs(i:integer);深搜 var j:integer; begin write(i, ); fi:=1; for j:=1 to n do if (fj=0)and(ai,j=1) then dfs(j); end;procedure bfs(i:integer);广搜 var j,k:integer; begin fillchar(q,sizeof(q),0); open:=0; 队首 closed:=1; 尾 q1:=i; i进队列 write(i, ); fi:=1; 标志 while openc

8、losed do 队列不空 begin inc(open); k:=qopen; 出队 for j:=1 to n do if (ak,j=1)and(fj=0) then begin write(j, ); fj:=1; inc(closed); 进队 qclosed:=j; end; end; end;BEGIN init; for i:=1 to n do if fi=0 then dfs(i); writeln; fillchar(f,sizeof(f),0); / for i:=1 to n do / if fi=0 then bfs(i); bfs(1);END.四、图的应用1、犯

9、罪团伙 警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。输入：第一行：n（=1000,罪犯数量），第二行：m（5000，关系数量）以下若干行：每行两个数：I 和j，中间一个空格隔开，表示罪犯i和罪犯j相互认识。输出：一个整数，犯罪团伙的数量。样例输入：11 8 1 24 35 41 35 67 105 108 9输出：3说明：共三个犯罪团伙。const maxn=10

10、00;var a:array1.maxn,1.maxnof longint; visited:array1.maxnof 0.1; t:array1.maxnof char; n,m,i,s:longint; procedure init; var i,x,y:longint; begin assign(input,group5.in);reset(input); readln(n); readln(m); for i:=1 to m do begin readln(x,y); ax,y:=1; ay,x:=1; end; close(input); end;procedure dfs(i:l

11、ongint); var j:longint; begin visitedi:=1; for j:=1 to n do if (ai,j=1) and (visitedj=0) then dfs(j); end;Begin init; s:=0; for i:=1 to n do visitedi:=0; for i:=1 to n do if visitedi=0 then begin dfs(i); inc(s); end; writeln(s); end.12354672、哈密顿路 邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的村子出发，途中每个村子仅且经

12、过一次，送完所有的信。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。输入：第一行：整数n：村子的个数。接下来是一个n*n的0、1矩阵，表示n个村子的连同情况，如：aI,j=1 ，表示第i和第j个村子之间有路可走，如果aI,j=0，表示他们之间无路可走。输出：一条可行的路线输入：70 1 0 1 1 0 01 0 1 0 1 0 00 1 0 0 0 0 11 0 0 0 0 0 01 1 0 0 0 1 00 0 0 0 1 0 10 0 1 0 0 1 0输出：2 3 7 6 5 1 4const maxn=100;算法一var a:array1.maxn,1.maxnof i

13、nteger; visited:array1.maxnof 0.1; b:array1.maxn of 1.maxn; n,m,i:integer; found:integer; procedure init; var i,j:integer; begin assign(input,a.in);reset(input); readln(n); for i:=1 to n do for j:=1 to n do read(ai,j); close(input); end; procedure print; var i:integer; begin found:=1; for i:=1 to n-

14、1 do write(bi, ); writeln(bn); end; procedure dfs(i:integer); var j,k:integer; begin if n=m then print; for j:=1 to n do if (aj,i=1) and (visitedj=0) then begin visitedj:=1; m:=m+1; bm:=j; dfs(j); visitedj:=0; m:=m-1; end; end; Begin init; found:=0; for i:= 1 to n do begin fillchar(visited,sizeof(vi

15、sited),0); m:=1; b1:=i; visitedi:=1; dfs(i); end; if found=0 then writeln(no road); end.算法二procedure dfs(i,k:integer); 结点i是路上的第k个结点 var j:integer; begin if k=n then print; for j:=1 to n do if (aj,i=1) and (visitedj=0) then begin visitedj:=1; bk+1:=j; dfs(j,k+1); visitedj:=0; end; end;Begin init; fou

16、nd:=0; for i:= 1 to n do begin fillchar(visited,sizeof(visited),0); m:=1; b1:=i; visitedi:=1; dfs(i,1); end; if found=0 then writeln(no road); end.3 、安排座位 n个客人围着一个桌子吃饭，每一个人都至少认识其他的2个客人。请设计程序求得n个人的一种坐法，使得每个人都认识他左右的客人。输入:第一行:n（吃饭人的个数）。以下n行：第i行的第一个数k表示第i个人认识的人数，后面k个数依次为i认识的人的编号。输出：所有座法，要求第一个人为1号作为起点，按顺

17、时针输出其它人的编号。样例输入：62 3 63 4 5 63 1 4 63 2 3 53 2 4 64 1 2 3 5样例输出：1 3 4 2 5 61 3 4 5 2 61 6 2 5 4 31 6 5 2 4 3procedure dfs(i:integer); var j,k:integer; begin if (n=m)and(ab1,bm=1) then print; for j:=1 to n do if (ai,j=1) and (visitedj=0) then begin visitedj:=1; m:=m+1; bm:=j; dfs(j); visitedj:=0; m:=

18、m-1; end; end;Begin init; fillchar(visited,sizeof(visited),0); found:=0; m:=1; b1:=1; visited1:=1; dfs(1); if found=0 then writeln(no road); end.4、素数链设计程序将1。n（20）排成一排，使任意两个相邻的数的和为素数。第1个和最后一个的和也为素数.输出:第一个数为1.const maxn=100;var visited:array1.maxnof 0.1; b:array1.maxn of 1.maxn; n,m,i:integer; found:i

19、nteger; function check(i:integer):boolean; var j:integer; begin for j:=2 to i-1 do if i mod j=0 then begin check:=false; exit; end; check:=true; end; procedure print; var i:integer; begin found:=1; for i:=1 to n-1 do write(bi, ); writeln(bn); halt; end; procedure dfs(i:integer); var j,k:integer; beg

20、in if (n=m)and(check(b1+bm) then print; for j:=1 to n do if (check(i+j) and (visitedj=0) then begin visitedj:=1; m:=m+1; bm:=j; dfs(j); visitedj:=0; m:=m-1; end; end;Begin fillchar(visited,sizeof(visited),0); n:=20; found:=0; m:=1; b1:=1; visited1:=1; dfs(1); if found=0 then writeln(no road); end.问题

21、描述 学校放暑假时，信息学辅导教师有n本书要分给参加培训的n个学生。如：A，B，C，D，E共5本书要分给参加培训的张、刘、王、李、孙5位学生，每人只能选1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。ABCDE张YY王YY刘YY孙Y李YY5、借书问题输入格式：第一行一个数n（学生的个数，书的数量） 以下共n行，每行n个0或1（由空格隔开），第I行数据表示第i个同学对所有书的喜爱情况。0表示不喜欢该书，1表示喜欢该书。输出格式：依次输出每个学生分到的书号。样例：输入：book.in50 0 1 1 01 1 0 0 00 1 1 0 00 0 0 1 00 1 0 0 1输出：book.out3 1 2 4 5分析: a:array1.maxn,1.maxnof 0.1; b:array1.maxnof integer; 方案:bi是第i个人借第bi本书 book:array1.maxnof boolean; booki:能否可以借第i本书, 初始:true,一旦有人借了:就改为:false算法设计:procedure try(i:integer);搜索第i个人可以借的书bi var j:intege