使用邻接矩阵在C ++上找到有向图中的所有循环的算法 [英] Algorithm for finding all cycles in a directed graph on C++ using Adjacency matrix

问题描述

给定图形邻接矩阵（例如对于g [] []），定向图形。
需要找到所有图周期的计数（如果存在）并打印它们。

我试图用Java编写这个算法，有时它的工作正常。如果图形有复杂的周期，算法返回疯狂的周期。请查看我的代码并帮助解决此问题。

  public static final int k = 6; 
 
 public static int g [] [] = {{0,1,0,0,0,0}，
 {1，0，1，0，0，0} 
 {0,0,0,1,0,0}，
 {0，0，0，0，1，0}，
 {0，0，1，0，0 ，0}，
 {0，0，0，0，0，0}}; 
 
 public static Vector stack = new Vector（）; 
 
 public static void printStack（）{
 System.out.print（stack is：{）; 
 for（int i = 0; i< stack.size（）; i ++）{
 System.out.print（stack.get（i）+）; 
} 
 System.out.println（};）; 
 
} 
 
 public static boolean checkCycle（）{
 boolean res = false; 
 
 for（int i = 0; i< stack.size（） -  1; i ++）{
 if（stack.get（i）.equals（stack.lastElement（）） ）{
 res = true; 
 break; 
} 
 
} 
 return res; 
} 
 
 public static boolean go_to_line（int line）{
 boolean res = false; 
 for（int i = 0; i  if（g [line] [i] == 1）{
 stack.add（i） 
 if（checkCycle（）== true）{
 System.out.println（Cycle found！）; 
 res = true; 
} else {
 res = go_to_line（i）; 
} 
} 
} 
 
 return res; 
} 
 
 public static int cycles_count（）{
 int res = 0; 
 
 for（int i = 0; i  if（g [i] [i] == 1）{
 System.out.println （在项{+ i +}！检测到结））; 
 res ++; 
} 
 
 for（int j = i + 1; j< k; j ++）{
 if（g [j] [i] == 1）{
 stack.add（j）; 
 stack.add（i）; 
 
 if（go_to_line（i）== true）{
 res ++; 
 
 System.out.print（Final）; 
 printStack（）; 
 stack.removeAllElements（）; 
} 
} 
} 
} 
 
 return res; 
} 
  

解决方案

一般情况。事情是，如果每个顶点连接到每个顶点，则所有图周期的计数大于 2 ^ n （节点的任何子集形成几个循环）。

因此在一般情况下没有好的算法。
要找到某个循环，您可以使用广度优先搜索。要找到所有循环，你应该使用强力算法。

Given graph adjacency matrix (for ex. g[][]), graph is directed. Needs find count of all graph cycles (if exists) and print them.

I tried to wrote this algorithm in Java, sometimes it works correctly. If graph has complex cycles, algorithm return crazy cycles. Please, look at my code and help to resolve this problem

public static final int k = 6;

public static int g[][] = { { 0, 1, 0, 0, 0, 0 },
                            { 1, 0, 1, 0, 0, 0 },
                            { 0, 0, 0, 1, 0, 0 },
                            { 0, 0, 0, 0, 1, 0 },
                            { 0, 0, 1, 0, 0, 0 },
                            { 0, 0, 0, 0, 0, 0 } };

public static Vector stack = new Vector();

public static void printStack() {
    System.out.print("stack is: { ");
    for (int i = 0; i < stack.size(); i++) {
        System.out.print(stack.get(i) + " ");
    }
    System.out.println("};");

}

public static boolean checkCycle() {
    boolean res = false;

    for (int i = 0; i < stack.size() - 1; i++) {
        if (stack.get(i).equals(stack.lastElement())) {
            res = true;
            break;
        }

    }
    return res;
}

public static boolean go_to_line(int line) {
    boolean res = false;
    for (int i = 0; i < k; i++) {
        if (g[line][i] == 1) {
            stack.add(i);
            if (checkCycle() == true) {
                System.out.println("Cycle found!");
                res = true;
            } else {
                res = go_to_line(i);
            }
        }
    }

    return res;
}

public static int cycles_count() {
    int res = 0;

    for (int i = 0; i < k; i++) {
        if (g[i][i] == 1) {
            System.out.println("Knot detected at item {" + i + "}!");
            res++;
        }

        for (int j = i + 1; j < k; j++) {
            if (g[j][i] == 1) {
                stack.add(j);
                stack.add(i);

                if (go_to_line(i) == true) {
                    res++;

                    System.out.print("Final ");
                    printStack();
                    stack.removeAllElements();
                }
            }
        }
    }

    return res;
}

解决方案

This problem has exponential complexity in the general case. The thing is that if each vertex is connected to each then the count of all graph cycles is more than 2^n (any subset of nodes forms several cycles).

Thus there is no good algorithm in the general case. To find some cycle you may use breadth-first search. To find all cycles you should use brute force algorithm.

这篇关于使用邻接矩阵在C ++上找到有向图中的所有循环的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！