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

这是清华大学的考研试题。为了判断有向图是否存在环，可以通过深度优先搜索的方法来实现。从编号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

判断一个有向图是否存在回路，除了采用拓扑算法以外，还可以使用深度优先搜索算法，本算法改编自“用邻接矩阵表示的深度优先搜索算法”，即DFS算法，两者共同点均为递归调用,DFS算法已在注释中标出，可进行对比学习。loop函数无论是强连通图和非强连通图均能判断出是否存在回路。

在loop函数中
1.visited数组用于记录被访问过的节点，和DFS算法中的visited数组相同。
2.count数组只有一个元素即count[0]，初始值为1，若能找到回路,则count[0]=1；为什么用count[0]而不直接用int count变量？因为loop函数中要进行很多次递归调用，若用count变量，当形参改变时，实参的值并不能跟着改变，无法判断count的值是否改变。若是能找到回路，count[0]++只执行一次，即变为1.
3.形参source为源节点，以source为源节点，loop在遍历过程中是否能回到source节点,若能回到source节点，则存在回路。
4.形参s用于记录source节点，在loop函数不断递归过程中,source的值回不断的改变，无法知道源节点是哪个，故需要一个s来记录source 节点，s在递归过程中始终不变。

void loop(GraphMatrix *graphMatrix,int *visited,int source,int s,int *count)
{
    int j;
    visited[source]=1//源节点被遍历到，记录为1;
    for(j=0;j<graphMatrix->size;j++)
    {
        if(graphMatrix->graph[source][j]!=MAX&&j==s)//在每一次使用loop函数中，count[0]++其实只执行一次
        {   count[0]++;
            printf("%d",count[0]);
        }

        if(graphMatrix->graph[source][j]!=MAX&&!visited[j])//若有节点还为遍历到，则继续递归
            loop(graphMatrix,visited,j,s,count);
    }
}

/*void DFS(GraphMatrix*graphMatrix,int* visited,int source)
{
    int j;
    visited[source]=1;
    printf("%d",source)
    for(j=0;j<graphMatrix;j++)
    {
        if(graphMatrix->graph[soure][j]!=MAX&&!visited[j])
            DFS(graphMatrix,visited,j);
    }
}*/

完整代码如下

#include <stdio.h>
#include <stdlib.h>
#define MAX 0
typedef struct GRAPHMATRIX_STRU
{
    int size;
    int **graph;
}GraphMatrix;

GraphMatrix* InitGraph(int num)
{
    int i,j;
    GraphMatrix *graphMatrix=(GraphMatrix*)malloc(sizeof(GraphMatrix));
    graphMatrix->size=num;
    graphMatrix->graph=(int**)malloc(sizeof(int*)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
        graphMatrix->graph[i]=(int*)malloc(sizeof(int)*graphMatrix->size);
    for(i=0;i<graphMatrix->size;i++)
    {
        for(j=0;j<graphMatrix->size;j++)
        graphMatrix->graph[i][j]=MAX;

    }
    return graphMatrix;
}
void ReadMatrix(GraphMatrix*graphMatrix)
{
    int vex1,vex2;
    scanf("%d%d",&vex1,&vex2);
    while(vex1!=-1||vex2!=-1)
    {
        graphMatrix->graph[vex1][vex2]=1;
        scanf("%d%d",&vex1,&vex2);
    }

}
void loop(GraphMatrix *graphMatrix,int *visited,int source,int s,int *count)
{
    int j;
    visited[source]=1//源节点被遍历到，记录为1;
    for(j=0;j<graphMatrix->size;j++)
    {
        if(graphMatrix->graph[source][j]!=MAX&&j==s)//在每一次使用loop函数中，count[0]++其实只执行一次
        {   count[0]++;
            printf("%d",count[0]);
        }

        if(graphMatrix->graph[source][j]!=MAX&&!visited[j])//若有节点还为遍历到，则继续递归
            loop(graphMatrix,visited,j,s,count);
    }
}

/*void DFS(GraphMatrix*graphMatrix,int* visited,int source)
{
    int j;
    visited[source]=1;
    printf("%d",source)
    for(j=0;j<graphMatrix;j++)
    {
        if(graphMatrix->graph[soure][j]!=MAX&&!visited[j])
            DFS(graphMatrix,visited,j);
    }
}*/
int main()
{
    int num=7;//节点个数为7个，可将num改为输入方式，节点个数动态定义
    int i=0,j;
    int count[1]={0};//count[1]=0则不存在回路，count[1]=1则存在回路
    int *visited=(int*)malloc(sizeof(int)*num);
   GraphMatrix *graphMatrix;
   //初始化邻接矩阵
   graphMatrix=InitGraph(num);
   ReadMatrix(graphMatrix);
   //从0开始判断每一个节点是否能存在回路
   for(i=0;i<(graphMatrix->size);i++)
   {
       if(count[0]!=0)//若oount变为1，则已存在回路，不需要再进行下去了
       break;
       for(j=0;j<graphMatrix->size;j++)//每一次都 visited数组元素全部初始化，因为每次循环都是不同的源接待你
       {
           visited[j]=0;
       }
       loop(graphMatrix,visited,i,i,count);

   }
   if(count[0]==0)
    printf("0");
   return 0;
}

若存在回路则输出1，否则输出0.输入输出样例如下

目录

题目

拓扑排序的算法步骤

代码部分

小结

题目

拓扑排序的算法步骤

1. 求出所有顶点的入度，可以附设一个存放各顶点入度的数组indegree[]
2. 遍历数组indegree[],如果有顶点的入度为零，便将顶点依次入队或者入栈
3. 当栈或者队列不为空时，一直重复下面两个操作

             1）进行出栈或者出队的操作，这里假设操作顶点为v

             2）将与顶点v邻接的所有顶点的入度减一，如果出现入度为0的顶点，便进行入栈或者入队操作

      4. 若此时输出的顶点数小于有向图的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列

代码部分

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int indegree[100], vertexs[100][100];
char Data[100];
int main()
{
    queue<int> que;
    int m, n, i;
    char x, y;
    cin >> n >> m;
    for (i = 0; i < n; i++)  cin >> Data[i]; //存入顶点数据
    while (m--)
    {
        cin >> x >> y;
        vertexs[x - 'A'][y - 'A'] = 1;
        indegree[y - 'A']++; //计算每个顶点的入度
    }
    for (i = 0; i < n; i++)  if (!indegree[i])    que.push(i); //将入度为零的顶点编号入队
    int count = 0;       //计算拓扑序列的顶点数
    while (!que.empty())
    {
        int start = que.front();
        que.pop();
        count++; //相当于输出一个拓扑序列中的一个编号
        for (i = 0; i < n; i++)
        {
            if (vertexs[start][i])
            {
                vertexs[start][i] = 0;
                indegree[i]--;
                if (!indegree[i])    que.push(i);
            }
        }
    }
    if (count == n)    cout << "no"; //存在拓扑排序,即不存在回路
    else    cout << "yes"; //不存在拓扑排序，即存在回路
    return 0;
}

小结

主要代码的解释放在了代码块里面，仅供参考，有问题可以评论区交流，有问必答！！！