《图的定义和基本术语(精)》由会员分享，可在线阅读，更多相关《图的定义和基本术语(精)（13页珍藏版）》请在金锄头文库上搜索。
1、第 13 页图的遍历算法及其应用图 程序设计算法篇 目 录第6章 图26.1 图的定义和基本术语26.2 图的存储和创建36.2.1 图的存储表示36.2.2 图的创建66.3 图的遍历66.3.1 深度优先搜索66.3.2 广度优先搜索76.4 遍历算法的应用86.4.1 应用问题概述86.4.2 求一条包含图中所有顶点的简单路径96.4.3 求距v0最短路径长度最长的一个顶点106.5 图的连通性问题116.5.1 无向图的连通分量和生成树116.5.2 最小生成树136.6 有向无环图及其应用13第6章 图6.1 图的定义和基本术语1、 图的特征任意两个数据元素之间都可能相关。结点之间的
2、关系是多对多的。G = (V,E)2、 基本术语结点：顶点结点间的关系：无向图：边(v,w)，v与w互为邻接点，边(v,w)依附于顶点v,w，边(v,w)和顶点v,w相关联v的度：和v相关联的边的数目。有向图：弧，v弧尾，w弧头，顶点v邻接到顶点w，顶点w邻接自顶点v，弧和顶点v,w相关联。v的入度：以v为头的弧的数目；v的出度：以v为尾的弧的数目；v的度：v的入度与出度之和。路径、回路(环)、简单路径、简单回路(简单环)连通性：若从顶点v到顶点v有路径，则称v和v是连通的图的规模：顶点数n、边(弧)数e、顶点的度(有向图：入度/出度)子图：G= (V,E), G = (V,E)，若VV且E
3、E，则称G是G的子图。图的分类：1）关系的方向性（无向/有向）、关系上是否有附加的数权(图/网)有向图、无向图、有向网、无向网2）边(弧)数：完全图(边数=n(n-1)/2的无向图)、有向完全图(弧数=n(n-1)的有向图)稀疏图(enlogn)3）连通性：无向图：连通图(任意两顶点都是连通的)、连通分量(极大连通子图)、生成树(极小连通子图)、生成森林有向图：强/弱连通图、强连通分量、生成树(极小连通子图)、生成森林3、 抽象数据类型定义ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R = VRVR = |v,wV且P(v,w)，表示从v到w的弧，谓
4、词P(v,w) 定义了弧的意义或信息 基本操作：CreateGraph(&G, V, VR)初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图GDestroyGraph(&G)初始条件：图G存在操作结果：销毁图GLocateVex(G,u)初始条件：图G已存在，u和G中顶点有相同特征操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回其它信息GetVex(G, v)初始条件：图G存在，v是G中某个顶点操作结果：返回v的值PutVex(&G, v, value)初始条件：图G存在，v是G中某个顶点操作结果：对v赋值valueFirstAdjVex(G, v)初始
5、条件：图G存在，v是G中某个顶点操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”NextAdjVex(G, v, w)初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点操作结果：返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”InsertVex(&G, v)初始条件：图G存在，v和G中顶点有相同特征操作结果：在图中增添新顶点vDeleteVex(&G, v)初始条件：图G存在，v是G中某个顶点操作结果：删除G中顶点v及其相关的弧InsertArc(&G, v, w)初始条件：图G存在，v和w是G中两个顶点操作结果：在图G中增添弧，若G是无
6、向的，则还应增添对称弧DeleteArc(&G, v, w)初始条件：图G存在，v和w是G中两个顶点操作结果：删除G中的弧，若G是无向的，则还应删除对称弧DFSTraverse(G, v, visit()初始条件：图G存在，v是G中某个顶点，visit是对顶点的应用函数操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败BFSTraverse(G, v, visit()初始条件：图G存在，v是G中某个顶点，visit是对顶点的应用函数操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数visit()一次且至多一次。一旦
7、visit()失败，则操作失败ADT Graph6.2 图的存储和创建6.2.1 图的存储表示1、 图的存储表示分析顶点之间的关系是多对多的(m:n)，由于m和n都是不定的，无法给出一个这种多对多的关系向线性关系的映射公式图中的关系不能通过顺序映像(即通过顶点之间的存储位置反映顶点之间的逻辑关系)反映；必须另外引入存储空间反映顶点之间的邻接关系。图的存储结构：1）顶点信息；2）边(弧)信息；3）整体信息：顶点数、边(弧)数、图的种类(有向图、无向图、有向网、无向网)顶点集的存储：图的应用中，顶点集动态变化的几率十分小顶点集可以采用顺序表存储，按预先估计的最大顶点数分配空间（顺序表和链表：若数据
8、元素集是静态的，采用顺序表要好(随机存取)；若数据元素集是动态的，则采用链表要好(动态分配与释放)）#defineMAX_VERTEX_NUM20/* 最大顶点数*/注意：顺序表与顺序映像之间的区别关系集的存储：在顶点确定的情况下，边或弧的数目也是不定的，且在实际应用中，可能会改变图中的顶点之间的关系。邻接矩阵表示法：矩阵中的第i行第j列的元素反映图中第i个顶点到第j个顶点是否存在弧，若存在其附加的信息是什么。邻接表表示法：将每一顶点的邻接点位置串成一个链，称为邻接表。对于有向图/网来说，该邻接表反映的是顶点的出边表。typedefenumDG, DN, AG, AN GraphKind;/*
9、有向图，有向网，无向图，无向网*/2、 邻接矩阵表示法（数组表示法）无向图/网：对称矩阵有向图/网：非对称矩阵图：邻接关系用1/0表示网：邻接关系需要进一步反映权值，用INFINITY表示无穷大，反映顶点之间无邻接关系#defineINT_MAX32767/* 最大整数*/#defineINFINITYINT_MAX1) 邻接矩阵typedef struct ArcCellintadj;/*顶点间关系，无权图：0-不相邻，1-相邻有权图，权值，INFINITY-不相邻*/InfoType*info;/* 该弧相关信息的指针*/ArcCell, AdjMatrixMAX_VERTEX_NUMMA
10、X_VERTEX_NUM; 2) 图的整体结构typedef struct charvexsMAX_VERTEX_NUM; /* 有效的顶点下标从0开始 */AdjMatrixarcs;/* 关系集 */intvexnum, arcnum;/* 顶点数、边/弧数 */GraphKindkind;/* 图的种类*/MGraph;3、 邻接表表示法无向图/网：边表，表结点的个数为边数的两倍有向图/网：出边表，表结点的个数为弧数1) 邻接表的表结点typedef struct ArcNodeintadjvex;/* 弧所指向的顶点的位置*/struct ArcNode*nextarc;/* 指向下一
11、条弧的指针*/InfoType*info;ArcNode;2) 邻接表的头结点typedef struct VNodechardata;/* 顶点信息*/ArcNode*firstarc;/*邻接表指针*/VNode, AdjListMAX_VERTEX_NUM;3) 图的整体结构typedef struct AdjListvertices;intvexnum, arcnum;GraphKindkind;ALGraph;4、 邻接矩阵与邻接表的对比假设图为G，顶点数为n，边/弧数为e。A邻接矩阵B邻接表存储空间O(n+n2)O(n+e)图的创建算法T1(n)=O(e+n2)或T2(n)=O(e
12、*n+n2)T1(n)=O(n+e)或T2(n)=O(e*n)T1(n)是指在输入边/弧时，输入的顶点信息为顶点的编号；而T2(n)则指在输入边/弧时，输入的为顶点本身的信息，此时需要查找顶点在图中的位置无向图中求第i顶点的度(第i行之和)或(第i列之和)G.verticesi.firstarc所指向的邻接表包含的结点个数无向网中求第i顶点的度第i行/列中adj值不为INFINITY的元素个数有向图中求第i顶点的入/出度入度：(第i列)出度：(第i行)入度：扫描各顶点的邻接表，统计表结点的adjvex为i的表结点个数T(n)=O(n+e)出度：G.verticesi.firstarc所指向的邻
13、接表包含的结点个数有向网中求第i顶点的入/出度入度：第i列中adj值不为INFINITY的元素个数出度：第i行中adj值不为INFINITY的元素个数统计边/弧数无向图：)无向网：G.arcs中adj值不为INFINITY的元素个数的一半有向图：有向网：G.arcs中adj值不为INFINITY的元素个数无向图/网：图中表结点数目的一半有向图/网：图中表结点的数目结论：邻接矩阵适于稠密图，邻接表适于稀疏图；邻接表求有向图的顶点的入度不方便，要遍历全部的邻接表。6.2.2 图的创建基本过程：1） 输入图的类型，根据类型选择相应的创建算法2） 输入图的顶点数，边/弧数3） 输入并存储顶点信息4）
14、输入边/弧所关联的顶点对，将边或弧的信息存储到邻接矩阵/邻接表中图的存储结构不同、图的类型不同，都会影响创建算法的实现细节；但是，图的总体创建流程是一致的（如上）。示例：用邻接矩阵表示法构造有向网GStatusCreateMDG(MGraph &G)/* 步骤2：输入图的顶点数、边/弧数*/scanf(&G.vexnum, &G.arcnum, &IncInfo);/* IncInfo为0则各弧不含其它信息 */* 步骤3：输入并存储顶点信息*/for ( i = 0; i G.vexnum ; i+)scanf ( &G.vexsi );/* 步骤4：输入并存储边/弧信息*/for ( i = 0; i G.vexnum ; i+)/* 邻接矩阵初始化*/for ( j = 0; j G.vexnum ; j+)G.arcsij = INFINITY, NULL;f
