设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.edge[n][n], 用来存放顶点的信息和边或弧的信息。定义为:
![](/images/cnblogs_com/xiaotaoliang/7_2_1.gif)
(1) 无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。
(2) 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度,统计第 j 行 1 的个
数可得顶点j 的入度。在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i的 度。
图的邻接矩阵存储表示:
#define INFINITY INT_MAX // 最大值∞
#define MAX_VERTEX_NUM 20 // 最大顶点个数
typedef enum {DG, DN, AG, AN} 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;
构造一个具有n个顶点和e条边的无向网的时间复杂度为O(n2+e*n),其中O(n2)用于对邻
接矩阵初始化。
2.图的邻接表(Adjacency List)存储表示法
邻接表是图的一种链式存储结构,它对图中每个顶点建立一个单链表,第i个单链表中的结 点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧),每个结点由三个域组成:邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置,链域(nextarc)指示下一条边或弧的结点,数据 域(info)存储和边或弧相关的信息(如权值)。每个链表上附设一个表头结点,包含数据域(data)和链域(firstarc)指向链表中的第一个结点,这些表头结点通常以顺序结构的形式存储,
以便随机访问任一顶点的链表。
![](/images/cnblogs_com/xiaotaoliang/7_2_2.gif)
在无向图的邻接表中,顶点vi的度等于第i个链表中的结点数;在有向图的邻接表中,顶点vi的出度等于第i个链表中的结点数,求入度必须遍历整个邻接表,为便于求vi的入度需建立有 向图的逆邻接表(是以顶点vi为头的弧所建立的邻接表)。
图的邻接表存储表示:
#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 vertices;
int vexnum, arcnum; // 图的当前顶点数和弧数
int kind; // 图的种类标志
} ALGraph;
3. 有向图的十字链表存储表示法
十字链表(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; // 有向图的当前顶点数和弧数
} OLGraph;
4. 无向图的邻接多重表存储表示
#define MAX_VERTEX_NUM 20
typedef emnu {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; // 指向第一条依附该顶点的边
} VexBox;
typedef struct {
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum, edgenum; // 无向图的当前顶点数和边数
} AMLGraph;