搜索
查看
编辑修改
首页
UNITY
NODEJS
PYTHON
AI
GIT
PHP
GO
CEF3
JAVA
HTML
CSS
搜索
我家自动化
这个屌丝很懒,什么也没留下!
关注作者
热门标签
jquery
HTML
CSS
PHP
ASP
PYTHON
GO
AI
C
C++
C#
PHOTOSHOP
UNITY
iOS
android
vue
xml
爬虫
SEO
LINUX
WINDOWS
JAVA
MFC
CEF3
CAD
NODEJS
GIT
Pyppeteer
article
热门文章
1
在Windows11系统中安装pyCharm Community_win11 pycharm安装
2
【转载】——KVM_cirros-0.3.4-x86_64-disk.img
3
【Codeforces】1120 Round #543 Div. 1 B-F简要题解_e. the very same munchhausen
4
Bat shell 脚本相关查询记录
5
js字符串转函数_js 字符串转函数
6
Vue3 第三十二篇:常用组件:Tab栏_vue3 tab
7
Python调用外部程序的9种方式,你都知道吗?_python启动其他程序
8
开源轻量堡垒机——Teleport的安装配置和使用_teleport radmin
9
Kafka系列之:Unexpected handshake request with client mechanism PLAIN, enabled mechanisms are []
10
编写一个完整的程序,运行时向用户提问“试考了多少分?(0~100)”输入后判断其等级显示出来。_运行时向用户提问你考试考了多少分
当前位置:
article
> 正文
判断有向图是否有环 、环的个数以及环中元素_判断有向图有几个环
作者:我家自动化 | 2024-02-06 21:10:51
赞
踩
判断有向图有几个环
判断有向图是否有环有三种方法:拓扑排序、深度遍历+回溯、深度遍历 + 判断后退边
这里使用 拓扑排序 和 深度遍历 + 回溯判断是不是环。使用 深度遍历 + 判断后退边找出环个数 以及环中元素
1、拓扑排序
思想:找入度为0的顶点,输出顶点,删除出边。循环到无顶点输出。
若:输出所有顶点,则课拓扑排序,无环;反之,则不能拓扑排序,有环
使用:可以使用拓扑排序为有向无环图每一个结点进行编号,拓扑排序输出的顺序可以为编号顺序
源代码:
[cpp] view plain
copy
#include <iostream>
using namespace std;
const int MAX_Vertex_Num = 20;
template<class VexType,class ArcType>
class MGraph
{
public:
void CreateGraph();//创建图
int LocateVex(VexType v);//返回顶点v所在顶点向量中的位置(下标)
void CheckCircle();
private:
VexType vexs[MAX_Vertex_Num];//顶点向量
ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //这里把邻接矩阵类型用模板表示,主要是为了处理有权值的情况,比如:权值可以为小数(代价),也可以为整数
int vexnum;//顶点数
int arcnum;//边数
private:
bool TopSort();
};
template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CreateGraph()
{
VexType first;
VexType Secend;
cout<<"请输入顶点数:";
cin>>vexnum;
cout<<"请输入边数:";
cin>>arcnum;
cout<<"请输入各个顶点值:";
for (int i=0;i<vexnum;i++)
{
cin>>vexs[i];
}
//初始化邻接矩阵
for (int i=0;i<arcnum;i++)
{
for (int j=0;j<arcnum;j++)
{
arcs[i][j]=0;
}
}
cout<<"请输入边的信息:"<<endl;
for (int i=0;i<arcnum;i++)
{
cin>>first>>Secend;
//如果边有权值的话,则还应该输入权值
int x = LocateVex(first);
int y = LocateVex(Secend);
arcs[x][y]=1;//如果是有权的话,这里应该是arc[x][y]=权值
}
}
/*
参数:v:表示顶点向量中一个值
函数返回值:函数返回v在顶点向量中的下标
*/
template<class VexType,class ArcType>
int MGraph<VexType,ArcType>::LocateVex(VexType v)
{
for (int i=0;i<vexnum;i++)
{
if (vexs[i]==v)
{
return i;
}
}
return -1;
}
/*
有向图可以拓扑排序的条件是:图中没有环。
具体方法:
⑴ 从图中选择一个入度为0的点加入拓扑序列。
⑵ 从图中删除该结点以及它的所有出边(即与之相邻点入度减1)。
*/
template<class VexType,class ArcType>
bool MGraph<VexType,ArcType>::TopSort()
{
int count = 0;//拓扑排序输出顶点的个数
int top = -1;
int stack[MAX_Vertex_Num];
int indegree[MAX_Vertex_Num]={0};
//求各个顶点的入度--邻接矩阵要查询该元素的列(记录入度情况)--
//如果是邻接表,就是麻烦在这里,查询结点入度很不方便
for (int i=0;i<vexnum;i++)
{
int num=0;
for (int j=0;j<vexnum;j++)
{
if (arcs[j][i]!=0)
{
num++;
}
}
indegree[i]=num;
}
//把入度为0的顶点入栈
for (int i=0;i<vexnum;i++)
{
if (!indegree[i])
{
stack[++top]=i;//顶点的下标
}
}
//处理入度为0的结点:把入度为0的结点出栈,删除与之有关的边
while (top>-1)
{
int x = stack[top--];
cout<<vexs[x];
count++;
//把与下标为x的顶点有关的边都去掉(出边),并改变对应结点的入度
for (int i=0;i<vexnum;i++)
{
if (arcs[x][i]!=0)
{
arcs[x][i]=0;//删除到下标为i的顶点的边,这时此顶点的入度减一
indegree[i]--;
if (!indegree[i])//顶点的入度为0,则入栈
{
stack[++top]=i;
}
}
}
}
cout<<endl;
if (count == vexnum) //能拓扑排序
{
return true;
}
return false;
}
/*
检查图中是不是有环
思想:
能进行拓扑排序,则无环,反之有环
*/
template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CheckCircle()
{
if (TopSort())
{
cout<<"无环!"<<endl;
}
else
{
cout<<"有环!"<<endl;
}
}
int main()
{
MGraph<char,int> G;
G.CreateGraph();
G.CheckCircle();
system("pause");
return 1;
}
测试:
有向图:
结果:
2、深度遍历 + 回溯
思想:用回溯法,遍历时,如果遇到了之前访问过的结点,则图中存在环。
代码:
[cpp] view plain
copy
#include <iostream>
using namespace std;
const int MAX_Vertex_Num = 20;
template<class VexType,class ArcType>
class MGraph
{
public:
void CreateGraph();//创建图
int LocateVex(VexType v);//返回顶点v所在顶点向量中的位置(下标)
bool CheckCircle();//检查图中有无环
private:
VexType vexs[MAX_Vertex_Num];//顶点向量
ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //这里把邻接矩阵类型用模板表示,主要是为了处理有权值的情况,比如:权值可以为小数(代价),也可以为整数
int vexnum;//顶点数
int arcnum;//边数
private:
void CheckCircle(int u,bool& isExist,bool visited[MAX_Vertex_Num],bool Isvisited[MAX_Vertex_Num]);
};
template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CreateGraph()
{
VexType first;
VexType Secend;
cout<<"请输入顶点数:";
cin>>vexnum;
cout<<"请输入边数:";
cin>>arcnum;
cout<<"请输入各个顶点值:";
for (int i=0;i<vexnum;i++)
{
cin>>vexs[i];
}
//初始化邻接矩阵
for (int i=0;i<arcnum;i++)
{
for (int j=0;j<arcnum;j++)
{
arcs[i][j]=0;
}
}
cout<<"请输入边的信息:"<<endl;
for (int i=0;i<arcnum;i++)
{
cin>>first>>Secend;
//如果边有权值的话,则还应该输入权值
int x = LocateVex(first);
int y = LocateVex(Secend);
arcs[x][y]=1;//如果是有权的话,这里应该是arc[x][y]=权值
}
}
/*
参数:v:表示顶点向量中一个值
函数返回值:函数返回v在顶点向量中的下标
*/
template<class VexType,class ArcType>
int MGraph<VexType,ArcType>::LocateVex(VexType v)
{
for (int i=0;i<vexnum;i++)
{
if (vexs[i]==v)
{
return i;
}
}
return -1;
}
/*
思想:用回溯法,遍历时,如果遇到了之前访问过的结点,则图中存在环。
引入visited数组的原因:
1)在一次深度遍历时,检测路径上是否结点是否已经被检测到,如果被重复检测,则表示有环。
2)注意,在深度递归返回时,总是要把visited置为false。
引入Isvisited数组的原因:
1)用于记录目前为止深度遍历过程中遇到的顶点。
2)因为,我们不一定以所有结点为起始点都进行一次深度遍历。
3)举例,在结点A为起点,进行深度遍历时,遇到了结点B,此时Isvisited在A和B两个位置都为true。
那么没遇到环,那么我们就不用再以B为起始点继续进行一次深度遍历了,
因为A为起点的深度遍历已经验证不会有环了。
*/
template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CheckCircle(int u,bool& isExist,bool visited[MAX_Vertex_Num],bool Isvisited[MAX_Vertex_Num])
{
visited[u]=true;
Isvisited[u]=true;
for (int j=0;j<vexnum;j++)
{
if (arcs[u][j]==1)
{
if (visited[j]==false)
{
CheckCircle(j,isExist,visited,Isvisited);
}
else
{
isExist = true;
}
}
}
visited[u]=false;//回溯,如果不写就变成一半的深度遍历,不能进行判断是否有边存在
}
template<class VexType,class ArcType>
bool MGraph<VexType,ArcType>::CheckCircle()
{
bool isExist = false;
bool Isvisited[MAX_Vertex_Num]={false};
bool visited[MAX_Vertex_Num]={false};
for (int i=0;i<vexnum;i++)
{
if (Isvisited[i]==false)
{
CheckCircle(i,isExist,visited,Isvisited);
if (isExist)
{
return true;
}
}
}
return isExist;
}
int main()
{
MGraph<char,int> G;
G.CreateGraph();
if (G.CheckCircle())
{
cout<<"图存在环!"<<endl;
}
else
{
cout<<"图不存在环!"<<endl;
}
system("pause");
return 1;
}
结果测试:
图:
结果:
3、深度遍历 + 判断后退边
思想:用DFS(深度优先遍历),判断是否有后退边,若有,则存在环
具体来说,在遍历顶点的每一条边时,判断一下这个边的顶点是不是在栈中,如果在栈中,说明之前已经访问过了,这里再次访问,说明有环存在
判断后退边时,借助一个栈和一个数组
栈:即可以用来输出环
数组:inStack判断是否在栈中
源代码:
[cpp] view plain
copy
#include <iostream>
using namespace std;
const int MAX_Vertex_Num = 20;
template<class VexType,class ArcType>
class MGraph
{
public:
void CreateGraph();//创建图
int LocateVex(VexType v);//返回顶点v所在顶点向量中的位置(下标)
void CheckCircle();
private:
VexType vexs[MAX_Vertex_Num];//顶点向量
ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //这里把邻接矩阵类型用模板表示,主要是为了处理有权值的情况,比如:权值可以为小数(代价),也可以为整数
int vexnum;//顶点数
int arcnum;//边数
private:
void DFS(int x,bool visited[MAX_Vertex_Num],int stack[MAX_Vertex_Num],int& top,bool inStack[MAX_Vertex_Num],int& count);
};
template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CreateGraph()
{
VexType first;
VexType Secend;
cout<<"请输入顶点数:";
cin>>vexnum;
cout<<"请输入边数:";
cin>>arcnum;
cout<<"请输入各个顶点值:";
for (int i=0;i<vexnum;i++)
{
cin>>vexs[i];
}
//初始化邻接矩阵
for (int i=0;i<arcnum;i++)
{
for (int j=0;j<arcnum;j++)
{
arcs[i][j]=0;
}
}
cout<<"请输入边的信息:"<<endl;
for (int i=0;i<arcnum;i++)
{
cin>>first>>Secend;
//如果边有权值的话,则还应该输入权值
int x = LocateVex(first);
int y = LocateVex(Secend);
arcs[x][y]=1;//如果是有权的话,这里应该是arc[x][y]=权值
}
}
/*
参数:v:表示顶点向量中一个值
函数返回值:函数返回v在顶点向量中的下标
*/
template<class VexType,class ArcType>
int MGraph<VexType,ArcType>::LocateVex(VexType v)
{
for (int i=0;i<vexnum;i++)
{
if (vexs[i]==v)
{
return i;
}
}
return -1;
}
/*
检查图中是不是有回向边
思想:
如果有回向边,则无环,反之有环
*/
template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::CheckCircle()
{
int count=0;//环的个数
int top=-1;
int stack[MAX_Vertex_Num];
bool inStack[MAX_Vertex_Num]={false};
bool visited[MAX_Vertex_Num]={false};
for (int i=0;i<vexnum;i++)
{
if (!visited[i])
{
DFS(i,visited,stack,top,inStack,count);
}
}
}
template<class VexType,class ArcType>
void MGraph<VexType,ArcType>::DFS(int x,bool visited[MAX_Vertex_Num],int stack[MAX_Vertex_Num],int& top,bool inStack[MAX_Vertex_Num],int& count)
{
visited[x]=true;
stack[++top]=x;
inStack[x]=true;
for (int i=0;i<vexnum;i++)
{
if (arcs[x][i]!=0)//有边
{
if (!inStack[i])
{
DFS(i,visited,stack,top,inStack,count);
}
else //条件成立,表示下标为x的顶点到 下标为i的顶点有环
{
count++;
cout<<"第"<<count<<"环为:";
//从i到x是一个环,top的位置是x,下标为i的顶点在栈中的位置要寻找一下
//寻找起始顶点下标在栈中的位置
int t=0;
for (t=top;stack[t]!=i;t--);
//输出环中顶点
for (int j=t;j<=top;j++)
{
cout<<vexs[stack[j]];
}
cout<<endl;
}
}
}
//处理完结点后,退栈
top--;
inStack[x]=false;
}
int main()
{
MGraph<char,int> G;
G.CreateGraph();
G.CheckCircle();
system("pause");
return 1;
}
结果测试:
有向图:
结果:
来源:http://blog.csdn.net/insistgogo/article/details/6978718
声明:
本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:
https://www.wpsshop.cn/w/我家自动化/article/detail/64585
推荐阅读
article
ubuntu
mysql8
_如何在
Ubuntu
Linux上
安装
MySQL
8.0
.11...
继
MySQL
5.7之后,直接跳到了
MySQL
8.0
,官方说这次来了个大升级,其他的不说,就访问速度是5.7的2倍,因...
赞
踩
article
Nature
:
当AI遇见
量子
计算
,
会
引发
科学
革命吗?...
来源
:
学术头条我们可以将其称为未来
计算
的复仇者联盟。将两个科技界最热门的术语——机器学习和
量子
计算
机结合起来
,
就形成了量...
赞
踩
article
虚拟机
Windows
Server
2016 安装
MySQL8
...
在虚拟机
Windows
Server
2016 中 安装
MySQL8
.0 并通过本机Navicat远程连接虚拟机Wind...
赞
踩
article
【
算法
修炼】
图
论
算法
一(
图
的表示、
图
的
遍历
、
图
中
环
的检测)_
多叉树
判断
环
...
学习自:https://labuladong.gitee.io/algo/2/19/35/终于开始了数据结构
算法
的学习…...
赞
踩
article
深度
学习
驱动下
的
自然语言
处理
进展及其
应用
前景...
自然语言
处理
(NLP)是一项正在迅速发展
的
技术,它利用
深度
学习
和大数据技术,让计算机能够更好地理解和生成人类语言。随着N...
赞
踩
article
竞赛
图
三元
环
期望
个数...
题意给定\(n\)个点的
竞赛
图,有\(m\)条边的方向是确定的,剩下的边方向不确定,问
期望
三元
环个数题解如果一个点\(u...
赞
踩
article
2014年
蓝桥
杯
c
/
c
++B组省赛真题解析_
十四届
蓝桥
杯
c
++
b
题解...
一、啤酒和饮料啤酒每罐2.3元,饮料每罐1.9元。小明买了若干啤酒和饮料,一共花了82.3元。我们还知道他买的啤酒比饮料...
赞
踩
article
Kubernetes
- 如何利用 K8S
拉取
私有
仓库
镜像
...
Kubernetes
- 如何利用 K8S
拉取
私有
仓库
镜像
Kubernetes
- 如何利用 K8S
拉取
私有
仓库
镜像
...
赞
踩
article
第十四届
蓝桥
杯省赛
Python
B 组 D 题——
管道
(AC)_
第十四届
蓝桥
杯大赛软件
赛省赛
pyt...
第十四届
蓝桥
杯省赛
Python
B 组 D 题——
管道
(AC)_
第十四届
蓝桥
杯大赛软件
赛省赛
pythonb
第十四届
蓝桥
...
赞
踩
article
龟兔
赛跑
编程
c
语言蓝桥
,
蓝桥杯
BASIC
24
龟兔
赛跑
预測(
模拟
)(示例代码)...
【思路】:
模拟
。注意一个是在兔子歇息的时间乌龟可能到达了。刚開始没考虑WA80%。【AC代码】:#in
c
lude #in...
赞
踩
article
射线
与
三角形
求交...
射线
与
三角形
求交 在几何选取、碰撞检测上 经常会用到,在计算机图形学上是最初级的应用。 问题的由来 来自三维场景的鼠标...
赞
踩
article
十四届
蓝桥
杯青少组选拔赛
Python
_202
3
.0
3
.12_202
3
年
3
月
蓝桥
杯
python
真题...
十四届
蓝桥
杯青少组选拔赛
Python
_202
3
.0
3
.12_202
3
年
3
月
蓝桥
杯
python
真题202
3
年
3
月
蓝桥
杯...
赞
踩
article
ubuntu20.04
安装
mysql8.0
...
1、直接使用终端工具安装。sudo apt-get updatesudo apt-get upgradesudo apt...
赞
踩
article
教你怎么
短期内
备考
并
通过
PMP
考试
!_
pnp
替考...
一般
PMP
的准
备考
试时间都是三个月之内的,即从你开始准备想要去报考
PMP
认证开始,到你临考,时间上一般都是在三个月之内。...
赞
踩
article
PTA
|C
语言
:龟兔
赛跑
_
c
语言
乌龟
与
兔子
赛跑
...
7-4 龟兔
赛跑
(20 分)
乌龟
与
兔子
进行
赛跑
,跑场是一个矩型跑道,跑道边可以随地进行休息。
乌龟
每分钟可以前进3米,兔...
赞
踩
article
盘点对比美英
与
我国
数据
科学
教育
战略
、
现状...
如今,全球正在加速从IT时代迈向DT时代,越来越多的国家推出发展
战略
,期望通过建立大
数据
竞争优势,巩固其在该领域的领先地...
赞
踩
article
蓝桥
杯
龟
兔
赛跑
预测
Python
(超详细!!)...
蓝桥
杯
龟
兔
赛跑
预测
Python
问题描述(简单描述)
龟
兔
赛跑
,跑道长l米,如果
兔
子比乌
龟
快t米,
兔
就会停下来休息s秒,有一...
赞
踩
article
CrossOver
软件
2022可以使苹果MAC电脑
运行
Windows
软件
应用_
crossover
m...
CrossOver
软件
2022可以使苹果MAC电脑
运行
Windows
软件
应用_
crossover
mac
crossove...
赞
踩
article
人工智能
大脑
模拟
_
认知
模拟
是指
使用
心理学
实验
的
结果...
大脑
模拟
主条目:控制论和计算神经科学20世纪40年代到50年代,许多研究者探索神经病学,信息理论及控制论之间
的
联系。其中...
赞
踩
article
蓝桥
青少年
组——
计算
24
2020-11-25_“
计算
24
”是
一个
流传已久
的
数字
游戏
,...
蓝桥
青少年
组——
计算
24
【编程实现】“
计算
24
"是
一个
流传已久
的
数字
游戏
,小蓝最近对此痴迷不已。
游戏
规则是:对4个1~1...
赞
踩
相关标签
ubuntu mysql8
量子计算
人工智能
mysql
windows
算法
图论
数据结构
深度学习
自然语言处理
数据结构与算法
蓝桥杯c/c++
省赛真题
kubernetes
容器
云原生
拉取
私有镜像
仓库
Image
蓝桥杯
python
职场和发展
c++
java