图是1种数据结构,加上1组基本操作就构成了图的抽象数据类型。
图的抽象数据类型定义以下:
ADT Graph{
数据对象V:具有相同特性的数据元素的集合,称为顶点集。
数据关系R:R={VR}
VR={<v,w>|<v,w>| v,w?V∧p(v,w) ,<v,w>表示 从v到w的弧,P(v,w)定义了弧<v,w>的信息 }
基本操作P:
Create_Graph() : 图的创建操作。
初始条件:无。
操作结果:生成1个没有顶点的空图G。GetVex(G, v) : 求图中的顶点v的值。
初始条件:图G存在,v是图中的1个顶点。
操作结果:生成1个没有顶点的空图G。
… …
DFStraver(G,V):从v动身对图G深度优先遍历。
初始条件:图G存在。
操作结果:对图G深度优先遍历,每一个顶点访问且只访问1次。
? ?
BFStraver(G,V):从v动身对图G广度优先遍历。
初始条件:图G存在。
操作结果:对图G广度优先遍历,每一个顶点访问且只访问1次。
} ADT Graph
图的存储结构比较复杂,其复杂性主要表现在:
◆ 任意顶点之间可能存在联系,没法以数据元素在存储区中的物理位置来表示元素之间的关系,所以不能用简单的顺序存储结构来表示。
◆ 图中顶点的度不1样,有的可能相差很大,若按度数最大的顶点设计结构,则会浪费很多存储单元,反之按每一个顶点自己的度设计不同的结构,又会影响操作。
图的经常使用的存储结构有:邻接矩阵、邻接链表、10字链表、邻接多重表和边表。
图的邻接矩阵基本思想:用两个数组来表示图:1个1维数组存储顶点信息,1个2维数组存储边或弧的信息。该2维数组称为邻接矩阵。
无向图邻接矩阵的特性
邻接矩阵是对称方阵;
对顶点vi,其度数是第i行的非0元素的个数;
无向图的边数是上(或下)3角形矩阵中非0元素个数。
无向图的邻接矩阵中非零元个数 = 2*无向图边数
有向图邻接矩阵的特性
对顶点vi,第i行的非0元素的个数是其出度OD(vi);第i列的非0元素的个数是其入度ID(vi) 。
邻接矩阵中非0元素的个数就是图的弧的数目。
3 图的邻接矩阵的创建
图的邻接矩阵的实现比较容易,定义两个数组分别存储顶点信息(数据元素)和边或弧的信息(数据元素之间的关系) 。其存储结构情势定义以下:
#define MAXVEX 100 /* 最大顶点数,应由用户定义 */
#define INFINITY 65535
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct
{
VertexType vexs[MAXVEX]; /* 顶点表 */
EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵,可看做边表 */
int numVertexes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;
(1) 图的创建
/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *G)
{
输入顶点数numVertexes和边数numEdges ;
for(i = 0;i <G-> numVertexes;i++)
读入顶点信息,建立顶点表
for(i = 0;i <G-> numVertexes;i++)
for(j = 0;j <G-> numVertexes;j++)
G->arc[i][j]=INFINITY;/* 邻接矩阵初始化 */
for(k = 0;k <G->numEdges;k++)
读入numEdges条边,建立邻接矩阵
}
其他操作
(2) 图的顶点定位
肯定1个顶点在vexs数组中的位置(下标) ,其进程完全同等于在顺序存储的线性表中查找1个数据元素。
根据下标,读出顶点信息。
(3) 向图中增加顶点
类似在顺序存储的线性表的末尾增加1个数据元素。
(4) 向图中增加1条弧
根据给定的弧或边所依附的顶点,修改邻接矩阵中所对应的数组元素。
基本思想:数组与链表相结合。
具体办法:
顶点用1个1维数组存储,每一个数据元素还需要存储指向第1个邻接点的指针。
每一个顶点vi的所有邻接点构成1个单链表,无向图称为顶点vi的边(链)表,有向图称为顶点vi作为弧尾的出边表(或作为弧头的入边表
求某结点的度,只需查找该顶点的边表中结点的个数(或直接将顶点结点的结构再增加1项,用以存储其邻接点的个数);
判断顶点vi到vj是不是存在边,检查顶点vi的边表中是不是存在结点vj的下标j便可;
求顶点的所有邻接点,只需对该顶点的边表进行遍历便可。
注:在无向图的邻接表中,边表结点的个数=2 * 边数
2 邻接表法的特点
◆ 在边或弧稀疏的条件下,用邻接表表示比用邻接矩阵表示节省存储空间;
◆ 在无向图,顶点Vi的度是第i个链表的结点数;
◆ 对有向图可以建立正邻接表或逆邻接表。正邻接表是以顶点Vi为出度(即为弧的出发点)而建立的邻接表;逆邻接表是以顶点Vi为入度(即为弧的终点)而建立的邻接表;
◆ 在有向图中,第i个链表中的结点数是顶点Vi的出 (或入)度;求入 (或出)度,须遍历全部邻接表;
3 结点及其类型定义
#define MAX_VEX 30 /* 最大顶点数 */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct EdgeNode /* 边表结点 */
{
int adjvex; /* 邻接点域,存储该顶点对应的下标 */
EdgeType info; /* 用于存储权值,对非网图可以不需要 */
struct EdgeNode *next; /* 链域,指向下1个邻接点 */
}EdgeNode;
typedef struct VertexNode /* 顶点表结点 */
{
VertexType data; /* 顶点域,存储顶点信息 */
/* int indegree ; //顶点的度, 有向图是入度或出度 (亦可不要) */
EdgeNode *firstarc; /* 边表头指针 */
}VertexNode, AdjList[MAX_VEX];
typedef struct
{
AdjList adjList; //顶点数组(亦成为头结点向量)
int numNodes,numEdges; /* 图中当前顶点数和边数 */
}GraphAdjList;
利用上述的存储结构描写,可方便地实现图的基本操作。
(1) 图的创建 /* 建立图的邻接表结构 */
void CreateALGraph(GraphAdjList *G)
{ 输入顶点数G->numNodes和边数G->numEdges
for(i = 0;i < G->numNodes;i++)
读入顶点信息 G->adjList[i].data,
G->adjList[i].firstedge)/* 将边表置为空表 */
for(k = 0;k < G->numEdges;k++) /* 建立边表 */
{ 输入边(vi,vj)上的顶点序号;
向内存申请空间,生成边表结点;
将新生成的结点插入到以顶点vi为头结点的链表上;
( 用头插入法or尾插入法方便?)
此处需注意:如果是无向图,1条边对应两个顶点,所以应同时修正以vi为头结点和以vj为头结点的链表。
}
}
其他操作:
(2) 图的顶点定位
图的顶点定位实际上是肯定1个顶点在AdjList数组中的某个元素的data域内容。
(3) 向图中增加顶点
向图中增加1个顶点的操作,在AdjList数组的末尾增加1个数据元素。
(4) 向图中增加1条弧
根据给定的弧或边所依附的顶点,修改单链表:无向图修改两个单链表;有向图修改1个单链表。
10字链表(Orthogonal List)是有向图的另外一种链式存储结构,是将有向图的正邻接表和逆邻接表结合起来得到的1种链表。
在这类结构中,每条弧的弧头结点和弧尾结点都寄存在链表中,并将分别组织到以弧尾结点为头(顶点)结点和以弧头结点为头(顶点)结点的链表中。
◆ data域:存储和顶点相干的信息;
◆ firstin:指向以该顶点为弧头的第1条弧所对应的弧结点;
◆ firstout:指向以该顶点为弧尾的第1条弧所对应的弧结点;
◆ tailvex:唆使弧尾顶点在顶点表中的下标;
◆ headvex:唆使弧头顶点在顶点表中的下标;
◆ hlink:指向弧头相同的下1条弧;
◆ tlink:指向弧尾相同的下1条弧;
◆ Info域:指向该弧的相干信息,如网的权值
结点类型定义
#define INFINITY MAX_VAL /* 最大值∞ */
#define MAX_VEX 30 // 最大顶点数
typedef struct ArcNode
{ int tailvex , headvex ; // 尾结点和头结点在顶点表中的下标;
InfoType info ; // 与弧相干的信息, 如权值
struct ArcNode *hlink , *tlink ;
}ArcNode ; /* 弧结点类型定义 */
typedef struct VexNode
{ VexType data; // 顶点信息
ArcNode *firstin , *firstout ;
}VexNode ; /* 顶点结点类型定义 */
typedef struct
{ int vexnum ;
VexNode xlist[MAX_VEX] ;
}OLGraph ; /* 图的类型定义 */
邻接多重表(Adjacency Multilist)是无向图的另外一种链式存储结构。
在无向图的邻接表中,1条边(v,w)的两个表结点分别被选在以v和w为头结点的链表中。如果关注的重点是顶点,则邻接表是不错的选择,但在触及到边的操作会带来不便。
邻接多重表的结构和10字链表类似,每条边用1个结点表示;邻接多重表中的顶点结点与邻接表中的完全相同
Data域:存储和顶点相干的信息;
firstedge:指向依附于该顶点的第1条边所对应的表结点;
mark:用以标识该条边是不是被访问过;
ivex和jvex:分别保存该边所依附的两个顶点在顶点表中的下标;
info域:保存该边的相干信息;
ilink:指向依附于顶点ivex的下1条边;
jlink:指向依附于顶点jvex的下1条边;
结点类型定义
#define INFINITY 65535 /* 最大值∞ */
#define MAX_VEX 30 /* 最大顶点数 */
typedef emnu {unvisited , visited} Visitting ;
typedef struct EdgeNode
{ Visitting mark ; // 访问标记
int ivex , jvex ; // 该边依附的两个结点在图中的位置
InfoType info ; // 与边相干的信息, 如权值
struct EdgeNode *ilink , *jlink ;
// 分别指向依附于这两个顶点的下1条边
}EdgeNode ; /* 弧边结点类型定义 */
typedef struct VexNode
{ VexType data; // 顶点信息
ArcNode *firsedge ; //指向依附于该顶点的第1条边
}VexNode ; /* 顶点结点类型定义 */
typedef struct
{ int vexnum ;
VexNode mullist[MAX_VEX] ;
}AMGraph ;
在某些利用中,有时主要考察图中边的权值和所依附的两个顶点,即图的结构主要由边来表示,称为边表存储结构。
边表结构采取顺序存储,用2个1维数组构成,1个存储顶点信息,1个存储边的信息。边数组的每一个元素由3部份组成:
边的出发点下标
边的终点下标
边的权值
边表存储结构的情势描写以下:
#define INFINITY MAX_VAL /* 最大值∞ */
#define MAX_VEX 30 /* 最大顶点数 */
#define MAX_EDGE 100 /* 最大边数 */
typedef struct ENode
{ int begin , end ; /* 边所依附的两个顶点 */
WeightType weight ; /* 边的权值 */
}ENode ; /* 边表元素类型定义 */
typedef struct
{ int vexnum , edgenum ; /* 顶点数和边数 */
VexType vexs[MAX_VEX] ; /* 顶点表 */
ENode edges[MAX_EDGE] ; /* 边表 */
}ELGraph ;
上一篇 六、Html头部和元信息