判断有向图是否有环&拓扑排序
程序员文章站
2022-03-09 20:47:20
...
//有向图判断是否有环
#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拓扑排序 然后看 拓扑排序的结果有没冲突 就是 后面的顶点 要是有对前面顶点的边 有冲突 就表示有环
上一篇: 就地堆排序