图的抽象数据类型
ADT Graph {
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：
R={VR}
VR={<v，w> | v,w属于V且P(v,w),<v,w>表示从v到w的弧，
谓词P(v,w)定义了弧(v,w)的意义或信息}
基本操作P：
CreateGraph(&G,V,VR);
……
} ADT Graph
顶点（Vertex）：图G中的数据元素称为顶点。
有向图：若图G中的每条边都是有方向的，则称图G是有向图。
弧（Arc）：在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示，有向边又称为弧。
弧尾（Tail）：弧的始点称为弧尾（起始点）。
弧头（Head）：弧的终点称为弧头（终端点）。
无向图：若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
我们约定：
· 一条边或弧中涉及的两个顶点必须不相同，即：若
或
是G中的一条边或弧，则要求
或是G中的一条边或弧，则要求 · 一对顶点间不能有同方向的两条有向边
· 一对顶点间不能有两条无向边
设n为图中顶点的数目，e为边或弧的数目：
完全图：有
条边的无向图。
条边的无向图。 有向完全图：有n(n-1)条边弧的有向图。
稀疏图：有很少条边或弧的图（如e<nlogn）。
稠密图：有很多条边或弧的图。
子图（Subgraph）：若两个图G=(V,{E})和G’=(V’,{E’})，如果
且
，则称G’为G的子图。
且，则称G’为G的子图。
入度：在有向图中，把以顶点v为终点的弧的数目称为顶点v的入度，记为
。
。 出度：在有向图中，把以顶点v为始点的弧的数目称为顶点v的出度，记为
。
。 度：在无向图中，一个顶点的度就是与该顶点相关联的边的数目。在有向图中，顶点v的度等于顶点的出度和入度之和。顶点的度记为
，即在有向图中
。
，即在有向图中。 无论是有向图还是无向图，顶点数n、边数e和度数之间有如下关系：
路径：无向图G中，若存在着一个顶点序列
，且
均属于E(G)，则称该顶点序列为顶点v到顶点u的一条路径。如果G是有向图，路径也是有向的，它由E(G)中的弧
组成。
，且均属于E(G)，则称该顶点序列为顶点v到顶点u的一条路径。如果G是有向图，路径也是有向的，它由E(G)中的弧组成。 路径长度：路径上边或弧的数目。
简单路径：如果一条路径上所有顶点均不相同，则称此路径为一条简单路径。
简单回路（简单环）：起点和终点相同（v=u），其他顶点均不相同的简单路径称为简单回路或简单环。
连通图：在无向图G中，若从顶点
到顶点
有路径，则称与是连通的。若V(G)中任意两个不同的顶点和都连通（即有路径），则称G为连通图。
到顶点有路径，则称与是连通的。若V(G)中任意两个不同的顶点和都连通（即有路径），则称G为连通图。 连通分量：无向图G的极大连通子图称为G的连通分量。
任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。
强连通图：在有向图G中，若对于V(G)中任意两个不同的顶点 和，都存在从到以及从到的路径，则称G是强连通图。
和，都存在从到以及从到的路径，则称G是强连通图。 强连通分量：有向图G的极大连通子图称为有向图的强连通分量。
生成树：一个连通图的生成树是一个含有图的全部顶点的极小连通子图，它只有足以构成一棵树的n-1条边。
一个有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和小于n-1条边，则是非连通图。如果它有多于n-1条边，则一定有环。但是，有n-1条边的图不一定是生成树。
生成森林：如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
网络：将图的每条边都赋上一个权，称这种带权图为网络。
图的存储结构
图的存储结构至少要保存两类信息：
· 顶点数据
· 顶点间的关系（边或弧）
在实际应用中，顶点的数据一般采用顺序表存储，而边或弧应根据具体的图和需要进行的操作，设计适当的存储结构，常用的有邻接矩阵、邻接表、邻接多重表和十字链表等方式。
邻接矩阵表示法
给定图G=(V, E)，其中
，G的邻接矩阵（Adjacency Matrix）是具有如下性质的n阶方阵：
，G的邻接矩阵（Adjacency Matrix）是具有如下性质的n阶方阵：
无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。
利用邻接矩阵计算图的顶点的度、入度、出度：
用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个顶点的度数。对于无向图，顶点的度数是邻接矩阵中第i行或第i列值为1的元素个数，即：
对于有向图，邻接矩阵中第i行值为1的元素个数为顶点的出度，第i列值为1的元素的个数为顶点的图片入度，即：
网络的邻接矩阵：当G=(V, E)是一个网络时，G的邻接矩阵是具有如下性质的n阶方阵：
其中，
表示边上的权值，∞表示一个计算机允许的、大于所有边的权值的数。
表示边上的权值，∞表示一个计算机允许的、大于所有边的权值的数。
邻接矩阵的存储结构的定义：
#define INFINITY INT_MAX //最大值∞
#define MAX_VERTEX_NUM 20 //最大顶点数
typedef enum {DG,DN,UDG,UDN} GraphKind; //图的类型
typedef struct ArcCell {
VRType adj; //VRType是顶点关系类型，对无权图用1或0
//表示是否相邻；对带权图，则为权值类型。
InfoType *info; //该边或弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{ //图的邻接矩阵存储结构定义
VertexType vexs[MAX_VERTEX_NUM]; //顶点数组，存放顶点信息
AdjMatrix arcs; //邻接矩阵
int vexnum, arcnum; //图中顶点总数与弧数
GraphKind kind; //图的种类标志
} MGraph;
图的邻接矩阵创建算法：
Status CreateGraph(MGraph &G) {
scanf(&G.kind);
switch(G.kind) {
case DG: return CreateDG(G);
case DN: return CreateDN(G);
case UDG: return CreateUDG(G);
case UDN: return CreateUDN(G);
default: return ERROR;
}
} // CreateGraph
Status CreateUDN(MGraph &G) { //创建无向网的邻接矩阵
scanf(&G.vexnum, &G.arcnum, &IncInfo);
for(i=0; i<G.vexnum; i++) scanf(&G.vexs[i]);
for(i=0; i<G.vexnum; i++)
for(j=0; j<G.vexnum; j++) G.arcs[i][j]={INFINITY,NULL};
for(k=0; k<G.arcnum; k++) {
scanf(&v1, &v2, &w);
i=LocateVex(G,v1); j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
if(IncInfo) Input(*G.arcs[i][j].info);
G.arcs[j][i] = G.arcs[i][j]; //对称性
}
return OK;
} // CreateUDN
邻接表（Adjacency List）
图的邻接矩阵表示法的问题：用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。一个含有n个顶点的图，如果其边数比少得多，那么它的邻接矩阵就会有很多空元素，浪费了存储空间。
邻接表是一种顺序表和链表相结合的存储结构。
图的顶点以顺序表存储，每个顶点结点设有数据域（data）和链域（firstarc），分别存放顶点的名或其他有关信息和指向第一个与其相连的边结点的指针。
每个顶点建立一个单链表，第i个单链表的结点表示依附于顶点的边（对有向图是以顶点为尾的弧），每个边结点由3个域组成，其中邻接点域（adjvex）指示与顶点邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点，数据域（info）存储与边或弧相关的信息，如权值等。
在无向图的邻接表中，顶点的度为第i个链表中边结点的个数；而在有向图的出边表中，第i个链表中的结点个数是顶点的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为i的结点的个数是顶点的入度。
度为第i个链表中边结点的个数；而在有向图的出边表中，第i个链表中的结点个数是顶点的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为i的结点的个数是顶点的入度。 逆邻接表：对有向图中每一个顶点建立一个链接以为头的弧的表。
建立一个链接以为头的弧的表。
邻接表存储结构定义：
#define MAX_VERTEX_NUM 20 //预定义图的最大顶点数
typedef struct ArcNode { // 边结点
int adjvex ; //该边所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
InfoType *info; //该弧相关信息的指针
} ArcNode;
typedef struct VNode { //顶点结点
VertexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { //图的邻接表存储结构定义
AdjList vertics;
int vexnum, arcnum; //图的当前顶点数和弧数
int kind; //图的种类标志
} ALGraph;
无向图的邻接表创建算法：
void CreateALUDG(ALGraph &G) {
scanf(&G.vexnum,&G.arcnum); //输入图的顶点数与边数
for(i=0;i<G.vexnum;i++) {
scanf(&G.vertics[i].data); //读入顶点信息
G.vertics[i].firstarc=NULL;
}
for(k=0; k<G.arcnum; k++) { //循环建立边链表
scanf(&i,&j); //输入无序对（i,j）
s=(ArcNode*)malloc(sizeof(ArcNode));
s->adjvex=j; //邻接点序号为j
s->nextarc=G.vertics[i].firstarc;
G.vertics[i].firstarc=s; //将新结点s插入顶点vi的表头（前插法，逆序）
s=(ArcNode*)malloc(sizeof(ArcNode)); //对称性
s->adjvex=i; //邻接点序号为i
s->nextarc=G.vertics[j].firstarc;
G.vertics[j].firstarc=s; //将新结点s插入顶点vj的表头
}
}
一个图的邻接矩阵表示是唯一的，但其邻接表表示并不唯一，这是因为在邻接表结构中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。
十字链表（Orthogonal List）
十字链表是有向图的另一种链式存储结构，它将有向图的邻接表和逆邻接表结合在一起。在十字链表中也有顶点结点和弧结点，如下图所示：
十字链表的存储结构的定义：
#define MAX_VERTEX_NUM 20 //预定义图的最大顶点数
typedef struct ArcBox { // 定义弧结点
int tailvex, headvex; //该弧的头尾顶点的位置
struct ArcBox *hlink, *tlink; //分别指向弧头相同和弧尾相同的弧的指针
InfoType *info; //该弧相关信息的指针
} ArcBox;
typedef struct VexNode { //定义顶点结点
VertexType data; //顶点信息
ArcBox *firstin, *firstout; //分别指向该顶点第一条入弧和出弧
} VexNode;
typedef struct { //有向图的十字链表存储结构
VexNode xlist[MAX_VERTEX_NUM]; //顶点结点数组
int vexnum, arcnum; //图的当前顶点数和弧数
int kind; //图的种类标志
} OLGraph;
有向图的十字链表的创建算法：
Status CreateDG(OLGraph &G) {
scanf(&G.vexnum,&G.arcnum, &IncInfo);
for(i=0;i<G.vexnum;i++) {
scanf(&G.xlist[i].data);
G.xlist[i].firstin=NULL; G.xlist[i].firstout=NULL;
}
for(k=0; k<G.arcnum; k++) {
scanf(&v1,&v2);
i=LocateVex(G,v1); j=LocateVex(G,v2);
p=(ArcBox*)malloc(sizeof(ArcBox)); //创建弧结点
p->tailvex=i; p->headvex=j;
p->hlink=G.xlist[j].firstin; p->tlink=G.xlist[i].firstout;
p->info=NULL;
G.xlist[j].firstin=G.xlist[i].firstout=p;
if(IncInfo) Input(* p->info);
}
}//CreateDG
邻接多重表
邻接多重表是无向图的另一种链式存储结构，在某些图的应用问题中，邻接多重表比邻接表更方便，如对访问过边打标志或删除一条边。邻接多重表也有顶点结点和边结点，如下图所示：
邻接多重表的存储结构的定义：
#define MAX_VERTEX_NUM 20 //预定义图的最大顶点数
typedef enum {unvisited, visited} visitif
typedef struct EBox { //定义边结点
visitif mark; //访问标记
int ivex, jvex; //该边依附的两个顶点的位置
struct EBox *ilink, *jlink; //分别指向依附这两个顶点的下一条边
InfoType *info; //该边信息指针
} EBox;
typedef struct VexBox { //定义顶点结点
VertexType data; //顶点信息
EBox *firstedge; //指向该顶点第一条依附的边
} VexNode;
typedef struct { //邻接多重表的存储结构
VexBox adjmulist[MAX_VERTEX_NUM]; //顶点结点数组
int vexnum, edgenum; //图的当前顶点数和边数
int kind; //图的种类标志
} AMLGraph;
无向图的邻接多重表创建算法：
Status CreateUDG(AMLGraph &G) {
scanf(&G.vexnum,&G.edgenum, &IncInfo);
for(i=0;i<G.vexnum;i++) {
scanf(&G.adjmulist[i].data);
G.adjmulist[i].firstedge=NULL;
}
for(k=0; k<G.edgenum; k++) {
scanf(&v1,&v2);
i=LocateVex(G,v1); j=LocateVex(G,v2);
p=(EBox*)malloc(sizeof(EBox));
p->ivex=i; p->jvex=j;
p->ilink=G.adjmulist[i].firstedge; p->jlink=G.adjmulist[j].firstedge;
p->info=NULL; p->mark=unvisited;
G.adjmulist[i].firstedge=G.adjmulist[j].firstedge=p;
if(IncInfo) Input(*p->info);
}
}//CreateUDG
作者：中国农业银行研发中心西研开发一部 陈登帅
版权声明：本文出自51Testing会员投稿，51Testing软件测试网及相关内容提供者拥有内容的全部版权，未经明确的书面许可，任何人或单位不得对本网站内容复制、转载或进行镜像，否则将追究法律责任。
