假设以邻接矩阵作为图的结构，编写算法，判别在给定的有向图中是否存在一个简单的有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）（注意：图中不存在顶点到自身的弧）

这是清华大学的考研试题。为了判断有向图是否存在环，可以通过深度优先搜索的方法来实现。从编号0的顶点出发，若两个顶点间存在路径，则记录下源顶点标记为已访问（标记为-1）。在遍历的过程中，若有顶点与源顶点相同，则说明存在环。

code:

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
using namespace std;
const int N = 100;
int G[N][N];
int path[N], visited[N], n, cycle;
int DFS(int u, int start)
{
	int i;
	visited[u] = -1;
	path[u] = start;
	for (i = 0; i < n;i++)
	{
		if (G[u][i]&&i!=start)
		{
			if (visited[i]<0)
			{
				cycle = u;
				return 0;

			}
			if (!DFS(i,u))
			{
				return 0;
			}
		}
	}
	visited[u] = 1;
	return 1;
}

void DisPath(int u)
{
	if (u<0)
	{
		return;
	}
	DisPath(path[u]);
	cout << " " << u;

}

void main()
{
	int i, j;
	cout << "请输入图中的顶点个数：" << endl;
	cin >> n;
	memset(G, 0, sizeof(G));
	cout << "请输入一个" << n << "*" << n << "矩阵（1表示存在弧，0表示不存在弧）：" << endl;
	for (i = 0; i < n;i++)
	{
		for (j = 0; j < n;j++)
		{
			cin >> G[i][j];
		}
	}
	cycle = -1;
	for (i = 0; i < n;i++)
	{
		if (!visited[i]&&!DFS(i,-1))
		{
			break;

		}
	}
	if (cycle<0)
	{
		cout << "不存在环!" << endl;
	} 
	else
	{
		cout << "存在环!" << endl;
		DisPath(cycle);
		cout << endl;
	}

	system("pause");
}

结果：

该算法创建4x4矩阵对应的有向图如下图所示

其中，a，b，c，d分别对应的编号为0，1，2，3，有向图有5条弧：<a,b> ,<a,c>,<b,c>,<b,d>和<d,a>，因此存在环a->b->d->a

 根据拓扑排序中是否所有点都入队（可形成拓扑序）来判断是否有回路

​
​
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
    queue<int>q;
    int cnt = 0;
    vector<int>indegree(1000,0);                //数组记录每个点的入度
    vector<int>Adj[1000];                              //邻接表
    int n,m;
    cin >> n>>m;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].push_back(v);
        indegree[v]++;                                       //计算每个点的入度
    }
    for (int i =1;i <= n; i++)
    {
        if (indegree[i] == 0)
        {
            q.push(i);                                        //初始化，将所有入度为0的点放入队列
        }
    }
    while (!q.empty())
    {
        int u = q.front();
        for (int j = 0; j < Adj[u].size(); j++)
        {
            indegree[Adj[u][j]]--;                        //将队首指向的点的入度减一
        }
        for (int j = 0; j <Adj[u].size(); j++)
        {
            if (indegree[Adj[u][j]]== 0 )
            {
                q.push(Adj[u][j]);                                       //更新队列
            }
        }
         q.pop();cnt++;                                        //队首元素弹出，记录个数
    }
    if (cnt < n)cout << "有环";                        //如果所有点均入过队列，则无环，否则有环
    else cout << "无环";
    return 0;
}

​

​

1. 拓扑排序的用处

对于有向图，我们有时候需要确保没有回路出现，如下面的例子：

学生学习的课程之间的优先关系构成了一个有向图，显然，该有向图不能出现回路，毕竟哪个学生也不想一直循环学习某几门课程不毕业。

P.s：这种用顶点表示活动，有向边表示活动之间的关系的有向图成为AOV网。

而拓扑排序的作用，就是帮我们判断一个有向图是否有回路出现。

2. 拓扑排序的思想

其实拓扑排序的思想很简单：

（1）在有向图中选择一个没有前驱（入度为0）的顶点输出；

（2）从图中删除该顶点和所有以它为尾的弧；

（3）重复（1）、（2）两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。

若所有顶点都被输出，则说明原有向图中没有回路；否则，说明有回路。

【举例】

3. 代码实现

代码实现也很简单，首先基于邻接表构造有向图，注意每个顶点结构体中需要加入一项int InDgree 表示该顶点的入度数（因为要把入度为0的顶点删除）。

我用的是栈来暂时存储删除的顶点，其实用队列或者别的容器都行，只是为了临时存储。

#include <iostream>
#include <stack>
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
using namespace std;
typedef char NumType;
typedef int Status;

//下面是邻接表构造有向图过程
struct ArcNode
{
    int AdjVex;
    ArcNode *NextArc;
};
struct VexNode
{
    NumType data;
    int InDegree;
    ArcNode *FirstArc;
};
struct ALGraph
{
    VexNode Vex[MAX_VERTEX_NUM];
    int VexNum;
    int ArcNum;
};
int Locate(ALGraph G,NumType v)
{
    int i;
    for(i=0;i<G.VexNum;i++)
        if(v==G.Vex[i].data)return i;
    return -1;
}
void CreatALGraph(ALGraph &G)
{
    cout<<"请输入顶点数和弧数："<<endl;
    cin>>G.VexNum;cin>>G.ArcNum;
    int i;
    cout<<"请输入顶点数据："<<endl;
    for(i=0;i<G.VexNum;i++)
    {
        cin>>G.Vex[i].data;
        G.Vex[i].FirstArc=0;
        G.Vex[i].InDegree=0;
    }
    NumType v1,v2;
    int j,k;
    cout<<"请输入弧："<<endl;
    for(k=0;k<G.ArcNum;k++)
    {
        cin>>v1;cin>>v2;
        i=Locate(G,v1);j=Locate(G,v2);
        G.Vex[j].InDegree++;
        ArcNode *p=new ArcNode();
        *p={j,G.Vex[i].FirstArc};
        G.Vex[i].FirstArc=p;
    }
}

//上面是用邻接表构造有向图
//下面是拓扑排序代码

void TopoLogicalSort(ALGraph G)
{
    ArcNode *p=0;
    stack<int> s;
    int i;
    for(i=0;i<G.VexNum;i++)
        if(G.Vex[i].InDegree==0)s.push(i);
    int t;
    int count0=0;
    while(!s.empty())
    {
        count0++;
        t=s.top();
        s.pop();
        cout<<G.Vex[t].data<<" ";
        for(p=G.Vex[t].FirstArc;p!=0;p=p->NextArc)
        {
            G.Vex[p->AdjVex].InDegree--;
            if(!G.Vex[p->AdjVex].InDegree)s.push(p->AdjVex);
        }
    }

    if(count0==G.VexNum){cout<<"YES";return;}
    cout<<"NO";
}
int main()
{
    ALGraph G;
    CreatALGraph(G);
    TopoLogicalSort(G);
    return 0;
}