数据结构-图的遍历

ops/2024/11/25 20:45:50/

一.深度优先搜素

遍历：把图中的每一个顶点访问一遍

把自己所能看见灯任意点亮然后依次进行点亮操作,当自己所能看见的灯全都被点亮，也不能直接从节点退出，而是回退然后继续进行上述操作

当所有的灯都被点亮了,一定要原路返回直到返回到出口再出去

二.广度优先搜索

BFS与二叉树的层次遍历相似,需要先指定一个起点，然后将起始点压入队列然后进入队列循环,弹出来的时候就顺序的把直接跟它有边相连的这些点一 一的压入队列,然后以此类推

三. 为什么需要两种遍历

因为只有一种遍历方式并不能很好解决所有的问题

四.图不连通的情况

从V到v1到v2到W之间有一条路径,有回环路的路径称为副复杂路径

邻接表存储的图-遍历

#include<iostream>
using namespace std;
#define MaxVertenNum 100/*最大顶点数设为100*/
typedef int Vertex;/*用顶点下标表示顶点为整形*/
typedef int WeightType;/*顶点存放的数据类型设为字符型*/
typedef char DataType;/*顶点存放的数据类型设为字符型*/
#include<queue>
bool Visited[MaxVertenNum] = { false };/*用来表示这个顶点是否被访问过了*/
/*定义边*/
typedef struct ENode* PtrToENode;
struct ENode
{Vertex V1, V2;/*有向图<v1,v2>*/WeightType Weight;/*权重*/
};
typedef  PtrToENode Edge;
/*邻接点的顶点*/
typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode
{Vertex Adjx;/*邻接点下标*/WeightType Weight;/*边权重*/PtrToAdjVNode Next;/*指向下一个邻接点*/
};
typedef struct Vnode {PtrToAdjVNode FirstEdge;/*边表头指针*/DataType Data;/*存储结点的数据*/
}AdjList[MaxVertenNum];/*是*//*图结点的定义*/
typedef struct GNode* PtrToGNode;
typedef struct GNode {int Nv;/*顶点数*/int Ne;/*边数*/AdjList G;/*邻接表*/
};
typedef PtrToGNode LGraph;/*邻接表方式存储*/
LGraph CreateGraph(int VertexNum) {/*初始化一个有VN个顶点没有边的图*/Vertex V;LGraph Graph;Graph = new GNode();Graph->Nv = VertexNum;Graph->Ne = 0;for (V = 0; V < Graph->Nv; V++) {Graph->G[V].FirstEdge = NULL;}return Graph;
}
void InsertEdge(LGraph Graph, Edge E) {PtrToAdjVNode NewNode;/* 插入边 <V1, V2> *//* 为V2建立新的邻接点 */NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->Adjx = E->V2;/* 将V2插入V1的表头 */NewNode->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = NewNode;/* 若是无向图，还要插入边 <V2, V1> *//* 为V1建立新的邻接点 */NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->Adjx = E->V1;/* 将V1插入V2的表头 */NewNode->Next = Graph->G[E->V2].FirstEdge;Graph->G[E->V2].FirstEdge = NewNode;}
LGraph BuildGraph() {LGraph Graph;Edge E;Vertex V;int Nv, i;cin >> Nv;Graph = CreateGraph(Nv);cin >> Graph->Ne;if (Graph->Ne != 0) {E = new ENode();for (int i = 0; i < Graph->Ne; i++) {cin >> E->V1 >> E->V2;InsertEdge(Graph, E);}}return Graph;
}
void BFS(LGraph Graph ,Vertex V) {PtrToAdjVNode W;cout << V << endl;Visited[V] = true;queue<Vertex>q;q.push(V);while (!q.empty()) {V = q.front();q.pop();for (W = Graph->G[V].FirstEdge; W; W = W->Next) {if (!Visited[W->Adjx] ) {cout << W->Adjx << endl;;Visited[W->Adjx] = true;q.push(W->Adjx);}}}}
void DFS(LGraph Graph, Vertex V) {cout << V << endl;PtrToAdjVNode W;Visited[V] = true;for (W = Graph->G[V].FirstEdge; W; W = W->Next) {if (Visited[W->Adjx] == false){DFS(Graph,W->Adjx);}}
}
void ListComponents(LGraph G) {for (int V = 0; V< G->Nv; V++) {//for (V = G->G[i].FirstEdge; V; V = V->Next)if (!Visited[V])DFS(G,V);}}
int main()
{//LGraph Graph = BuildGraph();LGraph Graph = CreateGraph(6);Graph->Ne = 8;Vertex a[8] = { 0,0,0,1,1,3,2,3 };Vertex b[8] = { 1,2,4,3,4,4,5,5 };/* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */for (int i = 0; i < Graph->Ne; i++) {Edge E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */E->V1 = a[i]; E->V2 = b[i];/* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge(Graph, E);}for (int i = 0; i < MaxVertenNum; i++) { Visited[i] = false; }cout << "BFS:" << endl;BFS(Graph, 0);for (int i = 0; i < MaxVertenNum; i++) { Visited[i] = false; }cout << "_________________________" << endl;cout << "DFS:" << endl;DFS(Graph, 0);for (int i = 0; i < MaxVertenNum; i++) { Visited[i] = false; }cout << "_________________________" << endl;LGraph G = CreateGraph(8);G->Ne = 8;Vertex d[8] = { 0,0,0,1,1,5,6,5 };Vertex e[8] = { 1,2,4,3,4,6,7,7 };for (int i = 0; i < Graph->Ne; i++) {Edge E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */E->V1 = d[i]; E->V2 = e[i];/* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge(G, E);}ListComponents(G);return 0;
}

邻接矩阵存储的图-遍历

#include<iostream>
#include<queue>
using namespace std;
#define INFINITY 65535;/*表示无穷大*/
typedef int Vertex;/*用顶点下标表示顶点*/
typedef int WeightType;/*边的权值设为整形*/
typedef char DataType;/*ing的存储的数据类型设为字符型*/
#define MaxVertexNum 1000
bool Visited[MaxVertexNum] = { false };
/*边的定义*/
typedef struct ENode* PtrToENode;
struct ENode
{Vertex V1, V2;WeightType Weight;//权重
};
typedef PtrToENode Edge;
/*图节点的定义*/
typedef struct GNode* PtrToGNode;
struct GNode
{int Nv;//顶点个数int Ne;//边数WeightType G[MaxVertexNum][MaxVertexNum];//邻接矩阵
};
typedef PtrToGNode MGraph;/*以邻接矩阵存储图*/
MGraph CreateCraph(int VertexNum) {/*初始化一个有VN个顶点但没有边的图*/Vertex V, W;MGraph G = new GNode();G->Nv = VertexNum;G->Ne = 0;for (V = 0; V < G->Nv; V++)for (W = 0; W < G->Nv; W++)G->G[V][W] = INFINITY;return G;
}
void InsertEdge(MGraph Graph, Edge E) {Graph->G[E->V1][E->V2] = 1;/*若是无向图还行要插入<V2,V1>*/Graph->G[E->V2][E->V1] = 1;
}
MGraph BuildGraph() {MGraph Graph;Edge E;Vertex V;int Nv;cin >> Nv;Graph = CreateCraph(Nv + 1);cin >> Graph->Ne;if (Graph->Ne != 0) {E = new ENode();for (int i = 0; i < Graph->Ne; i++) {cin >> E->V1 >> E->V2;InsertEdge(Graph, E);}}return Graph;
}
void DFS(MGraph Graph, Vertex V) {Vertex W;cout << V << endl;Visited[V] = true;for (W = 0; W < Graph->Nv; W++)if ((!Visited[W]) && (Graph->G[V][W] == 1))DFS(Graph, W);
}
void BFS(MGraph Graph, Vertex S) {Vertex V, W;cout << S << endl;queue<Vertex>q;Visited[S] = true;q.push(S);while (!q.empty()) {V = q.front();q.pop();for(W=0;W<Graph->Nv;W++)if (!Visited[W] && Graph->G[V][W] == 1) {cout << W << endl;Visited[W] = true;q.push(W);}}
}
void ListComponents(MGraph G) {//for (int V = 0; V < G->Nv; V++) {for (int W = 0; W < G->Nv; W++) {if (!Visited[W] )//DFS(G,W);BFS(G, W);}//}
}
int main()
{MGraph Graph = CreateCraph(6);Graph->Ne = 8;Vertex a[8] = { 0,0,0,1,1,3,2,3 };Vertex b[8] = { 1,2,4,3,4,4,5,5 };/* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */for (int i = 0; i < Graph->Ne; i++) {Edge E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */E->V1 = a[i]; E->V2 = b[i];/* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge(Graph, E);}for (int i = 0; i < MaxVertexNum; i++) { Visited[i] = false; }cout << "DFS" << endl;DFS(Graph, 0);cout << "________________" << endl;for (int i = 0; i < MaxVertexNum; i++) { Visited[i] = false; }cout << "BFS" << endl;BFS(Graph, 0);cout << "________________" << endl;for (int i = 0; i < MaxVertexNum; i++) { Visited[i] = false; }MGraph G = CreateCraph(8);G->Ne = 8;Vertex d[8] = { 0,0,0,1,1,5,6,5 };Vertex e[8] = { 1,2,4,3,4,6,7,7 };for (int i = 0; i < Graph->Ne; i++) {Edge E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */E->V1 = d[i]; E->V2 = e[i];/* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge(G, E);}ListComponents(G);}


http://www.ppmy.cn/ops/136661.html

相关文章

C++之旅-set和map掌握篇

C++之旅-set和map掌握篇

目录 前言 1.set的使用 1.1set类的介绍 1.2 set的构造和迭代器 1.3 set的增删查 1.4 代码练习 1.4.1 set的构造&#xff0c;插入与删除 1.4.2 set 的find的使用样例&#xff0c;与erase结合 1.4.3 set获取区间值函数的应用 1.5 multiset和set的差异 1.6 set强化练习&…
阅读更多...
什么是反向 DNS 查找以及它的作用是什么？

什么是反向 DNS 查找以及它的作用是什么？

反向DNS查询&#xff08;rDNS&#xff09;是一种技术&#xff0c;用于确定与某个IP地址对应的域名。当我们对一个IP地址进行反向DNS查询时&#xff0c;实际上是向域名系统&#xff08;DNS&#xff09;的特殊部分请求信息&#xff0c;这部分被称为PTR记录。PTR记录会返回与这个I…
阅读更多...
基于Multisim的汽车尾灯控制电路设计与仿真

基于Multisim的汽车尾灯控制电路设计与仿真

1、电路由四个按键控制&#xff0c;分别对应左转、右转、刹车和检查。 2、当左转或右转键按下时,左侧或右侧的 3个汽车尾灯按照左循环或右循环的顺!2/3 点亮&#xff0c;点亮时间为 1秒。 3、当刹车时&#xff0c;所有的尾灯同时闪烁&#xff0c;闪烁时间为1秒。 4、当检查时…
阅读更多...
Qt-容器类控件 布局管理器

Qt-容器类控件 布局管理器

容器类控件 之前学过的多元素控件&#xff0c;它里面包含的内容是一个一个自定义好的 “Item”对象。 而容器类控件&#xff0c;里面包含的就是之前学过的各种控件了&#xff0c;比如QPushButton&#xff0c;QLineEdit等等。 QGroup Box 使⽤ QGroupBox 实现⼀个带有标题的…
阅读更多...
RabbitMQ 之 死信队列

RabbitMQ 之 死信队列

一、死信的概念 先从概念解释上搞清楚这个定义&#xff0c;死信&#xff0c;顾名思义就是无法被消费的消息&#xff0c;字面意思可以这样理 解&#xff0c;一般来说&#xff0c;producer 将消息投递到 broker 或者直接到 queue 里了&#xff0c;consumer 从 queue 取出消息进行…
阅读更多...
Lucene(2):Springboot整合全文检索引擎TermInSetQuery应用实例附源码

Lucene(2):Springboot整合全文检索引擎TermInSetQuery应用实例附源码

前言 本章代码已分享至Gitee: https://gitee.com/lengcz/springbootlucene01 接上文。Lucene(1):Springboot整合全文检索引擎Lucene常规入门附源码 如何在指定范围内查询。从lucene 7 开始&#xff0c;filter 被弃用&#xff0c;导致无法进行调节过滤。 TermInSetQuery 指定…
阅读更多...
cookie反爬----普通服务器，阿里系

cookie反爬----普通服务器，阿里系

目录 一.常见COOKIE反爬 普通&#xff1a; 1. 简介 2. 加密原理 二.实战案例 1. 服务器响应cookie信息 1. 逆向目标 2. 逆向分析 2. 阿里系cookie逆向 1. 逆向目标 2. 逆向分析 实战&#xff1a; 无限debugger原理 1. Function("debugger").call() 2. …
阅读更多...
postman 调用 下载接口（download）使用默认名称（response.txt 或随机名称）

postman 调用 下载接口（download）使用默认名称（response.txt 或随机名称）

官网地址&#xff1a;https://www.postman.com 介绍 Postman 是一款流行的 API 开发和测试工具&#xff0c;用于发送 HTTP 请求、测试接口、调试服务器响应以及进行 API 文档管理。它支持多种请求类型&#xff08;如 GET、POST、PUT、DELETE 等&#xff09;&#xff0c;并且功能…
阅读更多...
最新文章

Copyright @ 2022~2023