六讲贯通C++图的应用之一基本储存方法("C++图应用六讲系列之一：基础存储方法解析")

原创

ithorizon 7个月前 (10-19) 阅读数 30 #后端开发

C++图应用六讲系列之一：基础存储方法解析

一、引言

在计算机科学中，图是一种非常常见的数据结构，它广泛应用于各种领域，如网络结构、社会关系、路径查找等。C++作为一种高效、灵活的编程语言，提供了多种方法来实现图的存储。本文将详细介绍C++图中常用的基本存储方法，帮助读者更好地懂得和应用图。

二、图的定义与基本术语

图由顶点（Vertex）和边（Edge）组成，分为无向图和有向图两种类型。以下是一些基本术语：

顶点：图中的基本单元，通常用V描述。

边：连接两个顶点的线段，分为无向边和有向边。

邻接顶点：与某个顶点直接相连的顶点。

度：顶点的邻接顶点数，分为入度和出度。

三、邻接矩阵存储方法

邻接矩阵（Adjacency Matrix）是一种常用的图存储方法，它使用一个二维数组来描述图中的顶点关系。对于无向图，如果顶点i与顶点j之间存在边，则矩阵的第i行第j列和第j行第i列的元素为1；对于有向图，则只设置第i行第j列的元素为1。


// 邻接矩阵存储方法的C++实现
#include 
#include 
using namespace std;
const int MAX_VERTICES = 100; // 最大顶点数
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
void addEdge(int u, int v) {
    adjacencyMatrix[u][v] = 1;
    adjacencyMatrix[v][u] = 1; // 对于无向图，需要同时设置两个位置
}
void printGraph() {
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            cout << adjacencyMatrix[i][j] << " ";
        }
        cout << endl;
    }
}

四、邻接表存储方法

邻接表（Adjacency List）是另一种常用的图存储方法，它使用链表来存储每个顶点的邻接顶点。对于无向图，每个顶点对应一个链表，链表中包含所有与该顶点相连的顶点；对于有向图，每个顶点对应一个出边链表和一个入边链表。


// 邻接表存储方法的C++实现
#include 
#include 
#include 
using namespace std;
struct Edge {
    int vertex; // 邻接顶点
    Edge* next; // 指向下一条边的指针
};
vector adjacencyList; // 邻接表
void addEdge(int u, int v) {
    // 添加u到v的边
    Edge* edge = new Edge{v, adjacencyList[u]};
    adjacencyList[u] = edge;
    // 对于无向图，还需要添加v到u的边
    edge = new Edge{u, adjacencyList[v]};
    adjacencyList[v] = edge;
}
void printGraph() {
    for (int i = 0; i < adjacencyList.size(); i++) {
        Edge* edge = adjacencyList[i];
        cout << "顶点" << i << ": ";
        while (edge != nullptr) {
            cout << edge->vertex << " ";
            edge = edge->next;
        }
        cout << endl;
    }
}

五、邻接多重表存储方法

邻接多重表（Adjacency Multilist）是邻接表的改进，它为无向图中的每一条边搭设一条边表，包含边的两个顶点信息和边的指针。这种存储方法便于进行边的删除操作。


// 邻接多重表存储方法的C++实现
#include 
#include 
using namespace std;
struct EdgeNode {
    int vertex; // 边的另一个顶点
    EdgeNode* next; // 指向下一条边的指针
};
struct VertexNode {
    int degree; // 顶点的度
    EdgeNode* firstEdge; // 指向第一条边的指针
};
vector adjacencyMultilist; // 邻接多重表
void addEdge(int u, int v) {
    // 添加u到v的边
    EdgeNode* edge = new EdgeNode{v, adjacencyMultilist[u].firstEdge};
    adjacencyMultilist[u].firstEdge = edge;
    // 添加v到u的边
    edge = new EdgeNode{u, adjacencyMultilist[v].firstEdge};
    adjacencyMultilist[v].firstEdge = edge;
    // 更新顶点的度
    adjacencyMultilist[u].degree++;
    adjacencyMultilist[v].degree++;
}
void printGraph() {
    for (int i = 0; i < adjacencyMultilist.size(); i++) {
        cout << "顶点" << i << "的度：" << adjacencyMultilist[i].degree << endl;
        EdgeNode* edge = adjacencyMultilist[i].firstEdge;
        cout << "顶点" << i << "的邻接顶点：";
        while (edge != nullptr) {
            cout << edge->vertex << " ";
            edge = edge->next;
        }
        cout << endl;
    }
}