程序员经验分享-hwhale

基于C++的带权无向图的实现 （二）- 遍历算法

2023-11-03

该系列文章是本人整理的有关带权无向图的数据结构和算法的分析与实现，若要查看源码可以访问我的github仓库，如有问题或者建议欢迎各位指出。

目录

基于C++的带权无向图的实现 （一）- 数据结构
基于C++的带权无向图的实现 （二）- 遍历算法
基于C++的带权无向图的实现 （三）- Prim最小生成树算法
基于C++的带权无向图的实现 （四）- Dijkstra最短路径算法
基于C++的带权无向图的实现 （五）- 连通图和连通分量
基于C++的带权无向图的实现 （六）- 关节点算法

图的遍历算法

图的遍历，其实就是依次访问图中所有的结点，并且不能访问重复结点，也就是说已经访问过的结点需要做上标记。

图的遍历分为两种两种算法：

  • 深度优先遍历算法（DFT）或者深度优先搜索算法（DFS）
  • 广度优先遍历算法（BFT）或者广度优先搜索算法(BFS)

本文将介绍这两种算法的思想和代码实现思路。


深度优先遍历

深度优先遍历，简单来说就是一条路走到底，然后退一步再把另一条路走到底，依此类推访问完图中的所有结点。二叉树的前中后序遍历其实就是深度优先遍历。

该算法可以通过递归和迭代的方法实现递归来实现。

递归

  1. 访问起始顶点u，标记顶点u为“已访问”的状态。
  2. 对顶点u的第一个未访问的结点v进行深度访问，每次访问的时候都会将邻接点标记为“已访问”的状态，避免重复访问。
  3. 当遇到死胡同时回溯到之前记录的未访问过的邻接点，再进行深度访问，直到遍历完整个图。

拿上一节中出现的图来举例子，对于下图，如果从顶点A开始深度优先遍历（红色用来标记已经访问过的顶点，蓝色用来表示访问路径）：
在这里插入图片描述

首先，对A的邻居进行遍历，顶点A的邻居依次为B,D，接着递归访问顶点B。
在这里插入图片描述

再对顶点B的邻居进行遍历，顶点B的邻居依次为A,C,D,E，由于A已经访问过了，所以访问顶点C。
在这里插入图片描述

再对顶点C的邻居进行遍历，顶点C的邻居依次为B,E，由于B已经访问过了，所以访问顶点E。
在这里插入图片描述

再对顶点E的邻居进行遍历，顶点C的邻居依次为B,C,D,F,G，由于B,C已经访问过了，所以访问顶点D。
在这里插入图片描述

再对顶点D的邻居进行遍历，顶点D的邻居依次为A,B,E,F，由于A,B,E都已经访问过了，所以访问顶点F。
在这里插入图片描述

再对顶点F的邻居进行遍历，顶点D的邻居依次为D,E,G，由于D,E都已经访问过了，所以访问顶点G。
在这里插入图片描述
所有结点访问完毕，遍历结束。

递归法深度优先遍历的结果为: A B C E D F G


迭代（需要用到栈）

迭代法本质上和递归实现的步骤一样，但由于栈是先入后出的数据结构，所以实际上每次都是对顶点u的最后一个顶点v进行深度遍历，例子如下：

从顶点A开始深度优先遍历，在访问顶点A前，先将顶点A压入栈，如下所示：
在这里插入图片描述

弹出栈顶元素A，表示开始访问顶点A，然后遍历顶点A的所有邻居，将未访问过的邻居压入栈，这里A的邻居为B,D。由于所有邻居均未访问过，所以将B,D压入栈。

在这里插入图片描述
弹出栈顶元素D，表示开始访问顶点D，然后遍历顶点D的所有邻居，将未访问过的邻居压入栈，这里D的邻居为A,B,E,F。由于A已经访问过了，所以将B,E,F压入栈。
在这里插入图片描述

弹出栈顶元素F，表示开始访问顶点F，然后遍历顶点F的所有邻居，将未访问过的邻居压入栈，这里F的邻居为D,E,G。由于D已经访问过了，所以将E,G压入栈。
在这里插入图片描述

弹出栈顶元素G，表示开始访问顶点G，然后遍历顶点G的所有邻居，将未访问过的邻居压入栈，这里G的邻居为E,F。由于F已经访问过了，所以将E压入栈。

在这里插入图片描述
弹出栈顶元素E，表示开始访问顶点E，然后遍历顶点E的所有邻居，将未访问过的邻居压入栈，这里E的邻居为B,C,D,F,G。由于D,F,G已经访问过了，所以将B,C压入栈。

在这里插入图片描述
弹出栈顶元素C，表示开始访问顶点C，然后遍历顶点E的所有邻居，将未访问过的邻居压入栈，这里C的邻居为B,E。由于E已经访问过了，所以将B压入栈。

在这里插入图片描述
弹出栈顶元素B，表示开始访问顶点B，然后遍历顶点B的所有邻居，将未访问过的邻居压入栈，这里B的邻居为A,C,D,E。由于所有邻接顶点已经访问过了，此时不会压入元素入栈。

在这里插入图片描述
到这里其实已经遍历完了，但是栈内还剩五个元素，依次是BEEBB。由于B,E顶点已经访问过了，所以每次弹出栈顶元素都不会再访问图中的任何一个顶点了，直到五个元素全部弹出，栈为空时遍历才算完全结束。

迭代法深度优先遍历的结果为：A D F G E C B


广度优先遍历

广度优先遍历比深度优先遍历更好理解，简单来说就是逐层遍历，图的第一层（初始点）遍历完后开始遍历第二层，然后是第三层。实现广度优先遍历一般需要借用到先入先出的“队列”这种结构。

继续拿刚刚的图来举例，从顶点A开始广度优先遍历，在访问顶点A前，先将顶点A入队，如下所示：
在这里插入图片描述
队列首元素A出队，表示开始访问顶点A，然后遍历顶点A的所有邻居，将未访问过的邻居压入队，这里A的邻居为B,D。由于所有邻居均未访问过，所以将B,D入队。
在这里插入图片描述
队列首元素B出队，表示开始访问顶点B，然后遍历顶点B的所有邻居，将未访问过的邻居压入队，这里A的邻居为C,E,D。由于所有邻居均未访问过，所以将C,E,D入队。

在这里插入图片描述
队列首元素D出队，表示开始访问顶点D，然后遍历顶点D的所有邻居，将未访问过的邻居压入队，这里D的邻居为A,B,E,F。由于A和B已经访问过了，所以将E,F入队。

在这里插入图片描述
队列首元素C出队，表示开始访问顶点C，然后遍历顶点C的所有邻居，将未访问过的邻居压入队，这里C的邻居为B,E。由于B已经访问过了，所以将E入队。

在这里插入图片描述
队列首元素E出队，表示开始访问顶点E，然后遍历顶点E的所有邻居，将未访问过的邻居压入队，这里E的邻居为B,C,D,F,G。由于B,C,D已经访问过了，所以将F,G入队。

在这里插入图片描述
队列首元素D出队，发现D已经访问过了，所以跳过。接着出队E，发现E也访问过了。然后出队F，发现F还没访问过，因此访问顶点F，然后遍历顶点F的所有邻居，将未访问过的邻居压入队，这里F的邻居为D,E,G。由于D,E已经访问过了，所以将G入队。
在这里插入图片描述

队列首元素E出队，发现E已经访问过了，所以跳过。接着出队F，发现F也访问过了。然后出队G，发现G还没访问过，因此访问顶点G，然后遍历顶点G的所有邻居，将未访问过的邻居压入队，这里F的邻居为E,F。由于E,F都已经访问过了，所以不会再有新元素入队。

在这里插入图片描述
最后队列首元素G出队，发现G已经访问过了，队列为空，遍历完全结束。

广度优先遍历结果： A B D C E F G


代码实现

在Graph类中除了上节内容实现的功能外，额外添加了遍历算法，T为提前定义好的模板：


函数名 用途
void dft_recursion(const T& u, set& visited, vector& result) 深度优先遍历（递归辅助函数）
vector depth_first_rec(const T& u); 深度优先遍历（递归）
vector depth_first_itr(const T& u); 深度优先遍历（迭代）
vector breadth_first(const T& u); 广度优先遍历（迭代）

  1. 边的定义(edge.hpp):
template <typename T>
class Edge {
public:
	T vertex;
	int weight;

	Edge(T neighbour_vertex) {
		this->vertex = neighbour_vertex;
		this->weight = 0;
	}

	Edge(T neighbour_vertex, int weight) {
		this->vertex = neighbour_vertex;
		this->weight = weight;
	}

	bool operator<(const Edge& obj) const {
		return obj.vertex > vertex;
	}

	bool operator==(const Edge& obj) const {
		return obj.vertex == vertex;
	}
};
  1. 图的定义(graph.hpp)
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include "edge.hpp"
using namespace std;

template <typename T>
class Graph {
public:
	map<T, set<Edge<T>>> adj;  /* 邻接表 */

	bool contains(const T& u); /* 判断顶点u是否在图中 */
	bool adjacent(const T& u, const T& v); /* 判断顶点u和v是否相邻 */

	void add_vertex(const T& u); /* 添加顶点 */
	void add_edge(const T& u, const T& v, int weight); /* 添加边和权重 */

	void change_weight(const T& u, const T& v, int weight); /* 修改权重 */

	void remove_weight(const T& u, const T& v); /* 移除权重 */
	void remove_vertex(const T& u); /* 移除顶点 */
	void remove_edge(const T& u, const T& v); /* 移除边 */

	int degree(const T& u); /* 求顶点的度数 */
	int num_vertices(); /* 求图中顶点的总数 */
	int num_edges(); /* 求图中边的总数*/
	int largest_degree(); /* 求图中的最大度数 */

	int get_weight(const T& u, const T& v); /* 得到某两个顶点之间边的权重 */
	vector<T> get_vertices(); /* 得到图中所有顶点 */
	map<T, int> get_neighbours(const T& u); /* 得到顶点u的所有边 */

	void show();

	void dft_recursion(const T& u, set<T>& visited, vector<T>& result); /* 深度优先遍历递归辅助函数 */
	vector<T> depth_first_rec(const T& u); /* 深度优先遍历递归法 */
	vector<T> depth_first_itr(const T& u); /* 深度优先遍历迭代法*/
	vector<T> breadth_first(const T& u); /* 广度优先遍历迭代法 */
};

由于图的函数声明除了最后四个其他的都在前一节中实现了，所以这里只放后面四个函数的实现代码(graph.hpp)：

template <typename T> void Graph<T>::dft_recursion(const T& u, set<T>& visited, vector<T>& result) {
	result.push_back(u);
	visited.insert(u);

	for (Edge<T> edge : adj[u])
		if (visited.find(edge.vertex) == visited.end())
			dft_recursion(edge.vertex, visited, result);
}

template <typename T> vector<T> Graph<T>::depth_first_rec(const T& u) {
	vector<T> result;
	set<T> visited;
	if (contains(u))  dft_recursion(u, visited, result);
	return  result;
}

template <typename T> vector<T> Graph<T>::depth_first_itr(const T& u) {
	vector<T> result;
	set<T> visited;
	stack<T> s;

	s.push(u);
	while (!s.empty()) {
		T v = s.top();
		s.pop();
		
		if (visited.find(v) != visited.end()) {
			continue;
		}
		visited.insert(v);
		result.push_back(v);

		for (auto w : adj[v]) {
			if (visited.find(w.vertex) == visited.end()) {
				s.push(w.vertex);
			}
		}
	}
	return  result;
}

template <typename T> vector<T> Graph<T>::breadth_first(const T& u) {
	vector<T>result;
	set<T> visited;
	queue<T> q;

	q.push(u);a
	while (!q.empty()) {
		T v = q.front();
		q.pop();

		if (visited.find(v) != visited.end()) {
			continue;
		}

		visited.insert(v);
		result.push_back(v);

		for (Edge<T> edge : adj[v]) {
			if (visited.find(edge.vertex) == visited.end()) {
				q.push(edge.vertex);
			}
		}
	}
	return result;
}

测试

测试案例（graph_testing.cpp）：

#include "graph.hpp"

void test02(Graph<char> g)
{
    auto dft = g.depth_first_rec('A');
    cout << "从顶点A进行深度优先遍历（递归）: {";
    for (auto u : dft) cout << u << " ";
    cout << "}" << endl;

    vector<char> dft_itr = g.depth_first_itr('A');
    cout << "从顶点A进行深度优先遍历（迭代）: {";
    for (auto u : dft_itr) cout << u << " ";
    cout << "}" << endl;

    auto bft = g.breadth_first('A');
    cout << "从顶点A进行广度优先遍历: {";
    for (auto u : bft) cout << u << " ";
    cout << "}" << endl;
    
int main()
{
    Graph<char> g;
    g.add_vertex('A');
    g.add_vertex('B');
    g.add_vertex('C');
    g.add_vertex('D');
    g.add_vertex('E');
    g.add_vertex('F');
    g.add_vertex('G');

    g.add_edge('A', 'B', 7);
    g.add_edge('A', 'D', 5);
    g.add_edge('B', 'C', 8);
    g.add_edge('B', 'D', 9);
    g.add_edge('B', 'E', 7);
    g.add_edge('C', 'E', 5);
    g.add_edge('D', 'E', 15);
    g.add_edge('D', 'F', 6);
    g.add_edge('E', 'F', 8);
    g.add_edge('E', 'G', 9);
    g.add_edge('F', 'G', 11);

    g.add_vertex('H');
    g.add_edge('B', 'H', 9);
    g.add_edge('A', 'H', 10);
    g.add_edge('D', 'H', 11);
    g.add_edge('A', 'H', 12);
    g.remove_vertex('H');
    cout << "打印图中顶点及其邻接表的详细信息如下" << endl;
    g.show();
    cout << endl;
    
    test02(g);
    return 0;
}
}

输出结果：
在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构和算法

数据结构

算法

c

基于C++的带权无向图的实现 （二）- 遍历算法 的相关文章

随机推荐

  • CV算法工程师面试问题总结（下） 2021.06.16

    本篇主要包含数据类问题 正则化 激活函数与梯度以及回归 SVM支持向量机 K Means均值以及机器学习相关常考内容等相关面试经验 数据类问题 1 样本不平衡的处理方法 欠采样 随机删除观测数量足够多的类 使得两个类别间的相对比例是显著的

  • 【pip】解决ERROR: Could not build wheels for pycuda which use PEP 517 and cannot be installed directly

    参考 https stackoverflow com questions 64038673 could not build wheels for which use pep 517 and cannot be installed direc

  • java中四种操作（dom、sax、jdom、dom4j）xml方法

    java中四种操作 dom sax jdom dom4j xml方式详解与比较 1 DOM JAXP Crimson解析器 DOM是用与平台和语言无关的方式表示XML文档的官方W3C标准 DOM是以层次结构组织的节点或信息片断的集合 这个层

  • csv反序列化_1.6.2python 文件复制、CSV、序列化和反序列化

    1 文件复制 单个文件复制 多个文件复制 使用系统模块 os 获取指定文件夹的所有文件名 复制流程 根据地址读取源文件 将读取的写入新地址 地址用os模块获取的文件名和文件夹名整合而成 2 CSV文件的写入与读取 导入CSV模块 CSV文件

  • Qt 使用QMediaPlayer类在VS中播放音乐

    qt有许多类都可以进行播放音频文件 这里我主要讲QMediaPlayer类 如何在vs中进行播放音乐 所遇到的问题该如何解决 QMediaPlayer可以对各种后缀的音频文件进行播放 包括 wav mp3等 1 向 pro文件中添加代码 由

  • requirejs之demo

    具体的理论就不讲了 可以参考 http www ruanyifeng com blog 2012 10 javascript module html http www ruanyifeng com blog 2012 10 asynchro

  • Linux下c++遍历文件夹中文件及读取绝对路径

    文件读取等操作是程序编写的基础 因此在总结了网上多个博客的基础上 写出了如下读取文件及保存绝对路径的代码片段 整理出来供大家学习 注意 这里dirent h是只有在Linux下才有的 include

  • c高级 day2

    1 写一个1 sh脚本 将以下内容放到脚本中 在家目录下创建目录文件 dir 在dir下创建dir1和dir2 把当前目录下的所有文件拷贝到dir1中 把当前目录下的所有脚本文件拷贝到dir2中 把dir2打包并压缩为dir2 tar xz

  • ios小程序上传文件使用onHeadersReceived获取header中的参数

    在上周做小程序上传的时候出现的问题 由于使用的oss 在安卓手机上获取header中的Etag是可以正常获取的 到了ios上传获取不到header中的参数 尝试了很多方法 后来发现onHeadersReceived可以获取到header就去

  • vi中不区分大小写查找的两种方法

    2019独角兽企业重金招聘Python工程师标准 gt gt gt 在 vim中 进行关键字查找 如果内容中分了大小写的 那么 查找默认是区分了大小写的 比如 ssh的配置文件中 etc ssh sshd config中 要去禁用 root

  • sqlserver存储过程加密和解密

    加密存储过程 IF EXISTS SELECT name FROM sysobjects WHERE name encrypt this AND type P DROP PROCEDURE encrypt this GO USE pubs

  • Python 在 JMeter 中如何使用？

    要在JMeter中使用Python 需要使用JSR223 Sampler元素来执行Python脚本 使用JSR223 Sampler执行Python脚本时 需要确保已在JMeter中配置了Python解释器 并设置了正确的环境路径 1 确保

  • 性能测试-JMeter分布式测试及其详细步骤

    性能测试概要 性能测试是软件测试中的一种 它可以衡量系统的稳定性 扩展性 可靠性 速度和资源使用 它可以发现性能瓶颈 确保能满足业务需求 很多系统都需要做性能测试 如Web应用 数据库和操作系统等 性能测试种类非常多 有些概念也很相近 Lo

  • 如何编写一个完整的Linux命令

    作者 gzshun 原创作品 转载请标明出处 来源 http blog csdn net gzshun 一个完整的Linux命令需要有以下几个重要的部分组成 1 使用方法 2 命令行参数 3 移植性 1 使用方法 在每个命令当中 都需要提供

  • uniapp开发小程序，上传图片和视频功能

    1 需求 可以上传图片和视频 并且都可以删除 图片可以预览 2 效果图 3 代码

  • JS金额千分位加逗号，多种实例

    涉及到金额展示的都需要在千分位上加逗号 以下为vue项目的实例 1 在main js下挂载一个全局方法 金额千分位加逗号 Vue prototype amountRule amount gt let defaultAmount let se

  • 初探生物信息数据库——生信原理第一次实验报告（华农）

    初探生物信息数据库 生信原理第一次实验报告 华农 1 实验目的 熟悉NCBI数据库Entrez检索系统 会使用关键词检索NCBI UnitProtKB PubMed等数据库 能理解检索结果页面各条目含义 2 实验题目与解答 2 1 水稻抗病

  • quartus18.1--下载设置

    一 quartus下载流程 1 打开Quartus工程 点击 Start Compilation 按钮进行程序全编译 如下图所示 2 程序全编译无错误 编译信息如下图所示 3 3 点击 Programmer 快捷按钮 进入程序下载页面 如下

  • git修改历史提交(commit)信息

    一 修改最近一次提交的commit信息 1 首先通过 git log 查看commit信息 2 使用指令 git commit amend 进入命令模式 修改号commit信息保存后退出编辑模式 3 git push force 到远程仓库

  • 基于C++的带权无向图的实现 （二）- 遍历算法

    该系列文章是本人整理的有关带权无向图的数据结构和算法的分析与实现 若要查看源码可以访问我的github仓库 如有问题或者建议欢迎各位指出 目录 基于C 的带权无向图的实现 一 数据结构 基于C 的带权无向图的实现 二 遍历算法 基于C 的带

热门标签