图的四种存储结构
邻接矩阵
有一个存储顶点的顺序表和一个存储边/弧的二维数组。
存储结构
#define MaxInt 32767
#define MVNum 100 //最大顶点数
typedef struct {
VerTexType vexs[MVNum]; //顶点顺序表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum; //图的顶点数和边数
} AMGraph;
特点
- 无向图的邻接矩阵是对称的。
- 有向图的邻接矩阵第i行表示以顶点i为头结点的弧，第i列表示以顶点i为尾结点的弧；第i行元素之和为顶点i的出度，第i列元素之和为顶点i的入度；第i行元素之和加第i列元素之和等于顶点i的度。
- 完全图的邻接矩阵对角元素全为0， 其他元素全为1.
- 初始化时，图全置为0，网全置为∞。
- 容易实现求顶点度、找邻接点、判断两点是否直接相连等操作，但对于稀疏图非常浪费空间，适合存储稠密图。空间复杂度为O(n²)（与边数无关）。
邻接表
图的链式存储结构，只保存图中存在的边的信息。
对每个结点建立一个带头结点的单链表（边链表），放入与其相邻的结点，再把所有边链表的头结点用顺序表存储。
存储结构
#define MVNum 100
typedef struct ArcNode {
int adjvex; // 该边依附的结点编号
struct ArcNode* nextarc; // 指向下一条边的指针
OtherInfo info;
} ArcNode; // 边
typedef struct VNode {
VertexType data;
ArcNode* firstarc; // 指向第一条依附该顶点的边
} VNode, AdjList[MVNum]; // 顶点结点
typedef struct {
AdjList vertices; // 顶点表
int vexnum, arcnum;
} ALGraph;
特点
- 对于每个顶点，与其相关的边连入表中的顺序任意，所以邻接表不唯一。
- 有向图的邻接表存储的是每个结点的出边，逆邻接表存储的是入边。邻接表和逆邻接表结合可以便于算出点度。
- 无向图空间复杂度为O(n + 2e)，有向图空间复杂度为O(n + e).
有向图：十字链表
存储结构
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;
特点
可以看作结合了有向图的邻接矩阵和逆邻接矩阵。
无向图：多重邻接表
存储结构
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; // 顶点数和边数
} OLGraph;
特点
相对于邻接表，邻接多重表用一个结点存储一条边，操作更方便。