判断有向图是否存在环的2种⽅法(深度遍历,拓扑排序)
此题是美团2017春招实习⽣在线笔试题,题⽬是“如何判断有向图有没有回路”,这⾥给出两种解法以供参考。
解法⼀:深度遍历
假设图以邻接矩阵表⽰,⼀条深度遍历路线中如果有结点被第⼆次访问到,那么有环。我们⽤⼀个变量来标记某结点的访问状态(未访问,访问过,其后结点都被访问过),然后判断每⼀个结点的深度遍历路线即可。
因为采⽤邻接矩阵存储,⼀般⾄少需要将矩阵中元素的⼀半给过⼀下,由于矩阵元素个数为n^2, 因此时间复杂度就是O(n^2)。如果采⽤邻接表存储,则只存储了边结点(e条边,⽆向图是2e条边),加上表头结点为n(也就是顶点个数),因此时间复杂度为O(n+e)。
Java实现如下:
import java.util.Scanner;
public class test2 {
//邻接矩阵
static int[][] graph =new int[200][200];
//结点个数和边的个数
static int vNum,eNum;
//标记矩阵,0为当前结点未访问,1为访问过,-1表⽰当前结点后边的结点都被访问过。
static int[] color =new int[200];
//是否是DAG(有向⽆环图)
static boolean isDAG =true;
//图的深度遍历函数
void DFS(int i){
System.out.println("正在访问结点"+i);
/
/结点i变为访问过的状态
color[i]=1;
for(int j=1;j<=vNum;j++){
//如果当前结点有指向的结点
if(graph[i][j]!=0){
//并且已经被访问过
if(color[j]==1){
isDAG =false;//有环
break;
}else if(color[j]==-1){
//当前结点后边的结点都被访问过,直接跳⾄下⼀个结点
continue;
}else{
DFS(j);//否则递归访问
}
}
}
//遍历过所有相连的结点后,把本节点标记为-1
color[i]=-1;
}
//创建图,以邻接矩阵表⽰
void create(){
Scanner sc =new Scanner(System.in);
System.out.println("正在创建图,请输⼊顶点个数vNum:");
vNum = sc.nextInt();
System.out.println("请输⼊边个数eNum:");
eNum = sc.nextInt();
//初始化邻接矩阵为0(如果3个顶点,顶点分别是1,2,3)
for(int i=1;i<=vNum;i++){
for(int j=1;j<=vNum;j++){
graph[i][j]=0;
}
}
/
/输⼊边的情况
System.out.println("请输⼊边的头和尾:");
for(int k=1;k<=eNum;k++){
for(int k=1;k<=eNum;k++){
int i = sc.nextInt();
int j = sc.nextInt();
graph[i][j]=1;
}
//初始化color数组为0,表⽰⼀开始所有顶点都未被访问过
for(int i=1;i<=vNum;i++){
color[i]=0;
}
}
public static void main(String[] args){
test2 t =new test2();
//保证每个节点都遍历到,排除有的结点没有边的情况
for(int i=1;i<=vNum;i++){
//该结点后边的结点都被访问过了,跳过它
if(color[i]==-1){
continue;
}
t.DFS(i);
if(!isDAG){
System.out.println("有环!");
break;
nextint()方法}
}
if(isDAG){
System.out.println("没环。。。");
}
}
}
测试输⼊输出如下:
正在创建图,请输⼊顶点个数vNum:
5
请输⼊边个数eNum:
5
请输⼊边的头和尾:
1 2
2 3
3 4
2 5
5 4
正在访问结点1
正在访问结点2
正在访问结点3
正在访问结点4
正在访问结点5
没环。。。
解法⼆:拓扑排序
⽅法是重复寻⼀个⼊度为0的顶点,将该顶点从图中删除(即放进⼀个队列⾥存着,这个队列的顺序就是最后的拓扑排序,具体见程序),并将该结点及其所有的出边从图中删除(即该结点指向的结点的⼊度减1),最终若图中全为⼊度为1的点,则这些点⾄少组成⼀个回路。
采⽤邻接矩阵存储时,遍历⼆维数组,求各顶点⼊度的时间复杂度是O(n^2)。 遍历所有结点,出⼊度为0的结点的时间复杂度是O(n)。对于n个⼊度为0的结点,删除他们的出边的复杂度为O(n^2)。 所以总的复杂度为O(n^2)。
对于邻接表,遍历所有边,求各顶点⼊度的时间复杂度是O(e),即边的个数。遍历所有结点,出⼊度为0的结点的时间复杂度是O(n),即顶点的个数。遍历所有边,删除⼊度为0的结点的出边的复杂度为O(e),即边的个数。所以总的时间复杂度是O(n+e)。
Java实现如下:
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Queue;
import java.util.Scanner;
public class test1 {
//邻接矩阵
static int[][] graph =new int[200][200];
//结点个数和边的个数
static int vNum,eNum;
//记录每个结点的⼊度,初始化为0
static int[] count =new int[200];
//⽤队列保存拓扑序列
static Queue<Integer> queue =new LinkedList<>();
//拓扑排序
void topoSort(){
//⼊度为0的结点的个数,也就是⼊队个数
int number =0;
//暂时存放拓扑序列
Queue<Integer> temp =new LinkedList<Integer>();
//遍历图中所有结点,⼊度为0的结点删除(放进队列)
for(int i=1;i<=vNum;i++){
if(count[i]==0){
queue.offer(i);
}
}
//删除这些被删除结点的出边(即对应结点⼊度减⼀)
while(!queue.isEmpty()){
int i = queue.peek();
temp.offer(queue.poll());
number++;
for(int j=1;j<=vNum;j++){
if(graph[i][j]==1){
count[j]-=1;
//出现了新的⼊度为0的结点,删除
if(count[j]==0){
queue.offer(j);
}
}
}
}
if(number != vNum){
System.out.println("最后存在⼊度为1的结点,这个有向图是有回路的。");
}else{
System.out.println("这个有向图不存在回路,拓扑序列为:"+ String()); }
}
//创建图,以邻接矩阵表⽰
void create(){
Scanner sc =new Scanner(System.in);
System.out.println("正在创建图,请输⼊顶点个数vNum:");
vNum = sc.nextInt();
System.out.println("请输⼊边个数eNum:");
eNum = sc.nextInt();
//初始化邻接矩阵为0(如果3个顶点,顶点分别是1,2,3)
for(int i=1;i<=vNum;i++){
for(int j=1;j<=vNum;j++){
graph[i][j]=0;
}
}
//输⼊边的情况
System.out.println("请输⼊边的头和尾:");
for(int k=1;k<=eNum;k++){
int i = sc.nextInt();
int j = sc.nextInt();
graph[i][j]=1;
graph[i][j]=1;
}
//计算每个结点的⼊度
Arrays.fill(count,0);//先初始化为0 for(int i=1;i<=vNum;i++){
for(int j=1;j<=vNum;j++){
if(graph[i][j]==1){
count[j]= count[j]+1;
}
}
}
}
public static void main(String[] args){ test1 t =new test1();
}
}
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论