数据结构第9章图

《数据结构第9章图》由会员分享，可在线阅读，更多相关《数据结构第9章图（99页珍藏版）》请在金锄头文库上搜索。

1、9.1 图的基本概念第9章 图9.2 图的存储结构9.3 图的遍历9.4 生成树和最小生成树9.5 最短路径9.6 拓扑排序9.7 AOE网与关键路径本章小结9.1 图的基本概念9.1.1 图的定义 图(Graph)G由两个集合V(Vertex)和E(Edge)组成 ，记为G=(V,E)，其中V是顶点的有限集合，记为 V(G)，E是连接V中两个不同顶点(顶点对)的边的有 限集合，记为E(G)。在图G中，如果代表边的顶点对是无序的，则称 G为无向图，无向图中代表边的无序顶点对通常用圆 括号括起来，用以表示一条无向边。 如果表示边的顶点对是有序的，则称G为有向图, 在有向图中代表边的顶点对通常用尖

2、括号括起来 。9.1.2 图的基本术语端点和邻接点 在一个无向图中，若存 在一条边(vi,vj)，则称vi和vj 为此边的两个端点，并称它 们互为邻接点。在一个有向图中，若存 在一条边，则称此边 是顶点vi的一条出边，同时 也是顶点vj的一条入边；称 vi和vj分别为此边的起始端 点(简称为起点)和终止端点( 简称终点)；称vi和vj互为邻 接点。13024(a)13024(b)2. 顶点的度、入度和出度在无向图中，顶点所具有的 边的数目称为该顶点的度。在有向图中，以顶点vi为终 点的入边的数目，称为该顶点的 入度。以顶点vi为始点的出边的 数目，称为该顶点的出度。一个 顶点的入度与出度的和为

3、该顶点 的度。若一个图中有n个顶点和e条 边，每个顶点的度为di(1in),则 有：13024(a)13024(b)3. 完全图若无向图中的每两个顶 点之间都存在着一条边，有 向图中的每两个顶点之间都 存在着方向相反的两条边， 则称此图为完全图。完全无向图包含有n(n- 1)/2 条边，完全有向图包含 有n(n-1)条边。图(a)所示的 图是完全无向图。图(b)所示 的图是一个完全有向图。 1023(b)1023(a)4. 稠密图、稀疏图当一个图接近完全图 时,则称为稠密图。相反， 当一个图含有较少的边数( 即当e， ，属于E(G) 。路径长度是指一条路径上经过 的边的数目。若一条路径上除开始

4、 点和结束点可以相同外，其余顶点 均不相同，则称此路径为简单路径 。例如，有图中，(v0,v2,v1)就是一 条简单路径，其长度为2。10237. 回路或环若一条路径上的开 始点与结束点为同一个 顶点，则此路径被称为 回路或环。开始点与结 束点相同的简单路径被 称为简单回路或简单环 。例如,右图中， (v0,v2,v1,v0)就是一条简 单回路，其长度为3。10239. 连通、连通图和连通分量在无向图G中，若从顶 点vi到顶点vj有路径，则称vi 和vj是连通的。 若图G中任意两个顶点 都连通，则称G为连通图， 否则称为非连通图。无向图G中的极大连通 子图称为G的连通分量。显 然，任何连通图的

5、连通分量 只有一个，即本身，而非连 通图有多个连通分量。1023102(b)(a)10. 权和网图中每一条边都可以附有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图，也称作网。例9.1 有n个顶点的有向强连通图最多需要多少条边？最少需要多 少条边？ 答：有n个顶点的有向强连通图最多有n(n-1)条边(构成一个有向完全图的情况)；最少有n条边(n个顶点依次首尾相接构成一个环的情况)。 9.2 图的存储结构 9.2.1 邻接矩阵存储方法邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n(n0)个顶点的图，顶点的顺序

6、依次为(v0,v1,vn-1)，则G的邻接矩阵A是n阶方阵，其定义如下：(1)如果G是无向图，则：Aij=1：若(vi,vj)E(G) 0:其他(2)如果G是有向图，则：Aij=1：若E(G) 0:其他(3)如果G是带权无向图，则：Aij= wij ：若vivj且(vi,vj)E(G) :其他(4)如果G是带权有向图，则：Aij= wij ：若vivj且E(G) :其他1302413024(a)(b)邻接矩阵的特点如下：(1)图的邻接矩阵表示是惟一的。(2)无向图的邻接矩阵一定是一个对称矩阵。因 此，按照压缩存储的思想，在具体存放邻接矩阵时 只需存放上(或下)三角形阵的元素即可。(3)不带权的

7、有向图的邻接矩阵一般来说是一个 稀疏矩阵，因此，当图的顶点较多时，可以采用三 元组表的方法存储邻接矩阵。(4)对于无向图,邻接矩阵的第i行(或第i列)非零元 素(或非元素)的个数正好是第i个顶点vi的度。(5)对于有向图，邻接矩阵的第i行(或第i列)非零元素(或非元素)的个数正好是第i个顶点vi的出度(或入度)。(6)用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。邻接矩阵的数据类型定义如下： #define MAXV typedef struct int no

8、;/*顶点编号*/InfoType info;/*顶点其他信息*/ VertexType;/*顶点类型*/ typedef struct /*图的定义*/ int edgesMAXVMAXV; /*邻接矩阵*/int vexnum,arcnum; /*顶点数,弧数*/VertexType vexsMAXV;/*存放顶点信息*/ MGraph;9.2.2 邻接表存储方法图的邻接表存储方法是一种顺序分配与链式 分配相结合的存储方法。在邻接表中，对图中每 个顶点建立一个单链表,第i个单链表中的结点表示 依附于顶点vi的边(对有向图是以顶点vi为尾的弧) 。每个单链表上附设一个表头结点。表结点和表 头

9、结点的结构如下：弧（或边）结点ANode 顶点结点VNodeadjvexadjvexnextarcnextarcinfoinfodatadatafirstarcfirstarcadjvex指示与 顶点vi邻接的 点在图中的位 置存储顶 点vi的 名或其 他信息指示以顶点 vi为端点的 第一条边13024(a)012341 2 3 0 3 3 4 3 v0 v1v2v3 v4(b)13024(b)邻接表的特点如下：(1)邻接表表示不惟一。这是因为在每个顶点对应的 单链表中，各边结点的链接次序可以是任意的，取决 于建立邻接表的算法以及边的输入次序。(2)对于有n个顶点和e条边的无向图，其邻接表有n

10、 个顶点结点和2e个边结点。显然，在总的边数小于n(n -1)/2的情况下，邻接表比邻接矩阵要节省空间。(3)对于无向图，邻接表的顶点vi对应的第i个链表的 边结点数目正好是顶点vi的度。(4)对于有向图，邻接表的顶点vi对应的第i个链表的 边结点数目仅仅是vi的出度。其入度为邻接表中所有 adjvex域值为i的边结点数目。邻接表存储结构的定义如下： typedef struct ANode /*弧的结点结构类型*/ int adjvex; /*该弧的终点位置*/struct ANode *nextarc; /*指向下一条弧的指针*/InfoType info; /*该弧的相关信息*/ Arc

11、Node; typedef struct Vnode /*邻接表头结点的类型*/ Vertex data; /*顶点信息*/ArcNode *firstarc; /*指向第一条弧*/ VNode; typedef VNode AdjListMAXV;/*AdjList是邻接表类型*/ typedef struct AdjList adjlist; /*邻接表*/int n,e; /*图中顶点数n和边数e*/ ALGraph; /*图的类型*/例9.2 给定一个具有n个结点的无向图的邻接矩阵和邻接表。(1) 设计一个将邻接矩阵转换为邻接表的算法；(2) 设计一个将邻接表转换为邻接矩阵的算法；(3

12、) 分析上述两个算法的时间复杂度。解：(1)在邻接矩阵上查找值不为0的元素，找到这样的元素后创建一个表结点并在邻接表对应的单链 表中采用前插法插入该结点。算法如下：void MatToList(MGraph g,ALGraph * ArcNode *p; /*n为顶点数*/G=(ALGraph *)malloc(sizeof(ALGraph);for (i=0;iadjlisti.firstarc=NULL;for (i=0;i=0;j-)if (g.edgesij!=0) p=(ArcNode *)malloc(sizeof(ArcNode);/*创建结点*p*/p-adjvex=j;p-n

13、extarc=G-adjlisti.firstarc;/*将*p链到链表前*/G-adjlisti.firstarc=p;G-n=n;G-e=g.arcnum; (2)在邻接表上查找相邻结点，找到后修改相应邻接矩阵元素 的值。算法如下： void ListToMat(ALGraph *G,MGraph ArcNode *p;for (i=0;iadjlisti.firstarc;while (p!=NULL) g.edgesip-adjvex=1;p=p-nextarc;g.vexnum=n;g.arcnum=G-e; (3)上述两个算法的时间复杂度均为O(n2)。对于(2)的算法，若不计算给

14、aij赋初值0的双重for循环语句，其时间复杂度为O(n*e)，其中e为图的边数。9.3 图的遍历9.3.1 图的遍历的概念从给定图中任意指定的顶点(称为初始点)出发 ，按照某种搜索方法沿着图的边访问图中的所有顶 点，使每个顶点仅被访问一次，这个过程称为图的 遍历。如果给定图是连通的无向图或者是强连通的 有向图，则遍历过程一次就能完成，并可按访问的 先后顺序得到由该图所有顶点组成的一个序列。图的遍历方法有：l深度优先搜索法(DFS)；l广度优先搜索法(BFS)。 9.3.2 深度优先搜索遍历深度优先搜索遍历的过程是：从图中某个初始顶点v出发，首先访问初始顶点v，然后选择一个与顶点v相邻且没被访

15、问过的顶点w为初始顶点，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。显然，这个遍历过程是个递归过程。以邻接表为存储结构的深度优先搜索遍历算法如下(其中：v是初始顶点编号，visited 是一个全局数组，初始时所有元素均为0表示所有顶点尚未访问过)：void DFS(ALGraph *G,int v) ArcNode *p;visitedv=1; /*置已访问标记*/printf(“%d “,v); /*输出被访问顶点的编号*/p=G-adjlistv.firstarc; /*p指向顶点v的第一条弧的弧头结点*/while (p!=NULL) if (visitedp-adjvex=0) DFS(G,p-adjvex); /*若p-adjvex顶点未访问,递归访问它*/p=p-