C++详细讲解图论的基础与图的储存

简介

图是计算机科学中的一种数据结构，广泛用于网络、社交媒体、计算机程序等领域。本文将详细讲解关于图的基础知识以及如何在C++中实现图的储存。

图的基础概念

图是由节点（顶点）和边构成的一种数据结构。可以用图来描述任何二元关系，如夫妻、朋友等等。图可以分为有向图和无向图两种。

• 无向图：顶点之间的边没有方向，也就是没有从A到B的方向限制。
• 有向图：边有方向，分为起点和终点。

在图中，每个节点可能有与之相连的多条边。如果两个节点之间有直接的联系，那么它们就是相邻的节点。从一个节点到另一个节点的路径称为通路。

图的储存方式

通常有以下两种方式来储存图：

• 邻接矩阵
• 邻接表

邻接矩阵

邻接矩阵使用二维数组来表示图，其中第i行第j列表示节点i到节点j的边是否存在。如果存在则为1，否则为0。

示例：

假设有一个有向图，有4个节点分别为A、B、C、D，边分别为A->B、A->C、B->D、C->D。用邻接矩阵储存的结果如下：

  A  B  C  D
A 0  1  1  0
B 0  0  0  1
C 0  0  0  1
D 0  0  0  0

邻接表

邻接表使用数组和链表来表示图。每个节点的数组中存储指向其相邻节点链表的指针或索引。

示例：

假设有一个无向图，有4个节点分别为A、B、C、D，边分别为A<->B、A<->C、B<->D、C<->D。用邻接表储存的结果如下：

A --> B --> C
B --> A --> D
C --> A --> D
D --> B --> C

C++实现图的储存

邻接矩阵

以下代码展示了如何在C++中使用邻接矩阵来储存图，并且实现了一个简单的深度优先搜索算法：

const int MAXN = 100; //最大节点数，可以根据需要修改

int g[MAXN][MAXN]; //邻接矩阵
bool visited[MAXN]; //记录已访问过的节点

void dfs(int u) { //深度优先搜索算法
    visited[u] = true;
    for(int v=0;v<MAXN;v++) {
        if(g[u][v] && !visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    int n = 4; //节点数
    int m = 4; //边数
    memset(g,0,sizeof(g)); //初始化邻接矩阵
    memset(visited,false,sizeof(visited)); //初始化visited
    //添加边
    g[0][1] = 1;
    g[0][2] = 1;
    g[1][3] = 1;
    g[2][3] = 1;
    dfs(0); //从起点0开始进行深度优先搜索
    return 0;
}

邻接表

以下代码展示了如何在C++中使用邻接表来储存图，并且实现了一个简单的广度优先搜索算法：

const int MAXN = 100; //最大节点数，可以根据需要修改

struct Edge { //边链表节点
    int to;
    int next;
} edge[MAXN*2]; //注意要乘以2，因为无向图中每条边都有两个节点

int head[MAXN]; //储存每个节点的第一条边在edge中的位置
bool visited[MAXN]; //记录已访问过的节点

void bfs(int u) { //广度优先搜索算法
    queue<int> q;
    visited[u] = true;
    q.push(u);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int i=head[v];i!=-1;i=edge[i].next) {
            int w = edge[i].to;
            if(!visited[w]) {
                visited[w] = true;
                q.push(w);
            }
        }
    }
}

int main() {
    int n = 4; //节点数
    int m = 4; //边数
    memset(head,-1,sizeof(head)); //初始化head
    memset(visited,false,sizeof(visited)); //初始化visited
    int idx = 0; //记录在edge中的位置
    //添加边
    edge[idx].to = 1;
    edge[idx].next = head[0];
    head[0] = idx++;
    edge[idx].to = 2;
    edge[idx].next = head[0];
    head[0] = idx++;
    edge[idx].to = 3;
    edge[idx].next = head[1];
    head[1] = idx++;
    edge[idx].to = 3;
    edge[idx].next = head[2];
    head[2] = idx++;
    bfs(0); //从起点0开始进行广度优先搜索
    return 0;
}

上面两段代码分别实现了邻接矩阵和邻接表的储存方式并且实现了图的遍历算法。通过对代码的运行和调试，可以深入理解C++中储存图的两种方式。