今天来介绍一下图的两种存储方式，分别为邻接矩阵与邻接链表。
邻接矩阵
在线性代数中，我们就已经学习到了用矩阵来表示图的方式，而在程序中，我们完全可以用二维数组graph[i][j]来存储图的信息。下面，我们来明确一下邻接矩阵的定义：
- 数组的下标
i和j表示边的起点和终点 - 元素
graph[i][j]表示由i点到j点的边的权 - 元素
graph[i][i] = 0 - 不连通的点之间的边权值设为
INF
下面，我们就来看一下具体的代码实现：
int n; //顶点数量
int m; //边数量
int graph[MAX_NODE][MAX_NODE]; //邻接矩阵
#define I_INF 0x7fffffff //定义无穷大
void init_graph()
{
for(int i = 0;i < n;i++)
{
for(int j < 0;j < n;j++)
{
if(i == j)
graph[i][j] = 0;
else
graph[i][j] = I_INF;
}
}
for(int i = 0;i < m;i++)
{
int v1, v2, w;
cin >> v1 >> v2 >> w; //输入: 边的起点、终点、权值
graph[v1][v2] = w;
}
}上面是有向图的实现，当然，如果是无向图的话只需要将两个顶点交换之后再存储一遍即可。
邻接链表
然而，我们发现，在一些顶点多而边少的图中，采用邻接矩阵可能会变得很稀疏，空间复杂度高。这时候我们可以怎么办呢？没错，按照处理稀疏矩阵的方式，我们同样可以以链表的形式来存储，将以每个顶点作为起点的边存储在相应链表中，这就是邻接链表。当然，在实际使用中，我们也可以使用数组来模拟链表。
struct Edge
{
int next; //链表下一节点索引
int to; //边起点
int weight; //边权值
} edge[MAX_EDGE];
int count = 0;
int head[MAX_NODE];
void add(int from, int to, int weight)
{
edge[++count].next = head[from];
edge[count].to = to;
edge[count].weight = weight;
head[from] = count;
}
int get(int from, int to)
{
int ptr = head[from];
while(edge[ptr].to != to)
ptr = edge[ptr].next;
return edge[ptr].weight;
}不过，邻接链表在优化了空间复杂度的同时，却增加了查询时的时间复杂度，所以，在实际使用中，两种存储方式应按需选择。
发表回复