时间戳

首页 > 解决方案 > 检查图是否有循环

java - 检查图是否有循环

问题描述

我有一个从 1 到 N 的 N 个顶点和 N 条边的有向图。边由数组 A 和 B 表示。要求是找出图是否为循环。如果可以从某个顶点开始并沿着提供的边访问所有其他边并返回起点，则图就是一个循环。

例子：

A={1,3,2,4}
B ={4,1,3,2}

2->3->1->4
^        |
|--------|

返回真，因为我们有一个循环。

例子：

    A={1,2,3,4}
    B ={2,1,4,3}
    
   1 <-> 2

   3 <-> 4

返回 false 因为我们没有循环。该图有 2 个不相交的循环，每个循环长度为 2

现在我可以创建一个以键为节点、以值为连接节点的映射。

static boolean process(int[] A, int[] B, int n) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            int a = A[i];
            int b = B[i];
            List<Integer> list = map.getOrDefault(a, new ArrayList<>());
            list.add(b);
            map.put(a, list);
        }
        System.out.println(map);
    }

现在如何识别循环？

标签： javaalgorithmgraphcycle

解决方案

您可以使用一个简单的int数组来保存您的地图。然后，正如 Vincent van der Weele 在他的评论中所说，这只是计算包含第一个元素的循环长度并检查它是否等于图的大小的问题。

static boolean process(int[] a, int[] b, int n) {

    int[] map = new int[n];
    for(int i=0; i<n; i++) {
        map[a[i]-1] = b[i]-1;
    }
    
    int len = 0;
    int curr = 0;
    do
    {
        curr = map[curr];
        len += 1;
    }
    while (curr != 0);
    
    return len == n;
}

测试：

System.out.println(process(new int[] {1,3,2,4}, new int[] {4,1,3,2}, 4));
System.out.println(process(new int[] {1,2,3,4}, new int[] {2,1,4,3}, 4));

输出：

true
false

推荐阅读