1.邻接矩阵
1.1 基本概念
用一个一维数组存储图中顶点的信息,用一个二维数组存储图中边的信息。
顶点的保存:直接存在一个一维数组里面。
边的存储:每一行代表一个顶点与其他顶点之间边的存在关系。结点数为n的图
G=(V, E)
的邻接矩阵A是n*n
的。若Vi与Vj之间存在一条边,那么就在i行j列让这个邻接矩阵A[i][j] = 1
,如果不存在,A[i][j] = 0
(带权图不存在使用∞)。
易错点:
- 带权图,为什么不能用零(0)表示带权图的边不存在?
- 0会代表权值,认为0这个权值是存在的,所以0不能用来表示边是否存在。
- 认定权值是不可能为一个巨大的数,权值越大代表代价越大。这个巨大的数字代表边不存在。
1.2 邻接矩阵数据结构
计算机之中,图的信息不仅仅包括弧信息、顶点的信息,对图有一个宏观的信息。
图的拓扑信息:微观信息和图的宏观信息。
图的宏观信息:有多少条边arcnum,有多少个顶点vexsnum,图是什么类型GraphKind(一共是4中类型:有(无)向图、(不)带权图)。
图的微观信息:顶点与顶点之间边的关系(弧)
1.2.1 图的类型
// 图的类型 typedef enum GraphKind { DG, // directed Graph,有向不带权图 UDG, // undirected Graph,无向不带权图 DN, // directed Network,有向带权图(有向网) UDN, // undirected Network,无向带权图(无向网) }GraphKind;
1.2.2 顶点
图中顶点最大数量
#define MXA_VERTEX 100
顶点数据类型
typedef int VertexType;
1.2.3 弧
注意:弧不仅仅只有权值,还可能有其他信息。如北京到天津的铁路抽象成依附于被北京和天津两个城市顶点,不仅仅是这个铁路有多长,额外信息:客流量、次数
弧的权值类型及权值无穷定义
// 有权图中的无穷大,使用C语言中的最大值宏定义 #define INFINITY INT_MAX
弧结构体定义
typedef struct ArcCell { int weight = 0; //不带权图时的权值 // int weight = INFINITY; //带权图时的权值 // InfoType* info; }ArcCell;
1.2.4 邻接矩阵
图的拓扑信息,不仅仅有弧信息,顶点信息,宏观信息
typedef struct { // 顶点信息,默认顶点编号从1开始 VertexType vexs[MXA_VERTEX]; // 弧信息 ArcCell arcs[MXA_VERTEX][MXA_VERTEX]; int vexnum; // 图当前顶点数 int arcnum; // 图当前弧数(边数) GraphKind kind; // 图的类型 }MGraph;
2.邻接表
2.1 基本概念
将公共的顶点作为链表的头结点,多条共源点的弧依附的源点都存在链表的头结点中。
每个顶点都会存到头结点中,这些头结点都是相同的数据类型。将其打包成为一个数组。这样就可以通过索引直接访问每个头结点(顶点<=>源点)。链表知道头结点就能知道整条链。
使用头插法插入较为简单。

顶点的类型:
- 是源点,不是源点(以源点开始出发(头结点)顺--->邻接表);
- 是终点,不是终点(以终点开始出发(头结点)逆--->逆邻接表)。
2.2 邻接表数据结构
2.2.1 边表结点
注意:弧不仅仅只有权值,还可能有其他信息
// 图结点(边表结点) typedef struct ArcNode { // 一般顶点默认是数组编号,所以跟索引一一对应,顶点编号即索引 int adjvex; // 目的结点的编号,目的顶点对应头结点在数组中的编号 struct ArcNode* next; // 指向下一条弧的指针 // 权值 int weight; // InfoType* info; // 网的权值信息 }ArcNode;
2.2.2 顶点表结点
// 顶点表结点 typedef struct VNode { VertexType data; // 顶点信息 // 只是为了区分指针是从弧结点获得,还是头结点获得 ArcNode* first; // 指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VERTEX];
2.2.3 邻接表
// 以邻接表存储的图 typedef struct { AdjList vertices; // 邻接数组,用于存顶点信息(头结点) int vexnum; // 图当前顶点数 int arcnum; // 图当前弧数(边数) GraphKind kind; // 图的类型 }ALGraph;