Adjacency matrix
,使用矩阵来表示点与点的连接关系,包含两部分:
如果顶点的信息是0~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算法就需要从小到大枚举所有的边,缺点是不便于判断两点之间是否有边,也不便于访问所有的邻接点和计算度。
。