C++处理图存储的方式分享

在C++中处理图的存储方式有多种，这里主要讲解三种最常见和实用的方式：邻接矩阵、邻接表和关联数组。

邻接矩阵

邻接矩阵是图最简单、使用最广泛的存储方式之一，它使用一个二维矩阵表示节点之间的关系。当图中有 n 个节点时，可以用一个 n x n 的矩阵来存储它们之间的关系，矩阵中的每个元素存储两个节点之间的边的信息，如边的权重。

以下是一个用邻接矩阵存储的无向有权图的代码示例：

const int MAXN = 1000;   // 最多节点数
int Graph[MAXN][MAXN];   // 邻接矩阵，可存储节点间权重信息
int n;                   // 图中节点总数

int main(){
    // 初始化图
    memset(Graph, 0, sizeof(Graph)); // 图的全部初始化为零，即无边
    // 显示节点i和节点j之间的权重
    printf("%d\n", Graph[i][j]);
    return 0;
}

邻接表

邻接表用链表方式存储图，对于一个有 n 个节点和 m 条边的图，可以使用一个大小为 n 的数组，每个数组元素存储与其相连的所有节点。相比邻接矩阵，邻接表能够更有效地存储稀疏图。

以下是一个用邻接表存储的有向无权图的代码示例：

const int MAXN = 1000;       // 最多节点数
vector<int> Graph[MAXN];     // 邻接表，存储节点的后继
bool visited[MAXN];          // 图结点是否已经遍历
int n;                       // 图中节点总数

void dfs(int curr_node){     // dfs搜索当前节点
    visited[curr_node] = true;
    for(int i=0; i<Graph[curr_node].size(); i++){
        if(!visited[Graph[curr_node][i]]){
            dfs(Graph[curr_node][i]);
        }
    }
}

int main(){
    // 初始化图中每个节点的后继为空
    for(int i=0; i<=n; i++){
        Graph[i].clear(); 
    }
    // 访问节点i的所有后继
    for(int i=0; i<Graph[i].size(); i++){
        int next_node = Graph[i][j];
        // do something...
    }
    return 0;
}

关联数组

关联数组是一种特殊的数组，使用键-值对存储数据。对于图来说，关联数组可以用来实现一个稀疏的邻接矩阵。可以使用 C++ STL 提供的 map 来实现关联数组。

以下是用 map 存储的有向有权图的代码示例：

const int maxn = 1000;      // 最多节点数
map<int, map<int, int> > Graph;   // 关联数组，存储课件之间的权重
int n;                      // 图中节点总数

int main(){
    // 初始化图中每对节点之间的权重（无穷大）
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            Graph[i][j] = INF;    // 无穷大表示不可达
        }
    }
    // 显示节点i和节点j之间的权重
    printf("%d\n", Graph[i][j]);
    return 0;
}

示例说明：

接下来，我们通过一些示例来说明如何使用上述三种方法来处理图。

邻接矩阵

假设我们有一个无向有权图，有 n 个节点，现在想要找到任意两点之间的路径长度。假设图的邻接矩阵为 Graph[][]，以下为代码实现：

for(int i=1; i<=n; i++){
    for(int j=i+1; j<=n; j++){
        printf("path between node %d and %d is: ", i, j);
        if(!Graph[i][j]){
            printf("no path\n");
        }else{
            printf("%d\n", Graph[i][j]);
        }
    }
}

以上代码中，使用两重循环对每个节点对进行遍历，当发现节点对 (i, j) 之间没有路径时，即输出 "no path"，否则输出节点对之间的路径长度。

邻接表

现在我们有一个有向无权图，想找到从某个节点开始到另一个节点的所有路径。假设图的邻接表为 Graph[]，以下为代码实现：

void dfs(int curr_node, int dest_node, vector<int>& path){
    path.push_back(curr_node);
    if(curr_node == dest_node){
        // 当前为目标节点，则输出路径
        for(int i=0; i<path.size(); i++){
            printf("%d ", path[i]);
        }
        printf("\n");
    }else{
        // 否则继续遍历
        for(int i=0; i<Graph[curr_node].size(); i++){
            dfs(Graph[curr_node][i], dest_node, path);
        }
    }
    path.pop_back();    // 回溯
}

int main(){
    vector<int> path;
    dfs(1, 5, path); // 找从节点1到节点5的所有路径
    return 0;
}

以上代码中，使用深度优先搜索算法递归遍历节点，同时使用一个记录路径的向量 path 来保存路径。当遍历到终点时，输出所有保存在 path 中的节点，从而找到所有路径。

关联数组

现在我们有一个有向有权图，要找到从某个节点开始到其他所有节点的最短路径。假设图的关联数组为 Graph，以下为代码实现：

const int INF = 1e9;  // 假设无穷大为1e9

void Dijkstra(int S){
    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > Q; // 最小堆
    vector<int> dis(n+1, INF);    // 到每个点的距离
    vector<int> pre(n+1, 0);      // 记录到最短路径上每个节点的前一个节点
    dis[S] = 0;
    Q.push(make_pair(0, S));
    while(!Q.empty()){
        int u = Q.top().second; Q.pop();
        for(map<int, int>::iterator iter = Graph[u].begin(); iter != Graph[u].end(); iter++){
            int v = iter->first;
            int w = iter->second;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                pre[v] = u;
                Q.push(make_pair(dis[v], v));
            }
        }
    }
}

int main(){
    Dijkstra(1);   // 找节点1到其他所有节点的最短路径
    return 0;
}

以上代码中，使用 Dijkstra 算法遍历以起点 S 开始到所有节点的最短路径，同时记录每个节点的前驱节点。当遍历完成后，输出所有节点到起点的最短路径长度，并输出最短路径的具体路径。

注意，以上的关联数组实现方式使用 STL 的 map 类型，但是在实际使用中，我们可以使用 C++11 的 unordered_map 容器替代 map，以提高代码效率。