《图及其应用课件》由会员分享，可在线阅读，更多相关《图及其应用课件（47页珍藏版）》请在金锄头文库上搜索。
1、第四讲 图,一、 图的基本概念 1、图的的定义 如果数据元素集合D中的各元素之间存在任意的前驱和后继关系R，则此数据结构G=（D，R）称为图。如果将数据元素抽象为结点，元素之间的先后关系用边表示，则图亦可以表示为G=（V，E），其中V是结点的有穷（非空）集合，E为边的集合。如果元素a是元素b的前驱，这种先后关系对应的边用(a，b)表示，即(a，b)E。图可以分为无向图和有向图两种形式。,2、无向图和有向图无向图：在图G=（V，E）中，如果对于任意的a，bV，当(a，b)E时，必有（b，a）E（即关系R对称），对称此图为无向图。在一无向图中用不带箭头的边 连接两个有关联的结点。在具有n个结点的无
2、向图中，边的最大数目为： 而边数达到最大值的图称为无向完全图。 在无向图中一个结点相连的边数称为该结点的度。 图(A) V=1,2,3,4 E=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4) 有向图：如果对于任意的a，bV，当(a，b)E时 ，(b，a)E未必成立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点（方向由前件指向后件）。例如图（b）为有向图。有向图中一个结点的后件个数称为该结点的出度，其前件个数称为该结点的入度。一个结点的入度和出度之和称为该结点的度。图中结点的最大度数称为图的度。例如下图 (b)）中结点1的出度和入度分别为1，结点1和
3、结点1度都为2。整个图的度为2。 图(B) V=1,2,3 E=,、 路径和连通集 在图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, v4,2、简单路径和回路 如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此路径为一条简单路径。图(a)中v1v2v3是一条简单路径，v1v3v4v1v3不是简单路径。x1=xk的简单路
4、径称为回路（也称为环）。例如图(b)中，v1v2v1为一条回路。,二、图的存储结构 图的相邻矩阵表示法 相邻矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的相邻矩阵是如下定义的二维数组a，其规模为n*n,type maxn=顶点数的上限； var a：array1.maxn，1.maxnof integer； f：array array1.maxnof boolean； 顶点的访问标志序列,上图中的图G1和图G2对应的相邻矩阵分别为：,0 1 1 1 01 0 1 1 11 1 0 1 01 1 1 0 10 1 0 1 0,相邻矩阵的特点： 1)无向图的相邻矩阵
5、是对称的，而有向图则不是。,2)相邻矩阵方便度数的计算。用相邻矩阵表示图: (1)容易判定任意两个结点之间是否有边相联; (2)并容易求得各个结点的度数。 (对于无权无向图的相邻矩阵，第i行元素值的和就是Vi的度数；对于无权有向图的相邻矩阵，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；)对于有权无向图的相邻矩阵，第i行（或第i列）中元素值0的元素个数就是Vi的度数；对于有权有向图的相邻矩阵，第i行中元素值0的元素个数就是Vi的出度；第i列元素值0的元素个数就是Vi的入度。,三、图的遍历 给出一个图G和其中任意一个结点V0，从V0出发系统地访问G中所有结点，每一个结点被访问一
6、次，这就叫图的遍历。 通常有两种遍历方法： 深度优先搜索dfs 广度优先搜索bfs 它们对无向图和有向图都适用。我们以相邻矩阵存储结构给出深度优先搜索和广度优先搜索的程序。,1、深度优先搜索DFS 深度优先搜索类似于树的前序遍历，是树的前序遍历的推广。其搜索过程如下： 假设初始时所有结点未曾被访问。深度优先搜索从某个结点V0出发，访问此结点。然后依次从V0的未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相连的结点都被访问到。若此时图中尚有结点未被访问，则另选一个未曾访问的结点作起始点，重复上述过程，直至图中所有结点都被访问为止。换句话说，深度优先搜索遍历图的过程是以V0为起始点，
7、由左而右，依次访问由V0出发的每条路径。,调用一次dfs(i)，可按深度优先搜索的顺序访问处理结点i所在的连通分支（或强连通分支），dfs(i)的时间复杂度为W（n2）。整个图按深度优先搜索顺序遍历的过程如下：,2、广度优先搜索(宽度优先搜索）BFS 广度优先搜索类似于树的按层次遍历的过程，其搜索过程如下： 假设从图中某结点v0出发，在访问了v0之后依次访问v0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。若此时图中尚有结点未被访问，则任选其中的一个作起始点，重复上述过程，直至图中所有结点都被访问到为止。换句话说，按广度优先顺
8、序搜索遍历图的过程是以v0为起始点，由近及远，依次访问和v0有路径相连且路径长度为1，2，3的结点。,bfs(i)的时间复杂度为W（n2）。调用一次bfs(i)可按广度优先搜索的顺序访问处理结点i所在的连通分支（或强连通分支）。整个图按广度优先搜索顺序遍历的过程如下：,1、写出图的深度优先搜索(DFS)算法和广度优先搜索(BFS)算法。 program dfsbfs(input,output); const n=8; var a:array1.n,1.nof integer;图的邻接矩阵 visited,come:array1.nof integer;访问标志 queue:array1.nof
9、 integer;队列 t:array1.nof char;结点信息 i,head,tail:integer;,procedure init; var i,j,e,k:integer; begin for i:=1 to n do read(ti);顶点信息 fillchar(a,sizeof(a),0); read(e);边数 for k:=1 to e do读入边的点信息,建立邻接矩阵 begin read(i,j); ai,j:=1; aj,i:=1; end; end;,procedure dfs(i:integer); var j:integer; begin write(ti);输
10、出结点信息 visitedi:=1;访问标志 for j:=1 to n do深度优先搜索i的邻接点 if (ai,j=1) and (visitedj=0) then dfs(j); end;,procedure bfs(i:integer);广搜 var j:integer; begin write(ti); visitedi:=1; tail:=tail+1;尾指针加1 queuetail:=i;入队列 while head =tail do队列非空 begin for j:=1 to n do搜索i的所有邻接点,如果没访问,入队列 if (aqueuehead,j=1 ) and (v
11、isitedj=0) then begin write(tj); visitedj:=1; tail:=tail+1; queuetail:=j; end; head:=head+1;出队列,访问队首元素 end; end;,Begin writeln; init; for i:=1 to n do visitedi:=0; for i:=1 to n do if visitedi=0 then dfs(i); writeln; head:=0; tail:=0; for i:=1 to n do visitedi:=0; for i:=1 to n do if visitedi=0 then
12、 bfs(i); end.,四、图的应用 （一）、拓扑排序 士兵排队 有n个士兵（100），编号依次为1，2，3 。n，排队训练，现在指挥官要把这些士兵从高到矮依次排成行，但现在指挥官不能直接获得每个人的身高信息，只能获得”i比j高“这样的比较结果输入：第一行为一个整数n，表示士兵的个数，以下若干行，每行两个数 i,j：表示i比j高。 输出：一种合法的排队序列 样例： 输入： 4 1 2 2 3 4 3 输出： 1 2 4 3,建立有向图，如果i比j高，建立一条由i指向j的有向边J的入度加先找一个入度为的结点，即没有比他高的结点输出，去掉该结点，同时把比他矮的结点的入度减再找入度为的结点，依次
13、类推直到最后输出完毕,const maxn=100;拓扑排序 var map:array1.maxn,1.maxnof integer;有向图 into:array1.maxnof byte;结点的入度 a:array1.maxnof integer;拓扑序列 i,n:integer; f:boolean;找到拓扑序列的标志：什么情况下无拓扑序列？,procedure init;建有向图 var i,j:integer; begin assign(input,tp.in); reset(input); fillchar(map,sizeof(map),0); fillchar(into,siz
14、eof(into),0); fillchar(a,sizeof(a),0); readln(n); while not eof do文件结束标志 begin readln(i,j);读入士兵的信息：i比j高 mapi,j:=1; inc(intoj)统计j的入度 end; close(input); end;,procedure work; var i,j,k,t:integer; begin t:=0; for i:=1 to n do begin j:=1; while(j0) do inc(j);寻找入度为0点的结点 if jn then begin f:=false;exit;end
15、无入度为0的结点，问题无解 else begin inc(t); at:=j; intoj:=$ff; 赋结点入度为较大的数 for k:=1 to n do if mapj,k=1 then dec(intok);k的入度减1 end; end; end;,begin f:=true; init; work; if f then begin for i:=1 to n-1 do write(ai, ); writeln(an); end else writeln(no answer); end.,（二）、哈密顿路,邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的
16、村子出发，途中每个村子仅且经过一次，送完所有的信。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线。,输入： 第一行：整数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 4,哈密顿路：找一条包含所有结点的简单路径 program h
