判断一个有向图是否存在回路
发布时间
阅读量：
阅读量
判断一个有向图是否存在回路，除了采用拓扑算法以外，还可以使用深度优先搜索算法，本算法改编自“用邻接矩阵表示的深度优先搜索算法”，即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.输入输出样例如下
全部评论 (0)
还没有任何评论哟~