版本比较
比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
图的存储
邻接矩阵
Adjaency 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]; int v; // 节点数 int e; // 边数 }ALGraph; |
邻接表形式的图优缺点如下:
优点:
- 节省空间。
- 便于增删顶点。
- 便于访问顶点的所有邻接点。
缺点:
- 不便于判断两个顶点之间是否有边。
- 不便于计算顶点的度,尤其是顶点的入度。
。
目录 |
---|