图及有向图的应用

《图及有向图的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章图及有向图的应用基本定义与术语图的存储结构图的存储结构单源最短路径问题顶点对之间最短路径拓扑排序关键路径小结4.1基本定义与术语基本定义：图的二元组定义：图G由两个集合V和E组成，记为：G=(V,E)其中：V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集有向图还是无向图，顶点数n、边数e和度数之间有如下关系：其中：n为图中的顶点数，e为图中的边数，D(Vi)为图中的第i顶点的度数基本术语：1.路径（Path）在无向图G中，如果存在一个顶点序列vp,vi1,vi2,…,vim,vq，使得(vp,vi1)，(vi1,vi2

2、)，…，(vim,vq)都属于E(G)，则称顶点vp到vq存在一条路径（Path）2.简单路径如果一条路径上除vp和vq外，其余顶点均不相同，则称此路径为一条简单路径（这里vp和vq可以相同也可以不同）简单回路起点和终点都相同的简单路径称为简单回路（Cycle）。有根图和图的根在一个有向图中，如果存在一个顶点v，从v可以到达图中其他所有顶点，则称此有向图为有根图，其中v称作图的根。连通图和连通分量在无向图中，如果从顶点V到顶点V′有路径，则称V和V′是连通的。如果对于图中的任意两个顶点Vi和Vj都是连通的，则称G为连通图强连通图和强连

3、通分量在有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。有向图的极大强连通子图称为G的强连通分量。欧拉图如果图中存在一条通过图中每条边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图称为欧拉图8.哈密顿图若图G中存在一条通过图中所有顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图4.2图的存储结构4.2.1图的邻接矩阵表示法1.图的邻接矩阵表示法在图的邻接矩阵表示法中，用一个顺序表来存储顶点信息，用邻接矩阵来表示顶点间的相

4、邻关系。2.邻接矩阵（AdacencyMatrix）设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是一个n阶方阵：4.2.2邻接表表示法4.2.2邻接表表示法图的邻接表表示法类似于树的孩子链表表示法邻接表的类型定义如下：#defineMaxVerNum100//最大顶点数为100typedefstructnode{//边表结点intadjvex;//邻接点域structnode*next;//链域//若要表示边上的权，则应增加一个数据域}EdgeNode;typedefstructvnode{//顶点表结点VertexTypeve

5、rtex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;图中当前顶点数和边数}ALGraph;//对于简单的应用，无须定义此类型，可直接使用AdjList类型4.3图的遍历图的遍历基本方法有两种：深度优先搜索和广度优先搜索，这两种方法都适用于有向图和无向图的遍历4.3.1深度优先搜索特点：尽可能先对纵深方向进

6、行搜索。基本思想是：以图中某个顶点v1为出发点，先访问v1，然后选一个v1的邻接点v2，以v2为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。搜索过程：4.3.2广度优先搜索特点：尽可能优先对横向搜索基本思想是：从图中某个顶点v1出发，访问了v1之后依次访问v1的所有邻接点；然后分别从这些邻接点出发按深度优先搜索遍历图的其他顶点，直至所有顶点都被访问到广度优先搜索的过程：4.4单源最短路径问题单源最短路径问题是：给定带权有向图G=(V,E)和源点s∈V，找出从源点s到V中其他各顶点的最短路径迪杰斯特拉（Dijkstra）

7、算法求单源最短路径Dijkstra算法如下所示：Dijkstra(G,D,s){//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度//以下是初始化操作S={s};D[s]=0;//设置初始的红点集及最短距离for(alli∈V-S)do//对蓝点集中每个顶点iD[i]=G[s][i];//设置i初始的估计距离为w//以下是扩充红点集for(i=0;i

8、)return;//蓝点集中所有蓝点的估计距离均为∞时，表示这些顶点的最短路径不存在S=S∪{k};//将蓝点k涂红后扩充到红点集for(allj∈V-S)do//调整剩余蓝点的估计距离if(D[j]>D[k]+G[k]