C/C++每日一练：图的邻接矩阵和邻接表表示

C/C++每日一练：图的邻接矩阵和邻接表表示

引用

CSDN

1.

https://m.blog.csdn.net/weixin_60461563/article/details/144329197

图的邻接矩阵和邻接表是计算机科学和数据结构课程中的基础知识点，对学习算法和编程非常有帮助。本文将详细介绍这两种表示方法，并通过C和C++代码示例展示如何实现这些数据结构。

一、相关概念

1. 图（graph）

图是一种非线性数据结构，由顶点（vertex）和边（edge）组成。可以将图抽象地表示为一组顶点 V和一组边 E的集合。

以下示例展示了一个包含5个顶点和7条边的图。

顶点：V = {1,2,3,4,5}
边：E = {(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(4,5)}
图：G = {V,E}

将顶点看作节点，边看作连接各个节点的引用（指针），就可以将图看作一种从链表拓展而来的数据结构。如图所示，相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高，因而更为复杂。

1.1 图的常见类型与术语

1.1.1 常见类型

1.1.1.1 无向图（undirected graph）和有向图（directed graph）

根据边是否具有方向，可分为无向图和有向图，如图所示：

• 无向图：边表示两顶点之间的“双向”连接关系，例如QQ中的“好友关系”。
• 有向图：边具有方向性，即1→3和1←3两个方向的边是相互独立的，例如微博或抖音上的“关注”与“被关注”关系。

1.1.1.2 连通图（connected graph）和非连通图（disconnected graph）

根据所有顶点是否连通，可分为连通图和非连通图，如图所示：

• 连通图：从某个顶点出发，可以到达其余任意顶点。
• 非连通图：从某个顶点出发，至少有一个顶点无法到达。

1.1.1.3 有权图（weighted graph）和无权图（unweighted graph）

为边添加“权重”变量，从而得到如下图所示的有权图。例如，在手游中，系统会根据游戏玩家之间的“共同游戏时间”来计算玩家之间的“亲密度”，这种亲密度网络就可以用有权图来表示。

1.1.2 常用术语

图数据结构包含以下常用术语：

• 邻接（adjacency）：当两顶点之间存在边相连时，称这两顶点“邻接”。例如，在有权图中，顶点1的邻接顶点为顶点2、3、5。
• 路径（path）：从顶点A到顶点B经过的边构成的序列被称为从A到B的“路径”。例如，在有权图中，边序列1-5-2-4是顶点1到顶点4的一条路径。
• 度（degree）：一个顶点拥有的边数。对于有向图，入度（in-degree）表示有多少条边指向该顶点，出度（out-degree）表示有多少条边从该顶点指出。

1.2 图的表示

图的常用表示方式包括“邻接矩阵”和“邻接表”。以下使用无向图进行举例。

1.2.1邻接矩阵（adjacency matrix）

设图的顶点数量为n，邻接矩阵使用一个n×n大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用1或0表示两个顶点之间是否存在边。

设邻接矩阵为Matrix、顶点列表为V，那么矩阵元素Matrix[i][j] = 1且Matrix[j][i]=1，表示顶点V[i]到顶点V[j]之间存在边，反之M[i,j] = 0表示两顶点之间无边。

邻接矩阵具有以下特性。

• 顶点不能与自身相连，因此邻接矩阵主对角线元素没有意义。
• 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
• 将邻接矩阵的元素从1和0替换为权重，则可表示有权图。

使用邻接矩阵表示图时，可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为O(1)。然而，矩阵的空间复杂度为O(n^2)，内存占用较多。

1.2.2 邻接表（adjacency list）

邻接表使用数组加n个链表的形式存储来表示图，链表节点表示顶点。第i个链表对应顶点i，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）。图中展示了一个使用邻接表存储的图的示例。

邻接表仅存储实际存在的边，而边的总数通常远小于n^2，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。

二、题目要求

题目：实现一个无向图，分别用邻接矩阵和邻接表表示，支持以下操作：

1. 添加一条边。
2. 删除一条边。
3. 查询两个节点是否直接相连。

三、做题思路

3.1 邻接矩阵

数据结构

• 使用一个二维数组表示图，其中matrix[ i ][ j ]表示节点i和节点j之间的关系。
• 如果是无向图，矩阵是对称的；如果是有向图，则矩阵可能是非对称的。
• 如果是加权图，可以用边的权值代替布尔值（0和1）。

基本操作

• 添加边：将对应位置赋值为1（或权值）。
• 删除边：将对应位置赋值为0。
• 查询是否相连：检查对应位置的值是否为1。

适用场景

• 邻接矩阵适合边密集的图（稠密图），查询是否相连的时间复杂度为O(1)。
• 当图的边数较少时，矩阵会浪费大量存储空间。

3.2 邻接表

数据结构

• 使用一个数组或向量，每个位置存储一个链表或动态数组，表示该节点的所有邻接点。
• 节点的连接关系存储在链表中，动态扩展存储空间以适应图的规模。

基本操作

• 添加边：在节点u的链表中添加节点v，同时在节点v的链表中添加节点u（无向图）。
• 删除边：从节点u的链表中删除节点v，同时从节点v的链表中删除节点u（无向图）。
• 查询是否相连：遍历节点u的链表，查找是否存在节点v。

适用场景

• 邻接表适合边稀疏的图（稀疏图），节省存储空间，但查询是否相连的复杂度较高，为O(degree(u))。

四、过程解析

4.1 邻接矩阵

初始化矩阵

• 创建一个n×n的二维数组，并初始化所有值为0。
• 在C++中可以使用vector，在C中需要动态分配内存。

实现添加边功能

• 对于无向图，在矩阵中对称设置matrix[u][v]=1和matrix[v][u]=1。
• 对于有向图，只设置matrix[u][v]=1。

实现删除边功能

• 对应的位置值改为0，表示移除该边。

实现查询功能

• 直接检查matrix[u][v]是否为1即可。

内存管理

• 在C中，动态分配内存后需要手动释放，以避免内存泄漏。

4.2 邻接表

初始化邻接表

• 创建一个大小为n的数组，每个元素是一个链表或向量，表示节点的邻接点集合。
• 初始时，每个链表为空。

实现添加边功能

• 在节点u的链表中插入节点v，在节点v的链表中插入节点u（无向图）。

实现删除边功能

• 遍历链表，找到目标节点后将其移除。

实现查询功能

• 遍历节点u的链表，查找是否存在节点v。

存储空间优化

• 邻接表在稀疏图中可以显著节省空间，尤其当节点数量大但边数量少时。

五、运用到的知识点

• 数组的基本操作。
• 动态数组或链表的实现。
• 图的基础概念（节点、边）。
• 时间复杂度和空间复杂度分析。

六、代码示例

1. 邻接矩阵 - C 实现

#include <stdio.h>
#include <stdlib.h>

// 图的邻接矩阵表示
typedef struct {
    int** matrix; // 动态分配的二维数组，表示邻接矩阵
    int n;        // 图中节点的数量
} GraphMatrix;

// 初始化图
GraphMatrix* createGraph(int n) {
    GraphMatrix* graph = (GraphMatrix*)malloc(sizeof(GraphMatrix)); // 分配内存给图结构
    graph->n = n; // 设置节点数量
    // 分配 n*n 的二维数组并初始化为 0
    graph->matrix = (int**)malloc(n * sizeof(int*)); // 分配行指针数组
    for (int i = 0; i < n; i++) {
        graph->matrix[i] = (int*)calloc(n, sizeof(int)); // 每行分配 n 个整型并初始化为 0
    }
    return graph;
}

// 添加边
void addEdge(GraphMatrix* graph, int u, int v) {
    graph->matrix[u][v] = 1; // 设置 u 到 v 的值为 1
    graph->matrix[v][u] = 1; // 无向图对称，设置 v 到 u 的值为 1
}

// 删除边
void removeEdge(GraphMatrix* graph, int u, int v) {
    graph->matrix[u][v] = 0; // 将 u 到 v 的值设置为 0
    graph->matrix[v][u] = 0; // 同时设置 v 到 u 的值为 0
}

// 查询是否相连
int isConnected(GraphMatrix* graph, int u, int v) {
    return graph->matrix[u][v]; // 返回 u 到 v 的值（1 表示相连，0 表示不相连）
}

// 打印邻接矩阵
void printMatrix(GraphMatrix* graph) {
    for (int i = 0; i < graph->n; i++) { // 遍历每一行
        for (int j = 0; j < graph->n; j++) { // 遍历每一列
            printf("%d ", graph->matrix[i][j]); // 输出矩阵的值
        }
        printf("\n"); // 换行表示下一行
    }
}

// 释放内存
void freeGraph(GraphMatrix* graph) {
    for (int i = 0; i < graph->n; i++) {
        free(graph->matrix[i]); // 释放每一行的内存
    }
    free(graph->matrix); // 释放行指针数组
    free(graph);         // 释放图结构
}

int main() {
    int n = 5; // 节点数量
    GraphMatrix* graph = createGraph(n); // 初始化图
    // 添加一些边
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    printf("Adjacency Matrix:\n");
    printMatrix(graph); // 打印邻接矩阵
    printf("Is 1 connected to 2? %s\n", isConnected(graph, 1, 2) ? "Yes" : "No"); // 查询是否相连
    removeEdge(graph, 1, 2); // 删除边
    printf("Is 1 connected to 2? %s\n", isConnected(graph, 1, 2) ? "Yes" : "No"); // 再次查询
    freeGraph(graph); // 释放内存
    return 0;
}

2. 邻接表 - C++ 实现

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

// 图的邻接表表示
class GraphList {
private:
    vector<list<int>> adjList; // 用动态数组（vector）和链表（list）实现邻接表
    int n; // 图中的节点数量
public:
    // 构造函数，初始化邻接表
    GraphList(int n) : n(n) {
        adjList = vector<list<int>>(n); // 创建 n 个空链表
    }

    // 添加边
    void addEdge(int u, int v) {
        adjList[u].push_back(v); // 在节点 u 的链表中添加节点 v
        adjList[v].push_back(u); // 在节点 v 的链表中添加节点 u（无向图）
    }

    // 删除边
    void removeEdge(int u, int v) {
        adjList[u].remove(v); // 从节点 u 的链表中删除节点 v
        adjList[v].remove(u); // 从节点 v 的链表中删除节点 u（无向图）
    }

    // 查询两个节点是否相连
    bool isConnected(int u, int v) {
        for (int neighbor : adjList[u]) { // 遍历节点 u 的链表
            if (neighbor == v) return true; // 如果找到 v，说明相连
        }
        return false; // 否则不相连
    }

    // 打印邻接表
    void printList() {
        for (int i = 0; i < n; i++) { // 遍历每个节点
            cout << i << ": "; // 输出节点编号
            for (int neighbor : adjList[i]) { // 遍历该节点的邻接链表
                cout << neighbor << " "; // 输出相邻节点
            }
            cout << endl; // 换行表示下一节点
        }
    }
};

int main() {
    int n = 5; // 节点数量
    GraphList graph(n); // 初始化邻接表
    // 添加一些边
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    cout << "Adjacency List:" << endl;
    graph.printList(); // 打印邻接表
    cout << "Is 1 connected to 2? " << (graph.isConnected(1, 2) ? "Yes" : "No") << endl; // 查询是否相连
    graph.removeEdge(1, 2); // 删除边
    cout << "Is 1 connected to 2? " << (graph.isConnected(1, 2) ? "Yes" : "No") << endl; // 再次查询
    return 0;
}