图的存储

· · 个人记录

图，在C++中是一种非常重要的数据结构，本章就先来讲一下图的存储。

1.邻接矩阵：

直接定义二维数组 gragh[N][N] ，N 为节点总数，节点的编号范围是 1--N-1 ，为防止数组爆掉，一般定义矩阵为gragh[N+1][N+1] ，gragh[N][N] 的空间复杂度是 O(N^2) 。一般用 gragh[i][j] 表示边 (i,j) 的权值。如果 (i,j) 是直连边，则定义 gragh[i][j] 为边 (i,j) 的权值；如果 (i,j) 不是直连边，则定义 gragh[i][j] 为 INF（无穷大）。矩阵能表示有向边和无向边，若是无向图，则定义边 (i,j) 的权值为 gragh[i][j] = gragh[j][i] ；若是有向图，则 gragh[i][j] 是边i-j 的权值，gragh[j][i] 是边 j-i 的权值。（注：邻接矩阵适合表示稠密图，而不适合表示稀疏图，因为浪费空间，稀疏图可以使用邻接表来存储）

2.邻接表：

邻接表使用的存储方式是链表，即每个节点只储存它的直连邻居。因为非直联的节点不用储存，所以节省了空间，储存效率非常高，空间复杂度为 O(n+m) ，n 为节点数量，m 为边数。但邻接表找单个节点的邻居时，要耗费大量的时间，不如邻接矩阵快，但因为表示的是稀疏图，没有太多节点，所以这个问题也就忽略不计了。

常用 STL vector 来实现邻接表：

struct edge{
    int from,to,w;
    edge(int a,int b,int c){
        from=a,to=b,w=c;//对边赋值 
    }
};
vector<edge>e[N]; //e[i]:存储第i个节点连接的所有边
//初始化：
for(int i=1;i<=n;i++)e[i].clear();
//存边：
e[a].push_back(edge(a,b,c));
//遍历节点u的所有邻居：
for(int i=0;i<e[u].size();i++){
    int v=e[u][i].to,w=e[u][i].u;
    ......
}

（用 n 表示点的数量，用 m 表示边的数量）

3.链式前向星：

链式前向星是一种常用的图存储结构，用于表示稀疏图，尤其适用于大规模图的存储和遍历。本文将介绍链式前向星的概念、实现方式以及常见应用场景。

链式前向星是一种以链表形式组织的图存储结构。它使用两个数组，分别为"头结点数组"和"边结点数组"，来表示图中的顶点和边。

通过这样的存储方式，可以有效地表示各个顶点之间的关系，并支持高效的图遍历和查询操作。

下面是用 C++ 实现链式前向星的代码示例：

#include <iostream>
#include <vector>
using namespace std;

// 边结点
struct EdgeNode {
    int to;              // 终止顶点
    int weight;          // 权重（如果有权重的话）
    int nextEdgeIndex;   // 下一条以相同起始顶点的边的索引
};

// 头结点
struct HeadNode {
    int firstEdgeIndex;  // 第一条边的索引
};

int main() {
    int numVertices, numEdges;
    cin >> numVertices >> numEdges;

    vector<HeadNode> heads(numVertices);       // 头结点数组
    vector<EdgeNode> edges(numEdges);          // 边结点数组

    for (int i = 0; i < numEdges; i++) {
        int from, to, weight;
        cin >> from >> to >> weight;

        edges[i].to = to;
        edges[i].weight = weight;
        edges[i].nextEdgeIndex = heads[from].firstEdgeIndex;

        heads[from].firstEdgeIndex = i;
    }

    // 遍历图，输出每个顶点的相邻顶点和权重（如果有权重的话）
    for (int i = 0; i < numVertices; i++) {
        cout << "Vertex " << i << ": ";

        int edgeIndex = heads[i].firstEdgeIndex;
        while (edgeIndex != -1) {
            EdgeNode edge = edges[edgeIndex];
            cout << "(" << edge.to << ", " << edge.weight << ") ";

            edgeIndex = edge.nextEdgeIndex;
        }

        cout << endl;
    }

    return 0;
}

链式前向星适用于大规模稀疏图的存储和遍历。由于只存储实际存在的边，因此可以减少存储空间的消耗。常见的应用场景包括：

  1. 网络流算法：链式前向星能有效地表示网络流中的图结构，并进行相关算法操作，如最大流、最小割等。
  2. 最短路径算法：链式前向星可以用于实现 Dijkstra 算法和 Bellman-Ford 算法等最短路径算法，以提高计算效率。
  3. 拓扑排序：链式前向星可以用于拓扑排序算法，通过遍历有向无环图的顶点和边来确定他们之间的依赖关系。

链式前向星是一种高效的图存储方法，适用于大规模稀疏图的存储与遍历。通过合理利用头结点数组和边结点数组的组织，可以快速访问图中的顶点和边，从而支持各种图算法的应用。