图的基本算法

《图的基本算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的基本算法www.themegallery.comCompanyLogo图的一些基本概念及其表示Contents拓扑排序和欧拉回路问题最小生成树和单源最短路问题二分图匹配1234CompanyLogo定义与术语图：二元组称为图(graph)。V为结点(node)点(vertex)集。E为中结点之间的边的集合。子图：什么是子图如果有两个图G和G’，G’的顶点集是G的顶点集的子集，且G’的边集点对(u,v)称为边(edge)或称弧(arc)，其中u,v属于V，称u,v是相邻的(adjacent

2、)，称u,v与边相关联(incident)。连通图：如果图中任意一对顶点都有路径存在，则称该图为连通的CompanyLogo定义与术语若边的点对(u,v)有序则称为有向(directed)边，其中u称为头(head)，v称为尾(tail)。所形成的图称有向图(directedgraph)。为对于u来说是出边(outgoingarc)；对于v来说是入边(incomingarc)。反之，若边的点对无序则称为无向(undirected)边，所形成的图称无向图(undirectedgraph)。Company

3、Logo定义与术语度(degree):一个顶点的度是指与该边相关联的边的条数，顶点v的度记作deg(v)。无向图：有向图：入度(indegree):在有向图中，一个顶点v的入度是指与该边相关联的入边(即边的尾是v)的条数。出度(outdegree)：在有向图中，一个顶点的出度是指与该边相关联的出边(即边的头是v)的条数。路径：如果从一个顶点v1出发，沿着一些边依次经过一些定点v2,v3……,vn,则称顶点序列(v1,v2,…..,vn)为从顶点v1到vn的路径。回路：如果一条路径上第一个顶点和最后一个

4、顶点是相同的，则称这样的路径为回路或环。CompanyLogo图的表示要表示一个图G=(V,E),有两种标准的方法，即邻接表和邻接矩阵。这两种方法即可以用于有向图，也可以用于无向图。用邻接表记录图StructEdge{intdest;//记录目的地intvalue;//边的权值Edge*link;//记录链表的下一个元素};Edge*edge=newEdge[n];//申请空间for(inti=0;i>u>>v)//(u,v)表

5、示一条边{L=newEdge;L->dest=v;//填写目的地L->link=edge[u];//用新建的这条边指向顶点u指向的链表edge[u]=L;//再把L赋给edge[u]}www.themegallery.comCompanyLogo遍历邻接表for(inti=0;idest<link;//取链表的下一个元素}}ww

6、w.themegallery.comCompanyLogowww.themegallery.comCompanyLogoDFS，BFS拓扑排序强连通分支欧拉路径和回路最小生成树最短路径哈密顿回路(NP)差分约束系统网络流二分图匹配图论涉及到的问题和算法www.themegallery.comCompanyLogo今天要讲的问题最小生成树最短路算法拓扑排序欧拉回路二分图的匹配拓扑排序拓扑排序是对有向无回路图(DAG)顶点的一种排序，它使得如果存在u,v的有向路径，那么满足序中u在v前。拓扑排序就是由一种

7、偏序(particalorder)得到一个全序(称为拓扑有序(topologicalorder))。偏序是满足自反性，反对称性，传递性的序。一个图的拓扑排序得到的结果可以看成是图中所有顶点沿水平线排列而成的序列，而且所有的有向边均是从左指向右在有向无回路图用于说明事件发生的先后顺序拓扑排序可以给出一个满足时间先后的顺序www.themegallery.comCompanyLogo陈熙大牛穿衣服的例子www.themegallery.comCompanyLogo拓扑排序算法描述拓扑排序的思路很简单，就是

8、每次任意找一个入度为0的点输出，并把这个点以及与这个点相关的边删除。实际算法中，用一个队列实现。算法：1.把所有入度=0的点入队Q。2.若队Q非空，则点u出队，输出u；否则转4。3.把所有与点u相关的边(u,v)删除，若此过程中有点v的入度变为0，则把v入队Q，转2。4.若出队点数