图是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头部和元信息