【C++数据结构 | 图速通】10分钟掌握邻接矩阵 & 邻接表 | 快速掌握图论基础 | 快速上手抽象数据类型图

2023-12-13 03:48:41

by.Qin3Yu

请注意:严格来说,图不是一种数据结构,而是一种抽象数据类型。但为了保证知识点之间的相关性,也将其列入数据结构专栏。

本文需要读者掌握顺序表和单链表的操作基础,若需学习,可参阅我的往期文章:
【C++数据结构 | 顺序表速通】使用顺序表完成简单的成绩管理系统.by.Qin3Yu
【C++数据结构 | 单链表速通】使用单链表完成数据的输入和返回元素之和.by.Qin3Yu

本文将不会涉及图的具体操作案例,若需阅读案例,可参阅我的往期文章:
【经典案例 | 骑士之旅】回溯算法解决经典国际象棋骑士之旅问题 | 详解Knight’s Tour Problem数学问题.by.Qin3Yu
【算法详解 | 最小生成树 I 】详解最小生成树prim算法(拓展kruskal算法) | 电力网络最短路径覆盖问题.by.Qin3Yu

文中所有代码默认已使用std命名空间且已导入部分头文件

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

概念速览

图的基本概念及定义

  • 图(Graph) 是由一组顶点和连接这些节点的组成的数据类型,可以将图抽象的看作为一些岛屿和连接这些岛屿的小桥,顶点就是岛屿,边就是桥。点和边是构成图的基本元素,如下所示就是一个图:

在这里插入图片描述

  • 注意:大多数数据结构和类型都可以为空,但是 图不可以为空

向性与连通性

  • 在图中,如果 所有的边 都没有方向限制,均可以双向通行,则称为无向图。相反,如果 所有的边 都具有方向限制,每条边只提供单向通行,则称为无向图。

在这里插入图片描述

  • 无向图 中,如果图上任意一对点都有路径连通(可以穿过其他点),则称为 连通图 。如果在 有向图 中,如果图上任意一对点都有路径连通且 双向连通 ,则称为 强连通图

在这里插入图片描述
在这里插入图片描述

特别注意:有向图需双向连通才算作强连通图!

加权图与边权

  • 在很多图中,每条边都有指定的长度,且长度各不相同。在图论中,边的长度叫做 边权 ,每条边都有权值的图叫做 加权图 ,例如在下图中,图书馆到体育室的边的长度为1200m,则我们可以说图书馆-体育室的 边权 为1200:

在这里插入图片描述

稀疏图与稠密图

  • 在图中,边数明显少于点数 的图叫做稀疏图,相反,点数明显少于边数 的图叫做稠密图。需要注意,稀疏图与稠密图只是一个相对而言的概念,没有明确的数值指明边和点之间的数量界限。

在这里插入图片描述

度与入度出度

  • 在无向图中,某个点的 度指的是与这个点相连的边的数量。如图所示,我们可以说 A点 的度为 2B点 的度为 1

在这里插入图片描述

  • 在有向图中,某个点的 入度是指与该点相连,且终点为该点 的边的数量。相反,某个点的* 出度是指与该点相连,且起点为该点* 的边的数量。如图所示,我们可以说 A点 的出度为 2,入度为 1

在这里插入图片描述

一个明确的图应具有以下特征:

1. 无重复边: 在无向图中,每对点之间只有唯一的一条边连接,不存在一对点之间有两条边的情况;
2. 明确向性: 大多数情况下的图要么是有向图,要么是无向图,很少存在同一张图中某些边有向同时某些边无相(混合图)的情况;
3. 无自环: 在图中不存在连接一个节点到其自身的边。
在这里插入图片描述


图的存储与表示

图根据稀疏和稠密的特征有两种常用的存储方式,分别是邻接矩阵和邻接表。

邻接矩阵

  • 在邻接矩阵中,我们使用一个二维数组(矩阵)来表示图,如下图中有6个点,则我们需要画一个6×6的矩阵,且默认表内元素全部为0:

在这里插入图片描述

int n = 6;  // 点数
vector<vector<int>> Graph(n, vector<int>(n, 0));  // 初始化一个n×n的矩阵,默认为0
  • 如图,点1点0 之间有一条边连接,则我们在 (1,0) 位置填入 1 ,表示 点1点0 之间有边:

在这里插入图片描述

  • 同理,点1点2 之间有一条边连接,则我们在 (2,1) 位置填入 1 ,表示 点2点1 之间有边:

在这里插入图片描述

  • 一直重复这个过程,我们便可以得出以下结果:

在这里插入图片描述

  • 但同时根据无向表双向通行的特性,点0点1 有边,那么反过来 点1点0 也有边,所以我们还需要反过来再重复一次,将剩下的半部分补齐。如下图所示,可以看到 无向图的邻接矩阵呈对角线对称 ,所以我们在使用程序输入时可以直接 对称输入

在这里插入图片描述

for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    Graph[x][y] = 1;
    Graph[y][x] = 1;  // 对称输入
}
  • 但如果图是有向图,则只能逐个输入:
int m = ...  // 边数
for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    Graph[x][y] = 1;
}
  • 从上面的案例可以看出邻接矩阵需要维护一个n×n的二维数组,且使用1来标记边的位置,所以不难看出,假如图是点很多而边很少的稀疏图,则会浪费大量的内存。所以,邻接矩阵更适合表示稠密图和无向图

邻接表

  • 除了用矩阵外,我们还可以用多链表来表示图。在链表中,每个节点具有两个成员,一个为该节点的值,另一个为指向下一个节点的指针,我们先初始化一些链表,让每个点都有一串对应的链表来表示自己与其他点的相连关系:

在这里插入图片描述

//定义单链表
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

const int n = 6;  // 节点数
const int m = 7;  // 边数
ListNode* Graph[n];  // 声明多个链表
  • 如图,点0点1 相连,则我们在 0号链表 上增加节点,节点值为 1,代表 点1

在这里插入图片描述

  • 然后再看 点1点1点2 相连,则我们在 1号链表 上增加节点,节点值为 2,代表 点2

在这里插入图片描述

  • 不断重复此过程,我们便可以得出如下的结果,这便是图的邻接表,与邻接矩阵相比,邻接表不需要维护一个很大的矩阵来表示边与边的关系,但是构造起来也相对复杂。因此,邻接表更适合表示稀疏图和有向图:

在这里插入图片描述

  • 在具体的代码实现中,我们只需要将节点链接到链表后面即可,具体操作请参阅我的往期单链表教程,本文不再赘述:
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;

    ListNode* newNode = new ListNode(v);
    newNode->next = Graph[u];
    Graph[u] = newNode;

}
  • 但要注意,在无向图中边是双向互通的,只要 u 有一条路径指向 v,那么相反 v 也有一条路径指向 u。因此,对于无向图,我们需要对称输入
for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

    ListNode* newNode1 = new ListNode(v);
    newNode1->next = Graph[u];
    Graph[u] = newNode1;

    ListNode* newNode2 = new ListNode(u);
    newNode2->next = Graph[v];
    Graph[v] = newNode2;

}
至此图的相关内容已讲解完毕,具体案例可以参阅我的往期文章(如文章开头所示)(=
如需提问,可以在评论区留言或私信(=

完整代码展示

无向图邻接矩阵

在这里插入图片描述

代码

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

int n = 6;  // 点数
int m = 7;  // 边数
vector<vector<int>> Graph(n, vector<int>(n, 0));

int main() {

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        Graph[u][v] = 1;
        Graph[v][u] = 1;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << Graph[i][j] << " ";
        cout << endl;
    }

    return 0;
}

参考输入

0 1
1 2
2 3
3 4
4 0
2 5
3 5

参考输出

0 1 0 0 1 0
1 0 1 0 0 0
0 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 0 1 1 0 0

有向图邻接矩阵

在这里插入图片描述

代码

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

int n = 6;  // 点数
int m = 7;  // 边数
vector<vector<int>> Graph(n, vector<int>(n, 0));

int main() {

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        Graph[u][v] = 1;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << Graph[i][j] << " ";
        cout << endl;
    }
    
    return 0;
}

参考输入

0 1
1 2
2 3
3 4
4 0
3 5
5 3

参考输出

0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 1
1 0 0 0 0 0
0 0 0 1 0 0

无向图邻接表

在这里插入图片描述

代码

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

const int n = 6;  // 节点数
const int m = 7;  // 边数
ListNode* Graph[n];

int main() {

    for (int i = 0; i < n; i++)
        Graph[i] = nullptr;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        ListNode* newNode1 = new ListNode(v);
        newNode1->next = Graph[u];
        Graph[u] = newNode1;

        ListNode* newNode2 = new ListNode(u);
        newNode2->next = Graph[v];
        Graph[v] = newNode2;
    }

    for (int i = 0; i < n; i++) {
        cout << i << ": ";
        ListNode* curr = Graph[i];
        while (curr != nullptr) {
            cout << curr->val << " ";
            curr = curr->next;
        }
        cout << endl;
    }

    return 0;
}

参考输入

0 1
1 2
2 3
3 4
4 0
2 5
3 5

参考输出

0: 4 1
1: 2 0
2: 5 3 1
3: 5 4 2
4: 0 3
5: 3 2

有向图邻接表

在这里插入图片描述

代码

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

const int n = 6;  // 节点数
const int m = 7;  // 边数
ListNode* Graph[n];

int main() {

    for (int i = 0; i < n; i++)
        Graph[i] = nullptr;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        ListNode* newNode = new ListNode(v);

        newNode->next = Graph[u];
        Graph[u] = newNode;
    }

    for (int i = 0; i < n; i++) {
        cout << i << ": ";
        ListNode* curr = Graph[i];
        while (curr != nullptr) {
            cout << curr->val << " ";
            curr = curr->next;
        }
        cout << endl;
    }

    return 0;
}

参考输入

0 1
1 2
2 3
3 4
4 0
3 5
5 3

参考输出

0: 1
1: 2
2: 3
3: 5 4
4: 0
5: 3

感谢您的观看(=

by.Qin3Yu

文章来源:https://blog.csdn.net/qq_38970634/article/details/134824972
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。