《图算法基础知识》PPT课件.ppt

1、图算法（一）,Graph Algorithms,图,图 G = (V, E) V = 顶点的非空有限集 E = 边集 = V V的子集，V中顶点对，边的有限集。 |E| = O(|V|2) 简单图(Sample Graph) 任意两个顶点最多只有一条边，且每个点都没有连接到自身的边。 完全图(Complete Grapth) 若有n个顶点的无向图n(n-1)/2条边，则此图为完全图。,图的扩展,扩展: 连通图（ connected graph） 从图中每一顶点都有到其它顶点的路径 。 无向图（ undirected graph）: 边(u,v) = 边 (v,u) 有向图 （directed

2、graph）: (u,v) 表示从顶点u 到顶点 v的一条有向边, 记为 uv 一个不含有环的有向图称为无环有向图(Directed acyclic graphs ,DAG）。 加权图（ weighted graph） 图中不是边就是顶点与权关联，例如：公路交通图，边以距离w为权。,图,通常用边数 |E|和顶点数|V|描述运行时间。 无向图中 0|E|V|(|V|-1)/2 有向图中 0|E|V|(|V|-1) 若|E| |V|2 ，图是稠密的 dense 若 |E| |V| ，图是稀疏的 sparse 对稠密图和稀疏图使用不同的数据结构,图的表示,假设 V = 1, 2, , n 邻接矩阵（

3、adjacency matrix） 将图表示成一个 n x n 矩阵 A: Ai, j = 1 若边 (i, j) E (或边的权wij)= 0 若边 (i, j) E,图: 邻接矩阵,Example:,1,2,4,3,有向图 非对称矩阵,图: 邻接矩阵,Example:,1,2,4,3,a,d,b,c,图: 邻接矩阵,Example:,1,2,4,3,a,d,b,c,图: 邻接矩阵,Example:,1,2,4,3,5,1,4,3,图: 邻接矩阵,Example:,1,2,4,3,a,d,b,c,无向图 对称矩阵,图: 邻接矩阵,邻接矩阵的实现 const maxlength=100 最大顶

4、点数 type graph=array1.maxlength,1.maxlength of integer; 二维数组,输入和查看一遍邻接矩阵需要多少时间？ 答: O(|V|2) 存储一个邻接矩阵需要多少存储空间？ 答: O(|V|2) 稀疏图（|E|V|或|E|V|),邻接矩阵是稀疏矩阵，浪费空间，因此采用邻接表更有效。,图: 邻接矩阵,图:邻接表,邻接表: 对每个顶点 v V, 将v的所有邻接点存放在一个列表中。 Example: Adj1 = 2,3 Adj2 = 3 Adj3 = Adj4 = 3,1,2,4,3,1,2,4,3,图:邻接表,1,2,3,nil,2,3,nil,3,ni

5、l,4,3,nil,邻接表的实现 Type pointer=adjnode adjnode=record adjvex:integer; 该点在图中的位置 next:pointer; 指向下一个顶点的指针 infor: ; 与边有关的信息，如权值w Adjlist=array1.maxlength of pointer;,图:邻接表,无环有向图的拓扑排序 Directed acyclic graphs( DAG) topological sort,DAG:不含回路的有向图称为无环有向图。 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。,如果有向图G有一个拓扑排序,则G是一个有向无

6、环图.反之, 任一有向无环图必可进行拓扑排序。,何谓“拓扑排序”？,按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。,由此所得顶点的线性序列称之为拓扑有序序列,例如：对于下列有向图,可求得拓扑有序序列： A B C D 或 A C B D,反之，对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路 B, C, D,如何进行拓扑排序？,一、从有向图中选取一个没有前驱 的顶点，并输出之;,重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。,二、从有向图中删去此顶点以及所 有以它为尾的弧;,a,b,h,c,

7、d,g,f,e,在算法中需要用定量的描述替代定性的概念,没有前驱的顶点 入度为零的顶点,删除顶点及以它为尾的弧 弧头顶点的入度减1,拓扑排序算法,Function topsort:boolean; P140 var i,count:integer; wadj:Arr3;/用来表示图的邻接表表头数组 indeg:Arr1; /一维数组，存储每个顶点的入度 p:wpointer; /链表，邻接表 q:queue; /队列q保存入度为零且未被排序的顶点 begin /算法依次对q的出队元素进行编号 topsort:=true; count:=0; makenull(q); /清空队列q fillch

8、ar(indeg,sizeof(indeg),0); /数组indeg存储每个顶点入度,/通过遍历邻接表，计算所有顶点的入度 For i:=1 to n do begin p:=wadji; /顶点i的邻接表的第一个邻接点 while pnil do /依次为顶点i的所有邻接点入度加1 begin inc(indegp.v); p:=p.next; end; End;,/入度为0的顶点加入队列q For i:=1 to n do if indegi=0 then enqueue(i,q); /入队 /队列q的队首顶点出队，与该顶点邻接的顶点的出度减1 While not empty(q) do

9、 begin i:=dequeue(q); inc(count); /计数器加1 ordi:=count; /ord数组存储顶点i的排序后的序号 p:=wadji; while pnil do / 该循环将顶点i的所有邻接点入度减1 begin dec(indegp.v); if indegp.v=0 then enqueue (p.v,q); p:=p.next; end End,/入度为0的顶点数小于n时，存在环； 否则图不存在环，且可进行拓扑排序，ord数组存储的就是排序后的序号 If countn then begin writeln(graph is cyclic); topsort

10、:=false; end; End;,拓扑排序应用,字母排序 给定的一组字母，并在该组字母上定义偏序关系，确定该组字母能否按此偏序关系升序排序。,例如，有序序列A, B, C, D表示A B, B C and C D.在该问题中，给出一形如A B的关系集，并要求确定该序列是否有序。,如果有序，输出这个序列，并输出是通过前多少关系 得出的（即使之后的关系引出矛盾也不必理会）。如 果存在矛盾，则输出前多少项出现的矛盾的。,具体思路： 每输入一组偏序关系进行一次拓扑排序。 如果存在回路，输出矛盾。 在不存在回路的基础上，判断每次入度为0的点是否唯一，只有保证每次只有一个点入度为0，才能保证最终的序列唯一。,Input 4 6 /n=4表示字母数,2n26, m=6表示形如AB的偏序关 系数 AB /第1个偏序关系 AC BC CD BD AB /第6个偏序关