//有向图判断是否有环
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
#define TRUE 1
#define FALSE 0
typedef struct{
int vexs[10];
int edges[10][10];
int n;
int e;
}MGraph;
void CreateGraphM(MGraph *G){
int N1,N2;
int i,j,k;
cout<<"Enter the number of vertexs and edges: "<<endl;
cin>>(G->n)>>(G->e);
k=G->n;
for(i=0;i<k;i++)
cin>>(G->vexs[i]);
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0;
cout<<"EDGES: "<<endl;
for(k=0;k<G->e;k++){
cin>>N1>>N2;
G->edges[N1-1][N2-1]=1;
}
return;
}
typedef struct{
int visited[10];
int finishing_time[10];
int discovery_time[10];
int times;
}DFS_DATA;
void DFSM(MGraph *G,int index,DFS_DATA *DATA){
DATA->times++;
DATA->discovery_time[index]=DATA->times;
DATA->visited[index]=1;
for(int i=0;i<G->n;i++)
if(G->edges[index][i]==1 && DATA->visited[i]==0){
DFSM(G,i,DATA);
}
DATA->finishing_time[index]=DATA->times;
DATA->times++;
}
void DFS(MGraph *G,DFS_DATA *DATA){
for(int i=0;i<G->n;i++){
DATA->visited[i]=0;
}
for(int i=0;i<G->n;i++){
DATA->finishing_time[i]=0;
DATA->discovery_time[i]=0;
}
DATA->times=0;
for(int i=0;i<G->n;i++){
if(DATA->visited[i]==0)
DFSM(G,i,DATA);
}
}
vector<int> Topological_Sort(MGraph *G){
DFS_DATA *DATA = new DFS_DATA;
vector<int> RESULT;
vector<int> tmp;
DFS(G,DATA);
for(int i=0;i<G->n;i++)
tmp.push_back(DATA->finishing_time[i]);
sort(tmp.begin(),tmp.end());
for(int i=G->n-1;i>=0;i--)
for(int j=0;j<G->n;j++)
if(DATA->finishing_time[j]==tmp[i]){
RESULT.push_back(j);
}
delete DATA;
return RESULT;
}
int Acyclic(MGraph *G){
vector<int> CHECK;
CHECK = Topological_Sort(G);
for(int i=1;i<G->n;i++)
for(int j=0;j<i;j++){
if(G->edges[CHECK[i]][CHECK[j]]==1)
return 1;
}
return 0;
}
int main()
{
MGraph *G = new MGraph;
CreateGraphM(G);
if(Acyclic(G)==1)
cout<<"There is Acyclic"<<endl;
else
cout<<"There is NO Acyclic"<<endl;
return 0;
}
先用DFS对图G拓扑排序 然后看 拓扑排序的结果有没冲突 就是 后面的顶点 要是有对前面顶点的边 有冲突 就表示有环
分享到:
相关推荐
AOV网,判断网中是否存在环 否则打印出拓扑序列
采用的方法是图的经典数据结构,若是有向无环图DAG则输出一个拓扑排序。若不是DAG则输出其中的一个环。
数据结构的作业…拓扑排序 判断有向图中的环并打印
利用拓扑排序判断有向图是否存在一个简单又向回路,若存在,输出该回路
基本要求:建立一个有向图,判断该图是否存在环,如果不存在环,输出它的拓扑有序序列;如存在环,给出存在环路的信息。 实验目的:利用所学C语言和数据结构的相关知识,输出有向网的拓扑排序序列。
题目:图的存储结构及拓扑排序 从键盘或文件读入有向图的顶点信息和弧信息(输入格式自拟); 建立有向图的十字链表存储结构; 利用拓扑排序方法判断该图是否为有向无环图。
以邻接矩阵给出一张以整数为结点的有向图,其中0表示不是相邻结点,1表示两个结点相连且由当前结点为初始点。利用拓扑排序判断图中是否有环,若有输出YES没有输出NO。 输入: 结点数邻接矩阵 输出: YES/NO
对给定的AOV网判断网中是否存在环,检测的办法是对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网中必定不存在环。在拓扑排序的基础上实现关键路径的的求解。
拓扑排序:对给定的AOV网判断网中是否存在环,检测的办法是对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网中必定不存在环。在拓扑排序的基础上实现关键路径的的求解。
判断给定的图是不是是有向无环图,方法是应用拓扑排序,代码如下
(1)以邻接表作为图的存储结构,从键盘输入图的顶点与弧的信息建立一个有向图; (2)对(1)中生成的有向图进行深度优先遍历并打印结果; (3)在(1)中生成的有向图中,分别插入与删除一条弧并打印其结果; (4)在(1...
( A ) 6、对一个有向图进行拓扑排序,一定可以将图的所有顶点按其关键码大小排列到一个拓 扑有序的序列中。(B ) 7、图的广度优先搜索算法通常采用递归算法求解。( B ) 8、当从一个小根堆(最小堆)中删除一个元素时...
邻接表法只能用于有向图的存储,而邻接矩阵法对于有向图和无向图的存储都适用。 ( ) 答:FALSE(邻接表也可存储无向图) 3.图的深度优先搜索序列和广度优先搜索序列不一定是唯一的。( ) 答:TRUE 4.有回路的图不能...
实现了图的多种存储方法,并实现了无向图的遍历,生成树,最小生成树,查找关节点;有向图的遍历,DAG判断,拓扑排序,关键路径,最短路径。
19.下面哪一方法可以判断出一个有向图是否有环(回路):【东北大学 2000 4、2(4分)】 A.深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径1).A.VT,ET为空 B.VT为所有顶点,ET为空 C.VT为网中任意...
图的深度优先和广度优先搜索(假设图用邻接表矩阵表示)、拓扑排序、判断是否有环 最短路径: : 邻接矩阵表示的图结构的最短路径 最小生成树: : 邻接矩阵表示的图结构的最小生成树 : 用并查集方法构造最小生成树 ...
比如求两数的最大公约数、素数的求法、判断longint范围内的数是否为素数(包含求50000以内的素数表)、寻找离生成树最近的未加入顶点k、按权值递增顺序删去图中的边,若不形成回路则将此边加入最小生成树、计算图的...
若不形成回路则将此边加入最小生成树、计算图的传递闭包、无向图的连通分量、拓扑排序,找入度为0的点,删去与其相连的所有边,不断重复这一过程,例寻找一数列,其中任意连续p项之和为正,任意q 项之和为负,若不...
| 有向图强连通分支(DFS/BFS 邻接阵)O(N^2) 8 | 有向图最小点基(邻接阵)O(N^2) 9 | FLOYD 求最小环 9 | 2-SAT 问题 9 Network 网络流 11 | 二分图匹配(匈牙利算法 DFS 实现) 11 | 二分图匹配(匈牙利算法 ...