图算法基础知识ppt课件.ppt

《图算法基础知识ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图算法（一）GraphAlgorithms图图G=(V,E)V=顶点的非空有限集E=边集=VV的子集，V中顶点对，边的有限集。

2、E

3、=O(

4、V

5、2)简单图(SampleGraph)任意两个顶点最多只有一条边，且每个点都没有连接到自身的边。完全图(CompleteGrapth)若有n个顶点的无向图n(n-1)/2条边，则此图为完全图。图的扩展扩展:连通图（connectedgraph）从图中每一顶点都有到其它顶点的路径。无向图（undirectedgraph）:边(u,v)=边(v,u)有向图（directedgraph）:(u,v)表示从顶点u到顶点v的一

6、条有向边,记为uv一个不含有环的有向图称为无环有向图(Directedacyclicgraphs,DAG）。加权图（weightedgraph）图中不是边就是顶点与权关联，例如：公路交通图，边以距离w为权。图通常用边数

7、E

8、和顶点数

9、V

10、描述运行时间。无向图中0≤

11、E

12、≤

13、V

14、(

15、V

16、-1)/2有向图中0≤

17、E

18、≤

19、V

20、(

21、V

22、-1)若

23、E

24、

25、V

26、2，图是稠密的dense若

27、E

28、

29、V

30、，图是稀疏的sparse对稠密图和稀疏图使用不同的数据结构图的表示假设V={1,2,…,n}邻接矩阵（adjacencymatrix）将图表示成一个nxn矩阵A:A[i,

31、j]=1若边(i,j)E(或边的权wij)=0若边(i,j)E图:邻接矩阵Example:1243A123410110200103000040010有向图非对称矩阵图:邻接矩阵Example:1243adbcA1234123??4图:邻接矩阵Example:1243adbcA123410ad0200b030000400c0图:邻接矩阵Example:12435143A123410350200103000040040图:邻接矩阵Example:1243adbcA123410ad02a0b03db0c400c0无向图对称矩阵图:邻接矩阵邻接矩阵的实现cons

32、tmaxlength=100{最大顶点数}typegraph=array[1..maxlength,1..maxlength]ofinteger;二维数组输入和查看一遍邻接矩阵需要多少时间？答:O(

33、V

34、2)存储一个邻接矩阵需要多少存储空间？答:O(

35、V

36、2)稀疏图（

37、E

38、

39、V

40、或

41、E

42、<<

43、V

44、),邻接矩阵是稀疏矩阵，浪费空间，因此采用邻接表更有效。图:邻接矩阵图:邻接表邻接表:对每个顶点vV,将v的所有邻接点存放在一个列表中。Example:Adj[1]={2,3}Adj[2]={3}Adj[3]={}Adj[4]={3}12431243图:邻接表1

45、23nil23nil3nil43nil邻接表的实现Typepointer=↑adjnodeadjnode=recordadjvex:integer;{该点在图中的位置}next:pointer;{指向下一个顶点的指针}infor:…;{与边有关的信息，如权值w}Adjlist=array[1..maxlength]ofpointer;图:邻接表无环有向图的拓扑排序Directedacyclicgraphs(DAG)topologicalsortDAG:不含回路的有向图称为无环有向图。检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。如果有向图G有一

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

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

48、l(q);//清空队列qfillchar(indeg