版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
邻接矩阵
Adjacency matrix
,使用矩阵来表示点与点的连接关系,包含两部分:
- 一个一维数组存储图中顶点的信息。
- 一个二维数组存储图中顶点之间的邻接关系。
如果顶点的信息是0~n编号,则可以省略掉一维数组,但如果顶点是类似字符串这样的信息,则需要先用一维数组存储,然后将下标作为邻接矩阵的顶点,以下是一个邻接矩阵的示例:
使用邻接矩阵存储图时要考虑以下问题:
- 对角线上的点为0,这个设置可以简化后续运算。
- 有向图 vs 无向图:无向图是沿对角线对称的。
- 无权图 vs 带权图:无权图每个位置只能为0和1,但有权图可以是具体的数值,表示这条边的权值。
邻接矩阵形式的图优缺点如下:
优点:
- 快速判断两顶点之间是否有边。
- 方便计算每个顶点的度,包括入度和出度。
缺点:
- 空间复杂度高,尤其是在存储稀疏图时空间利用率低。
- 不便于增加或删除顶点。
- 访问一次全部的邻接点时间固定为O(n),其中n为顶点的个数,如果n较大,则访问邻接点的将非常耗时。
邻接表
Adjacency list
,图的一种链表存储方式,包含两部分:
顶点的所有邻接点构成一个单链表,但如果图的情况比较简单,或者图只需要建立一次,也可以使用数组来存储所有的邻接点。以下是一个邻接表的示意图:
以下是邻接表的一些代码实现形式:
代码块 |
---|
vector<int> graph[MAXN]; // MAXN个顶点,graph[i]表示顶点i的全部邻接点
// 邻接点类型
struct Node {
int val; // 邻接点下标
Node *next; // 下一个邻接点
Node() : val(0), next(nullptr) {}
Node(int v) : val(v), next(nullptr) {}
Node(int v, Node *next) : val(v), next(next) {}
};
// 顶点类型
struct VexNode {
VexType data; // 顶点的数据类型,比如字符串,数字等
Node *first; // 指向第一个邻接点
};
// 邻接表类型
typedef struct {
VexNode nodes[MAXN]; // n个顶点,每个顶点有自己的数据,以及一个指向全部邻接点的单链表
int v; // 节点数
int e; // 边数
}ALGraph; |
邻接表形式的图优缺点如下:
优点:
- 节省空间。
- 便于增删顶点。
- 便于访问顶点的所有邻接点。
缺点:
- 不便于判断两个顶点之间是否有边。
- 不便于计算顶点的度,尤其是顶点的入度。
边集数组
Edge list
,只存储边和边的权值,不关注顶点信息,如下:
代码块 |
---|
struct Edge {
int u; // 起点
int v; // 终点
int w; // 权值
};
Edge G[MAXN]; // 边集数组 |
边集数组这种图的存储形式不以顶点为中心,只关注边,优点是可以对边按权值排序,以便于按顺序操作边,比如Kruskal算法就需要从小到大枚举所有的边,缺点是不便于判断两点之间是否有边,也不便于访问所有的邻接点和计算度。
。
目录 |
---|