(13)第六章 图及其存储结构

1、1第六 章 图定义、概念、存储结构、输入2图图(Graph)的的ADT定义：定义：图图是是n( n0 0 )个个结点的有限集结点的有限集合。在任意一个图中合。在任意一个图中任意两个结点之间都可能相关任意两个结点之间都可能相关。图。图的的ADT定义如下：定义如下：一、基本概念一、基本概念数据对象数据对象V： V是具有相同特性的数据元素的集合，并称为顶点集是具有相同特性的数据元素的集合，并称为顶点集合。合。数据关系数据关系R： R=E E=|v,wV , （或（或（v, w)表示从表示从v到到w的弧的弧 (或边）或边）,且有函数且有函数 P(v,w)定义了弧定义了弧上的信息或权值上的信息或权值基本

2、操作基本操作P： 详见详见 P127图的二元组表示：图的二元组表示：G=(V，E)E即为图中边或弧的集合。即为图中边或弧的集合。3图的有关术语：图的有关术语：一、基本概念一、基本概念 图中的数据元素称为图中的数据元素称为顶点；顶点； 有向图；有向图； 弧；弧； 弧头；弧头； 弧尾；弧尾； 无向图；无向图； 边；边； *定理定理：若用：若用e表示有向图或无向图中弧或边的条数，表示有向图或无向图中弧或边的条数，即即e=|E|,则有：则有： 在有向图中：在有向图中： 0en(n-1) 在无向图中：在无向图中： 0en(n-1)/2 具有具有n(n-1)/2条边的无向图称为条边的无向图称为无向无向完全

3、图：完全图： 具有具有n(n-1)条边的有向图称为条边的有向图称为有向完全图：有向完全图：abcd01234图的有关术语：图的有关术语：一、基本概念一、基本概念顶点的度；顶点的度； 有向图中顶点的度有向图中顶点的度是该顶点的是该顶点的入度入度与与出度出度之和之和。 无向图中顶点的度无向图中顶点的度是与该是与该顶点顶点相关联的边的条数相关联的边的条数。 子图：子图：对于对于G1=(V1,E1),G2=(V2,E2),若若V2 V1，E2 E1，则称，则称G2是是G1的子图。的子图。 回路（环）：回路（环）：若一条路径上的顶点均不相同则该路径称为若一条路径上的顶点均不相同则该路径称为简单路径简单路

4、径；除了除了第一顶点第一顶点和和终点终点相同外，路径上的其他顶点均不相同的路径相同外，路径上的其他顶点均不相同的路径称为称为简单回路简单回路或或简单环简单环。第一顶点第一顶点和和最后顶点最后顶点相同的路径叫相同的路径叫回路回路或环或环。abcd01235图的有关术语：图的有关术语：一、基本概念一、基本概念 无向图中任意两个顶点都是连通的，则该图为无向图中任意两个顶点都是连通的，则该图为连通图连通图。有向图中任何有序顶点对之间都有有向路径，则称该图是有向图中任何有序顶点对之间都有有向路径，则称该图是强连通的强连通的。无向图中最大的连通子图称为该图的。无向图中最大的连通子图称为该图的连通分量连通分

5、量；有向图中相应地称为有向图中相应地称为强连通分量强连通分量。abcd01236图的有关术语：图的有关术语：一、基本概念一、基本概念 一个连通无向图的一个连通无向图的生成树生成树是该图的一个极小连通子图，是该图的一个极小连通子图，它包含有该图的所有它包含有该图的所有n个顶点以及连接这个顶点以及连接这n个顶点的（个顶点的（n-1）条边。条边。 边或弧上带权值的图称为边或弧上带权值的图称为网网（分为（分为无向网无向网和和有向网有向网）。）。 一个无向图的所有生成树中，边上的权值之和最小的一个无向图的所有生成树中，边上的权值之和最小的生成树称为该图的生成树称为该图的最小生成树最小生成树或或最小代价生

6、成树最小代价生成树。abcdef65512564637图的有关术语：图的有关术语：一、基本概念一、基本概念图中顶点的图中顶点的“序号序号”及其邻接点的及其邻接点的“序号序号”： 由于图中顶点之间不存在全序关系，所以无法将图中由于图中顶点之间不存在全序关系，所以无法将图中顶点进行线性排序。但为了实现图的存储结构，我们必须顶点进行线性排序。但为了实现图的存储结构，我们必须给每个顶点附加一个人为规定的给每个顶点附加一个人为规定的“序号序号”。这个序号即称。这个序号即称为该为该顶点在图中的位置顶点在图中的位置。 对于任意一个顶点而言，若它有两个以上的邻接点，对于任意一个顶点而言，若它有两个以上的邻接点

7、，则它的邻接点也有所谓则它的邻接点也有所谓“第一个邻接点第一个邻接点”， “第二个邻第二个邻接点接点”，.，这个顺序也称为，这个顺序也称为邻接顺序邻接顺序。8一、基本概念一、基本概念图的遍历图的遍历：从图中某一顶点出发按一定规律沿着图中的边：从图中某一顶点出发按一定规律沿着图中的边或弧访问每一顶点一次且仅一次的操作称为对图的遍历。或弧访问每一顶点一次且仅一次的操作称为对图的遍历。 *图的遍历有两种方法：图的遍历有两种方法：深度优先遍历深度优先遍历和和广度优先遍历广度优先遍历 *若图是连通的或是强连通的，则遍历过程所经过的边若图是连通的或是强连通的，则遍历过程所经过的边（或弧）及所遍历的顶点就得

8、到图中的一棵（或弧）及所遍历的顶点就得到图中的一棵生成树生成树。 *对于非连通图而言，从某一连通分量中的某一顶点出对于非连通图而言，从某一连通分量中的某一顶点出发执行一次发执行一次“遍历遍历”算法可得该连通分量的生成树，该生算法可得该连通分量的生成树，该生成树是非连通图的一颗成树是非连通图的一颗生成子树生成子树；分别对各连通分量执行；分别对各连通分量执行一次一次“遍历遍历”算法可得到非连通图的算法可得到非连通图的生成森林生成森林。 9二、存储结构二、存储结构*思想思想： 用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系： 一个一维数组vexs: 存放各顶点的有关信息； 一个二维数组

9、arcs: 存放各条边或弧的有关信息Arcs : 一般情况下存放边或弧上的权值； 对于边或弧上无权值的图而言，边或弧上的权值 为1时表示该条弧或边的存在，若两顶点之间没有边或弧，则设置该条边或弧上的权值为0。10二、存储结构二、存储结构#define INFINITY 10000 / INFINITY用以表示用以表示#define MAX_VERTEX_NUM 20 /最大顶点数最大顶点数enum GraphKind DG,DN,UDG,UDN ; /枚举：有向图枚举：有向图,有向网有向网,无向图无向图,无向网无向网typedef struct ArcCell VRType adj; / VR

10、Type的类型视具体情况而定。对于带权图，的类型视具体情况而定。对于带权图，adj用以存用以存 /放边或弧上的权值放边或弧上的权值;对于无权图，对于无权图，adj用以存放用以存放0或或1(int类型类型) /InfoType * info; /一般情况下可以不使用该项一般情况下可以不使用该项 ArcCell , AdjMatrix MAX_VERTEX_NUM , MAX_VERTEX_NUM ; /AdiMatrix是一个类型为是一个类型为ArcCell的二维数组的二维数组,用以存放弧或边的邻接关系或权值用以存放弧或边的邻接关系或权值typedef struct VertexType vex

11、s MAX_VERTEX_NUM ; / VertexType是顶点值的类型是顶点值的类型 /一维数组一维数组vexs用以存放各顶点的值用以存放各顶点的值 AdjMatrix arcs; /二维数组二维数组arcs存放边或弧上的信息（如权值）存放边或弧上的信息（如权值） int vexnum , arcnum; /这两项分别存放图的顶点数目和弧的条数这两项分别存放图的顶点数目和弧的条数 GraphKind kind; / kind用以存放图的种类标志用以存放图的种类标志 MGraph11二、存储结构二、存储结构例1：例如：例如：MGraph G1; 0 1 1 0 0 0 0 0 0 0 0

12、1 1 0 0 0G1.vexs0=a，. .， G1.vexs3=d ；G1.vexnum=4； G1.arcnum=4 ； G1.kind=DGG1.arcs =abcd012312二、存储结构二、存储结构例2：abde0134c2MGraph G2; 3 9 3 6 8 6 2 4 9 2 8 4 G2.vexs0=a，. .， G2.vexs4=e ；G2.vexnum=5； G2.arcnum=6 ； G2.kind=UDNG2.arcs =38692413二、存储结构二、存储结构*当输入一个图时，要求用户先输入图的类型：Status CreateGraph(MGraph &

13、G) cinG.kind; switch(G.kind) case DG: return CreateDG(G); /0 case DN: return CreateDN(G); /1 case UDG: return CreateUDG(G); /2 case UDN: return CreateUDN(G); /3 default : return ERROR;/CreateGraph14二、存储结构二、存储结构*以无向网为例,即当用户输入图的类型标志为UDN时,有：Status CreateUDN(MGraph &G) cinG.vexnum G.arcnum; /输入顶点个数和

14、边的条数 for (i=0;iG.vexsi; /一维数组存放顶点值 for (i=0;iG.vexnum;+ +i ) /二维数组赋初值 for (j=0;jG.vexnum;+ +j ) G.arcsij= INFINITY ; /即将做为初值存入矩阵的各行各列 for (k=0;kv1 v2 w; i=locatevex(G,v1); j=locatevex(G,v2); /求顶点v1,v2在图中的位置 G.arcsij.adj=w; G.arcsji.adj=w; /无向网的邻接矩阵是对称的 return OK;/CreateUDN此处的locatevex(G,vi)是一个对一维数组G

15、.vexsG.vexnum进行搜索查找vi在图G中的位置的函数子程序；请同学们自己编写之。参考：int locatevex(MGraph G, VRType v) int k,i; k=-1; for (i=0;iG.kind; /输入图的种类 switch(G.kind) case 0: return CreateAL0(G); /DG case 1: return CreateAL1(G); /DN case 2: return CreateAL2(G); /UDG case 3: return CreateAL3(G); /UDN default : return ERROR;/Crea

16、teGraph19二、存储结构二、存储结构*以无向图为例,即当用户输入图的类型标志为2时,有：Status CreateAL2(ALGraph &G) cinG.vexnum G.arcnum; /输入顶点数和弧的条数 n= G.vexnum; e= G.arcnum; G.kind=2; for (i=0;iG.verticesi.data; G.verticesi.firstarc=NULL; /输入n个顶点的值 for (k=1;kvt vh; /输入一条边的两个顶点的值 i=locatevex(G,vt); j=locatevex(G,vh); p=new Arcnode; /申请一个弧结点存放序号申请一个弧结点存放序号j,并并 p-adjvex=j; /头插法将其插入到序号为i的顶点的单链表（即第i个单链表）的表首 p-nextarc=G.verticei.firstarc; G.verticei.firstarc=p; p= new Arcnode; /由于边可视为对称的两条弧，故 /再申请一个弧结点存放序号i, 并将其插入到序号为j的顶点的单链表的表首 p-adjvex=i; p-ne