欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

判断有向图是否有环&拓扑排序

程序员文章站 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拓扑排序 然后看 拓扑排序的结果有没冲突 就是 后面的顶点 要是有对前面顶点的边 有冲突 就表示有环
相关标签: J#