图算法基础知识精.ppt

《图算法基础知识精.ppt》由会员分享，可在线阅读，更多相关《图算法基础知识精.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图算法基础知识第1页，本讲稿共29页图图图图 G=(V,E)V=顶点的非空有限集顶点的非空有限集E=边集边集=V V的子集，的子集，V中顶点对，边的有中顶点对，边的有限集。限集。|E|=O(|V|2)简单图简单图(Sample Graph)任意两个顶点最多只有一条边，且每个点都没有连任意两个顶点最多只有一条边，且每个点都没有连接到自身的边。接到自身的边。完全图完全图(Complete Grapth)若有若有n n个顶点的无向图个顶点的无向图n(n-1)/2 2条边，则此图为完全图。条边，则此图为完全图。第2页，本讲稿共29页图的扩展图的扩展扩展扩展:连通图连通图（connected graph

2、）从图中每一顶点都有到其它顶点的从图中每一顶点都有到其它顶点的路径路径 。无向图无向图（undirected graph）:边边(u,v)=边边(v,u)有向图有向图（directed graph）:(u,v)表示从顶点表示从顶点u u 到顶点到顶点 v v的一条有向边的一条有向边,记为记为 u uv v一个不含有环的有向图称为无环有向图一个不含有环的有向图称为无环有向图(Directed acyclic graphs,DAG）。加权图加权图（weighted graph）图中不是边就是顶点与权关联，例图中不是边就是顶点与权关联，例如：公路交通图，边以距离如：公路交通图，边以距离w为权。为权。

3、第3页，本讲稿共29页图图通常用边数通常用边数|E|E|和顶点数和顶点数|V|V|描述运行时间描述运行时间。无向图中无向图中 0|E|V|(|V|-1)/20|E|V|(|V|-1)/2有向图中有向图中 0|E|V|(|V|-1)0|E|V|(|V|-1)若若|E|V|2，图是稠密的图是稠密的 dense若若|E|V|，图是稀疏的图是稀疏的 sparse对稠密图和稀疏图使用不同的数据结构对稠密图和稀疏图使用不同的数据结构第4页，本讲稿共29页图的表示图的表示假设假设 V=1,2,n邻接矩阵（邻接矩阵（adjacency matrix）将图表示成一个将图表示成一个 n x n 矩阵矩阵 A:Ai

4、,j=1 若边若边(i,j)E (或边的权或边的权wij)=0 若边若边(i,j)E第5页，本讲稿共29页图:邻接矩阵Example:1243A123410110200103000040010有向图有向图 非对称矩阵非对称矩阵第6页，本讲稿共29页图:邻接矩阵Example:1243adbcA1234123?4第7页，本讲稿共29页图:邻接矩阵Example:1243adbcA123410ad0200b030000400c0第8页，本讲稿共29页图:邻接矩阵Example:12435143A123410350200103000040040第9页，本讲稿共29页图:邻接矩阵Example:124

5、3adbcA123410ad02a0b03db0c400c0无向图 对称矩阵第10页，本讲稿共29页图图:邻接矩阵邻接矩阵邻接矩阵的实现邻接矩阵的实现 const maxlength=100 最大顶点数最大顶点数type graph=array1.maxlength,1.maxlength of integer;二维数组二维数组第11页，本讲稿共29页输入和查看一遍邻接矩阵需要多少时间？输入和查看一遍邻接矩阵需要多少时间？答答:O(|V|2)存储一个邻接矩阵需要多少存储空间？存储一个邻接矩阵需要多少存储空间？答答:O(|V|2)稀疏图稀疏图（|E|E|V|V|或或|E|V|),|E|V|),邻

6、接矩阵是稀邻接矩阵是稀疏矩阵，浪费空间，因此采用疏矩阵，浪费空间，因此采用邻接表邻接表更有效。更有效。图图:邻接矩阵邻接矩阵第12页，本讲稿共29页图图:邻接表邻接表邻接表邻接表:对每个顶点对每个顶点 v V,将将v的所有邻接的所有邻接点存放在一个列表中。点存放在一个列表中。Example:Adj1=2,3Adj2=3Adj3=Adj4=31243第13页，本讲稿共29页1243图图:邻接表邻接表1 12 23 3nilnil2 23 3nilnil3 3nilnil4 43 3nilnil第14页，本讲稿共29页邻接表的实现邻接表的实现Type pointer=adjnode adjnode

7、=record adjvex:integer;该点在图中的位置该点在图中的位置 next:pointer;指向下一个顶点的指针指向下一个顶点的指针 infor:;与边有关的信息，如权值与边有关的信息，如权值w Adjlist=array1.maxlength of pointer;图图:邻接表邻接表第15页，本讲稿共29页 无环有向图的拓扑排序无环有向图的拓扑排序 Directed acyclic graphs(DAG)topological sort DAG:不含回路的有向图称为无环有向图。不含回路的有向图称为无环有向图。检查有向图中是否存在回路的方法之一，是检查有向图中是否存在回路的方法之

8、一，是对有向图进行对有向图进行拓扑排序拓扑排序。如果有向图如果有向图G有一个有一个拓扑排序拓扑排序,则则G是一个有向是一个有向无环图无环图.反之反之,任一有向无环图必可进行任一有向无环图必可进行拓扑排序拓扑排序。第16页，本讲稿共29页何谓何谓“拓扑排序拓扑排序”？按照有向图给出的次序关系，将图中按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上有限定次序关系的顶点，则可以人为加上任意的次序关系。任意的次序关系。由此所得顶点的线性序列称之为由此所得顶点的线性序列称之为拓扑拓扑有序序列有序序列第17页，本讲

9、稿共29页例如：对于下列有向图例如：对于下列有向图BDAC可求得可求得拓扑有序序列拓扑有序序列：A B C D 或或 A C B D第18页，本讲稿共29页BDAC反之，对于下列有向图反之，对于下列有向图不能求得它的拓扑有序序列。不能求得它的拓扑有序序列。因为图中存在一个回路因为图中存在一个回路 B,C,D第19页，本讲稿共29页如何进行拓扑排序？如何进行拓扑排序？一、从有向图中选取一个没有前驱一、从有向图中选取一个没有前驱 的顶点，并输出之的顶点，并输出之;重复上述两步，直至图空，或者图重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。不空但找不到无前驱的顶点为止。二、从有向图中删

10、去此顶点以及所二、从有向图中删去此顶点以及所 有以它为尾的弧有以它为尾的弧;第20页，本讲稿共29页abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 没有前驱的顶点没有前驱的顶点 入度为零的顶点入度为零的顶点删除顶点及以它为尾的弧删除顶点及以它为尾的弧 弧头顶点的入度减弧头顶点的入度减1第21页，本讲稿共29页拓扑排序算法拓扑排序算法Function topsort:boolean;P140 var i,count:integer;wadj:Arr3;/用来表示图的邻接表表头数组用来表示图的邻接表表头数组 indeg:Arr1;/一维

11、数组，存储每个顶点的入度一维数组，存储每个顶点的入度 p:wpointer;/链表，邻接表链表，邻接表 q:queue;/队列队列q q保存入度为零且未被排序的顶点保存入度为零且未被排序的顶点 begin /算法依次对算法依次对q q的出队元素进行编号的出队元素进行编号 topsort:=true;count:=0;makenull(q);/清空队列清空队列q fillchar(indeg,sizeof(indeg),0);/数组数组indegindeg存储每个顶存储每个顶点入度点入度第22页，本讲稿共29页/通过遍历邻接表，计算所有顶点的入度通过遍历邻接表，计算所有顶点的入度For i:=1

12、 to n do begin p:=wadji;/顶点顶点i的邻接表的第一个邻接点的邻接表的第一个邻接点 while pnil do /依次为顶点依次为顶点i的所有邻接点入度加的所有邻接点入度加1 begin inc(indegp.v);p:=p.next;end;End;第23页，本讲稿共29页/入度为入度为0的顶点加入队列的顶点加入队列qFor i:=1 to n do if indegi=0 then enqueue(i,q);/入队入队/队列队列q q的队首顶点出队，与该顶点邻接的顶点的出度减的队首顶点出队，与该顶点邻接的顶点的出度减1 1While not empty(q)do be

13、gin 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第24页，本讲稿共29页/入度为入度为0的顶点数小于的顶点数小于n时，存在环；时，存在环；否则图不存在环，且可进行拓扑排序，否则图不存在环，且可进行拓扑排序，ord数组存储的就是

14、排序后的序号数组存储的就是排序后的序号If countn then begin writeln(graph is cyclic);topsort:=false;end;End;第25页，本讲稿共29页拓扑排序应用字母排序给定的一组字母，并在该组字母上定义偏序给定的一组字母，并在该组字母上定义偏序关系关系，确定该组字母能否按此偏序关系升，确定该组字母能否按此偏序关系升序排序。序排序。例如，有序序列例如，有序序列A,B,C,DA,B,C,D表示表示A B,B C and C D.A B,B C and C D.在在该问题中，给出一形如该问题中，给出一形如A BA B的关系集，并要求确定该序的关系集

15、，并要求确定该序列是否有序。列是否有序。如果有序，输出这个序列，并输出是通过前多少关系如果有序，输出这个序列，并输出是通过前多少关系得出的（即使之后的关系引出矛盾也不必理会）。如得出的（即使之后的关系引出矛盾也不必理会）。如果存在矛盾，则输出前多少项出现的矛盾的。果存在矛盾，则输出前多少项出现的矛盾的。第26页，本讲稿共29页具体思路具体思路：每输入一组偏序关系进行一次拓扑排序。每输入一组偏序关系进行一次拓扑排序。如果存在回路，输出矛盾。如果存在回路，输出矛盾。在不存在回路的基础上，判断每次入度为在不存在回路的基础上，判断每次入度为0 0的点是的点是否唯一，只有保证每次只有一个点入度为否唯一，

16、只有保证每次只有一个点入度为0 0，才能保证，才能保证最终的序列唯一。最终的序列唯一。第27页，本讲稿共29页Input4 6 /n=4表示字母数表示字母数,2n26,m=6表示形如表示形如AB的偏序关的偏序关 系数系数 AB /第第1个偏序关系个偏序关系ACBCCDBDAB /第第6个偏序关系个偏序关系 Output 4个关系后确定的有序序列：个关系后确定的有序序列：ABCD.第28页，本讲稿共29页Input3 2 /n=3表示字母数表示字母数2n26,m表示形如表示形如AB的的 偏序关系数偏序关系数 AB /第第1个偏序关系个偏序关系BA /第第2个偏序关系个偏序关系 Output Inconsistency found after 2 relations.第29页，本讲稿共29页