数据结构之图的遍历

图的遍历

图的遍历目的是访问图的每一个顶点恰好一次,，同时访问图中每条边恰好一 次。

对于无向图，常见的遍历方式有深度优先遍历（Depth-First Search, DFS） 和广度优先遍历（Breadth-First Search, BFS）。

1 深度优先遍历（DFS）

深度优先遍历是一种用于遍历或搜索树或图的算法。

深度优先搜索是一个递归的过程。

  • 首先，选定一个出发点后进行遍历，如果有邻接的未被访问过的节点则继续前进。
  • 若不能继续前进，则回退一步再前进
  • 若回退一步仍然不能前进，则连续回退至可以前进的位置为止。
  • 重复此过程，直到所有与选定点相通的所有顶点都被遍历。

示例

先选择一个起始的顶点

、在这里插入图片描述

选择其中一个邻接点

在这里插入图片描述

3没有邻接点，回退到2

在这里插入图片描述

2有两个邻接点，但是3已经访问过了，选择0

在这里插入图片描述

0有两个邻接点，但是2已经访问过了，选择1

在这里插入图片描述

1有1个邻接点，但是2已经访问过了,于是整个深度优先遍历完成，输出结果为2->3->0->1

代码如下：

#include <iostream>
using namespace std;// 定义图的边（顶点值默认从0开始）用两个顶点之间的连接表示边
typedef struct Node
{int vertex;        // 下一个顶点的值struct Node *next; // 下一条顶点（如果当前顶点没有更多的邻接点，则此指针为NULL）
} Node;// 定义图
typedef struct Graph
{int numVertices; // 顶点数Node **adjLists; // 邻接表，指向指针数组的指针，每个指针都指向一个Node链表的头部。数组// 的大小numVertices 数组元素则是指向从该顶点出发的第一条边的指针（如果顶点没有邻接点，则为// NULL）。bool *isVisited; // 标记看看是不是访问过 数组的大小numVertices （顶点数）
}Graph;// 创建一个图，包含vertices个顶点
Graph *createGraph(int vertices)
{Graph *graph = new Graph();if (!graph){perror("创建失败");return nullptr;}// /初始化顶点数graph->numVertices = 0;graph->adjLists = new Node *[vertices]; // 表示一个包含 vertices 个 Node* 元素的数组。在C++中，数组名在大多数情况下会退化成指向数组首元素的指针// new Node*[vertices] 返回的是一个指向包含 vertices 个 Node* 元素的数组的指针，其类型是 Node**，这与 adjLists 的类型匹配// /为邻接表申请内存for (int i = 0; i < vertices; ++i){graph->adjLists[i] = nullptr;}// 标注位申请内存graph->isVisited = new bool [vertices] { 0 };return graph;
}// 添加边 src起点 dest终点
void addEdge(Graph *graph, int src, int dest)
{// 创建边Node *newNode = new Node();//  //设置邻接点newNode->vertex = dest;// 将新边添加到起点的链表中newNode->next = graph->adjLists[src];// 更新第一天条边graph->adjLists[src] = newNode;graph->adjLists[src] = newNode;如果是无向图，也需要添加反向边Node* newNode2 = (Node*)malloc(sizeof(Node));// Node* newNode2 = new Node;// newNode2->vertex = src;// newNode2->link = graph->adjLists[dest];// graph->adjLists[dest] = newNode2;
}// 深度优先遍历
void DFS(Graph *graph, int v)
{// 输出遍历到的节点cout << v << " ";// 递归访问所有未访问的邻接顶点Node *adjList = graph->adjLists[v];while (adjList){// 标记当前节点为已访问graph->isVisited[v] = true;// 邻接点未被访问到if (!graph->isVisited[adjList->vertex]){ // 递归调用 访问他的所有邻接点DFS(graph, adjList->vertex);}// 往后遍历每一条边adjList = adjList->next;}
}// 清理Graph对象
void freeGraph(Graph *graph)
{if (!graph){return;}// 释放邻接表中每个链表占用的内存for (int i = 0; i < graph->numVertices; ++i){Node *current = graph->adjLists[i];while (current){Node *next = current->next; // 保存下一条边的指针delete current;             // 释放当前边的内存current = next;             // 移动到下一条边}}// 释放邻接表数组本身占用的内存delete[] graph->adjLists;// 释放访问标记数组占用的内存delete[] graph->isVisited;
}int main()
{// 创建一个包含4个顶点的图Graph *graph = createGraph(4);addEdge(graph, 0, 1);addEdge(graph, 0, 2);addEdge(graph, 1, 2);addEdge(graph, 2, 0);addEdge(graph, 2, 3);// 深度优先遍历图cout << "深度优先遍历（从顶点2开始）:" << endl;DFS(graph, 2);delete graph;graph = NULL;return 0;
}

newNode1->next = graph->adjList[src];意思是 新节点的 next 指针指向当前 src 邻接链表的第一个节点。

这样，新节点 newNode1 被插入到链表的头部

graph->adjList[src] = newNode1; 将 src 的邻接链表的头部更新为 newNode1。这样，newNode1 成为链表的新头节点

结果是

深度优先遍历（从顶点2开始）:
2 0 1 3

1.2 广度优先遍历（BFS）

广度优先遍历是图的另一种遍历方式，它从根节点开始，首先访问离根节点最近的节点（即根节点的所 有邻接节点），然后逐层向外访问，直到访问完所有节点。

  • 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点
  • 然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
  • 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止(队列为空)。

示例

先选择一个起始的顶点·

在这里插入图片描述

2的邻接点有两个，全部入队，队列元素为3， 0

在这里插入图片描述

3没有邻接点，出列，输出3,队列元素为0

在这里插入图片描述

0的邻接点是1和2，但是2已经访问过了，1入队，0出列，输出0，队列元素为1

在这里插入图片描述

1的邻接点是2，但是2已经访问过了，0出列，输出0，队列元素为空，同时访问完毕 整个广度优先遍历完成，输出结果为2->3->0->1

在这里插入图片描述

代码如下

#include <iostream>
using namespace std;
#include <queue>
// 定义图的边（顶点值默认从0开始）用两个顶点之间的连接表示边
typedef struct Node
{int vertex;        // 下一个顶点的值struct Node *next; // 下一条顶点（如果当前顶点没有更多的邻接点，则此指针为NULL）
} Node;// 定义图
typedef struct Graph
{int numVertices; // 顶点数Node **adjLists; // 邻接表，指向指针数组的指针，每个指针都指向一个Node链表的头部。数组// 的大小numVertices 数组元素则是指向从该顶点出发的第一条边的指针（如果顶点没有邻接点，则为// NULL）。bool *isVisited; // 标记看看是不是访问过 数组的大小numVertices （顶点数）
}Graph;// 创建一个图，包含vertices个顶点
Graph *createGraph(int vertices)
{Graph *graph = new Graph();if (!graph){perror("创建失败");return nullptr;}// /初始化顶点数graph->numVertices = vertices;graph->adjLists = new Node *[vertices]; // 表示一个包含 vertices 个 Node* 元素的数组。在C++中，数组名在大多数情况下会退化成指向数组首元素的指针// new Node*[vertices] 返回的是一个指向包含 vertices 个 Node* 元素的数组的指针，其类型是 Node**，这与 adjLists 的类型匹配// /为邻接表申请内存for (int i = 0; i < vertices; ++i){graph->adjLists[i] = nullptr;}// 标注位申请内存graph->isVisited = new bool [vertices] { 0 };return graph;
}// 添加边 src起点 dest终点
void addEdge(Graph *graph, int src, int dest)
{// 创建边Node *newNode = new Node();//  //设置邻接点newNode->vertex = dest;// 将新边添加到起点的链表中newNode->next = graph->adjLists[src];// 更新第一天条边graph->adjLists[src] = newNode;如果是无向图，也需要添加反向边Node* newNode2 = (Node*)malloc(sizeof(Node));// Node* newNode2 = new Node;// newNode2->vertex = src;// newNode2->link = graph->adjLists[dest];// graph->adjLists[dest] = newNode2;
}// 深度优先遍历
void DFS(Graph *graph, int v)
{// 输出遍历到的节点cout << v << " ";// 递归访问所有未访问的邻接顶点// 第一个顶点Node *adjList = graph->adjLists[v];// 标记当前节点为已访问graph->isVisited[v] = true;while (adjList){// 邻接点未被访问到if (!graph->isVisited[adjList->vertex]){ // 递归调用 访问他的所有邻接点DFS(graph, adjList->vertex);}// 往后遍历每一条边adjList = adjList->next;}
}// 广度优先遍历 
void BFS(Graph* graph, int startVertex)
{// 初始化队列  queue <int> q;// / 标记所有顶点为未访问for(int i = 0; i < graph->numVertices ; ++i){graph->isVisited[i] = false;}      // 将起始顶点加入队列，并标记为已访问      q.push(startVertex);graph->isVisited[startVertex] = true;// 循环条件是队列不为空while (!q.empty()){// 从队列中取出第一个顶点int  vertex = q.front(); //出队    q.pop();// 访问该顶点 cout <<  "Visited " << vertex << endl;// 遍历访问的顶点的所有邻接点 Node* current  = graph->adjLists[vertex];while (current){ //邻接点 终点int adjVertex = current->vertex;// 如果邻接点未被访问，则加入队列并标记为已访问if(!graph->isVisited[adjVertex])  {q.push(adjVertex);graph->isVisited[adjVertex] = true;}// 移动到下一个邻接点 current = current->next;}}
}
// 清理Graph对象
void freeGraph(Graph *graph)
{if (!graph){return;}// 释放邻接表中每个链表占用的内存for (int i = 0; i < graph->numVertices; ++i){Node *current = graph->adjLists[i];while (current){Node *next = current->next; // 保存下一条边的指针delete current;             // 释放当前边的内存current = next;             // 移动到下一条边}}// 释放邻接表数组本身占用的内存delete[] graph->adjLists;// 释放访问标记数组占用的内存delete[] graph->isVisited;
}int main()
{// 创建一个包含4个顶点的图Graph *graph = createGraph(4);addEdge(graph, 0, 1);addEdge(graph, 0, 2);addEdge(graph, 1, 2);addEdge(graph, 2, 3);addEdge(graph, 2, 0);// 深度优先遍历图cout << "深度优先遍历（从顶点2开始）:" << endl;DFS(graph, 2);cout << endl;cout << "广度优先遍历（从顶点2开始）:" << endl;BFS(graph, 2);delete graph;graph = NULL;return 0;
}

  • 问题1：初始化的时候把顶点numVertices 初始化为0了而且创建时候没有再赋值，直接初始化传入节点就行了

  • 问题2 graph->isVisited[v] = true; 放在循环外面，那么下面访问了之后会再标记吗

    当然会，这是递归，会调用自己

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/news/904990.shtml
繁体地址，请注明出处：http://hk.pswp.cn/news/904990.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Ubuntu 第11章 网络管理_常用的网络配置命令

Ubuntu 第11章 网络管理_常用的网络配置命令

为了管理网络&#xff0c;Linux提供了许多非常有用的网络管理命令。利用这些命令&#xff0c;一方面可以有效地管理网络&#xff0c;另一方面出现网络故障时&#xff0c;可以快速进行诊断。本节将对Ubuntu提供的网络管理命令进行介绍。 11.2.1 ifconfig命令 关于ifconfig命令&…
阅读更多...
Qt解决自定义窗口样式不生效问题

Qt解决自定义窗口样式不生效问题

方法一&#xff1a; this->setAttribute(Qt::WA_StyledBackground, true); 方法二&#xff1a; 将类继承QWidget 改成继承 QFrame class MyWidget : public QFrame {} 方法三&#xff1a;重新实现QWidget的paintEvent函数时&#xff0c;使用QStylePainter绘制。 void p…
阅读更多...
HNUST湖南科技大学-软件测试期中复习考点（保命版）

HNUST湖南科技大学-软件测试期中复习考点（保命版）

使用说明&#xff1a;本复习考点仅用于及格保命。软件测试和其他专业课不太一样&#xff0c;记忆的太多了&#xff0c;只能说考试的时候&#xff0c;想到啥就写啥&#xff0c;多写一点&#xff01;多写一点&#xff01;多写一点&#xff01;&#xff08;重要事情说三遍&#xf…
阅读更多...
ES6 知识点整理

ES6 知识点整理

一、变量声明&#xff1a;var、let、const 的区别 作用域 var&#xff1a;函数作用域&#xff08;函数内有效&#xff09;。let/const&#xff1a;块级作用域&#xff08;{} 内有效&#xff0c;如 if、for&#xff09;。 变量提升 var 会提升变量到作用域顶部&#xff08;值为…
阅读更多...
分布式爬虫去重：Python + Redis实现高效URL去重

分布式爬虫去重：Python + Redis实现高效URL去重

1. 引言 在互联网数据采集&#xff08;爬虫&#xff09;过程中&#xff0c;URL去重是一个关键问题。如果不对URL进行去重&#xff0c;爬虫可能会重复抓取相同页面&#xff0c;导致资源浪费、数据冗余&#xff0c;甚至触发目标网站的反爬机制。 对于单机爬虫&#xff0c;可以使…
阅读更多...
C# WPF 颜色拾取器

C# WPF 颜色拾取器

x:Name=Color Picker 语言：C# WPF 下载：https://download.csdn.net/download/polloo2012/90780640 主界面 颜色库 关于我们 颜色拾取器是一种能够帮助用户获取颜色信息，并进行颜色选择、识别和调整的工具，以下将从其常见类型、使用场景及部分软件工具这几个维度展开介绍…
阅读更多...
Git 使用的全流程以及SourceTree工具的使用操作和忽略文件的配置

Git 使用的全流程以及SourceTree工具的使用操作和忽略文件的配置

1. 安装 Git 要使用 Git&#xff0c;首先得在你的系统上安装它。你可以按照不同操作系统的安装指南来操作&#xff1a; Windows&#xff1a;访问 Git 官方下载页面&#xff0c;下载安装程序并运行。 macOS&#xff1a;可以使用 Homebrew 来安装&#xff0c;命令为 brew inst…
阅读更多...
《深入理解Linux网络》笔记

《深入理解Linux网络》笔记

《深入理解Linux网络》笔记 前言参考 前言 前段时间看了《深入理解Linux网络》这本书&#xff0c;虽然有些地方有以代码充篇幅的嫌疑&#xff0c;但总体来说还是值得一看的。在这里简单记录一下笔记&#xff0c;记录下对网络新的理解。 内核是如果接受网络包的&#xff1f; 如…
阅读更多...
数仓-可累计，半累加，不可累加指标，是什么，举例说明及解决方案

数仓-可累计，半累加，不可累加指标，是什么，举例说明及解决方案

目录 1. 可累计指标定义&#xff1a;举例&#xff1a;解决方案&#xff1a; 2. 半累加指标定义&#xff1a;举例&#xff1a;解决方案&#xff1a; 3. 不可累加指标定义&#xff1a;举例&#xff1a;解决方案&#xff1a; 4. 总结对比5. 实际场景中的注意事项 这是数据仓库设计…
阅读更多...
NestJS 的核心构建块有哪些？请简要描述它们的作用（例如，Modules, Controllers, Providers）

NestJS 的核心构建块有哪些？请简要描述它们的作用（例如，Modules, Controllers, Providers）

NestJS 核心构建块解析&#xff08;Modules、Controllers、Providers&#xff09; NestJS 是一个基于 TypeScript 的渐进式 Node.js 框架&#xff0c;核心设计借鉴了 Angular 的模块化思想。下面从实际开发角度解析它的三大核心构建块&#xff0c;并附代码示例和避坑指南。 一…
阅读更多...
vue2 上传pdf，拖拽盖章，下载图片

vue2 上传pdf，拖拽盖章，下载图片

效果图片&#xff1a; 不多废话上代码&#xff1a; <template><div class"pdf-stamp" onbeforecopyreturn false onselectdocument.selection.empty() ondragstartreturn false onselectstart return false ><div class"scroll-box" scro…
阅读更多...
理性地倾听与表达：检索算法的语言学改进

理性地倾听与表达：检索算法的语言学改进

论文标题 Rational Retrieval Acts: Leveraging Pragmatic Reasoning to Improve Sparse Retrieval 论文地址 https://arxiv.org/pdf/2505.03676 代码地址 https://github.com/arthur-75/Rational-Retrieval-Acts 作者背景 巴黎萨克雷大学&#xff0c;索邦大学&#xff…
阅读更多...
MySQL及线程关于锁的面试题

MySQL及线程关于锁的面试题

目录 1.了解过 MySQL 死锁问题吗&#xff1f; 2.什么是线程死锁&#xff1f;死锁相关面试题 2.1 什么是死锁&#xff1a; 2.2 形成死锁的四个必要条件是什么&#xff1f; 2.3 如何避免线程死锁&#xff1f; 3. MySQL 怎么排查死锁问题&#xff1f; 4.Java线上死锁问题如…
阅读更多...
【Reality Capture 】Reality Capture1.5中文版安装教程（附安装包下载）

【Reality Capture 】Reality Capture1.5中文版安装教程（附安装包下载）

文章目录 一、Reality Capture1.5中文版安装教程二、拷贝中文补丁三、Reality Capture1.5中文版下载地址一、Reality Capture1.5中文版安装教程 1. Reality Capture v1.4.0汉化版安装包下载并解压 2. 运行EpicInstaller-15.17.1-4a91a118786f4c2aa3c0093b23f83863.msi 3. 更改…
阅读更多...
SVG数据可视化设计（AI）完全工作流解读｜计育韬

SVG数据可视化设计（AI）完全工作流解读｜计育韬

AI 的 SVG 创作极限在哪里&#xff1f;绝不是那些初级的流程图生成和粗糙的商业模型设计。以下是由我们 JZ Creative Studio 通过 Claude 和 Deepseek 开展的专业级 SVG Data Visualization 创作&#xff0c;应广大读者强烈要求&#xff0c;专程直播讲授了一期 AI 工作流分享。…
阅读更多...
not a genuine st device abort connection的问题

not a genuine st device abort connection的问题

1.魔法棒里面电机Settings 2.然后在Other里面把Enabled的钩子去掉
阅读更多...
uv简单使用

uv简单使用

通过uv创建项目和虚拟环境 初始化项目 uv init --package my-project 初始化一个名为 my-project 的新项目&#xff0c;并生成必要的文件结构。 创建虚拟环境 uv venv .venv 激活虚拟环境 # For Windows .venv\Scripts\activate# For macOS/Linux source .venv/bin/acti…
阅读更多...
测试左移系列-产品经理实战-实战认知1

测试左移系列-产品经理实战-实战认知1

课程&#xff1a;B站大学 记录产品经理实战项目系统性学习&#xff0c;从产品思维&#xff0c;用户画像&#xff0c;用户体验&#xff0c;增长数据驱动等不同方向理解产品&#xff0c;从0到1去理解产品从需求到落地的全过程&#xff0c;测试左移方向&#xff08;靠近需求、设计…
阅读更多...
从需求到用例的AI路径：准确率与挑战

从需求到用例的AI路径：准确率与挑战

用工作流生成测试用例和自动化测试脚本&#xff01; 引言&#xff1a;用例的黄金起点 在软件工程中&#xff0c;“测试用例”是连接需求理解与质量保障之间的关键桥梁。一份高质量的测试用例&#xff0c;不仅是验证功能实现是否符合需求的工具&#xff0c;更是产品风险感知、用…
阅读更多...
大语言模型中的“温度”参数到底是什么？如何正确设置？

大语言模型中的“温度”参数到底是什么？如何正确设置？

近年来&#xff0c;市面上涌现了大量调用大模型的工具&#xff0c;如 Dify、Cherry Studio 等开源或自研平台&#xff0c;几乎都提供了 “温度”&#xff08;Temperature&#xff09; 选项。然而&#xff0c;很多人在使用时并不清楚该如何选择合适的温度值。 今天&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023