Печать ребер цикла в неориентированном графике

Question

У меня есть неориентированный граф, который загружается как матрица смежности. У меня есть метод для обнаружения цикла на графике с использованием алгоритма BFS. Я пытаюсь добиться печати всех ребер так, чтобы они указывали на найденный цикл.

Я могу напечатать все ребра на графике, но не могу печатать только те ребра, которые создают цикл. Как мне заставить это работать?

Вот реализация графа:

Edge:

public class Edge {
    int source, dest;

    public Edge(int source, int dest) {
        this.source = source;
        this.dest = dest;
    }
}

График:

public class Graph {
    // A List of Lists to represent an adjacency list
    // Each insideList contains pointers to the next vertex
    // list with an index of 1 (vertex 1) contains elements 2 and 3 (where 2, 3 are vertices connected to 1) 
    List<List<Integer>> adjList = null;

    // Constructor
    public Graph(List<Edge> edges, int N) {
        adjList = new ArrayList<>(N);

        for (int i = 0; i < N; i++) {
            adjList.add(i, new ArrayList<>());
        }

        // add edges to the undirected graph
        for (Edge edge : edges) {
            int src = edge.source;
            int dest = edge.dest;

            adjList.get(src).add(dest);
            adjList.get(dest).add(src);
        }
    }
}

Узел:

public class Node {
    int v, parent;

    public Node(int v, int parent) {
        this.v = v;
        this.parent = parent;
    }
}

Алгоритм и тест:

public class GraphTest {
    // Perform BFS on graph starting from vertex src and
    // returns true if cycle is found in the graph

    // while traversing the graph, it should display the edges which create a cycle, but I am unable to do it (the result is wrong)
    public static boolean BFS(Graph graph, int src, int N) {
        // stores booleans if a vertex is discovered or not
        boolean[] discovered = new boolean[N];

        // mark source vertex as discovered
        discovered[src] = true;

        // create a queue used to do BFS and
        // push source vertex into the queue
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(src, -1));

        // run till queue is not empty
        while (!q.isEmpty()) {
            // pop front node from queue and print it
            Node node = q.poll();

            // do for every edge (v -> u)
            for (int u : graph.adjList.get(node.v)) {
                if (!discovered[u]) {
                    // mark it as discovered
                    discovered[u] = true;

                    // construct the queue node containing info
                    // about vertex and push it into the queue
                    System.out.println(node.v + " -- " + u);
                    q.add(new Node(u, node.v));
                }

                // u is discovered and u is not a parent
                else if (u != node.parent) {
                    // we found a cross-edge ie. cycle is found
                    return true;
                }
            }
        }

        // No cross-edges found in the graph
        return false;
    }
    // Check if an undirected graph contains cycle or not
    public static void main(String[] args) {
        // In my case I load an adjacency matrix from file and then perform an action to create Edges.
        // 0 1 1 0 
        // 1 0 1 0 
        // 1 1 0 1 
        // 0 0 1 0

        // Edge(1, 2), Edge(2, 3), Edge(3, 1), Edge(3, 4)
        // Edge(3, 1) introduces a cycle in the graph

        List<Edge> edges = new ArrayList<Edge>();
        ArrayList<ArrayList<Integer>> matrixList = loadFromFile(filePath);
        System.out.println("Graph: (Adjacency Matrix)");
        for (int i = 0; i < matrixList.size(); i++) {
            for (int j = 0; j < matrixList.size(); j++) {
                System.out.print(matrixList.get(i).get(j) + " ");
            }
            System.out.println();
        }
        System.out.println("All the edges: ");
        for (int i = 0; i < matrixList.size(); i++) {
            // ' + 1' is added so as to start vertices from 1 instead of 0
            int temp = i + 1;
            for (int j = 0; j < matrixList.size(); j++) {
                if (matrixList.get(i).get(j) == 1) {
                    System.out.println(temp + "--" + (j + 1) + " ");
                    // each edge is added one-way only since it is an undirected graph
                    // if Edge(1,3) is already present, Edge(3,1) is not added
                    boolean isFound = false;
                    for (Edge e : edges) {
                        if (e.dest == temp && e.source == (j + 1)) {
                            isFound = true;
                        }
                    }
                    if (!isFound)
                        edges.add(new Edge(temp, j + 1));
                }
            }
            System.out.println();
        }

        // sets number of vertices in the graph
        final int N = 5;

        // creates a graph from edges
        Graph graph = new Graph(edges, N);
        boolean[] discovered = new boolean[N];

        // do BFS traversal in connected components of graph
        System.out.println("Detect a cycle: ");
        if (BFS(graph, 1, N))
            System.out.println("Graph contains cycle");
        else
            System.out.println("Graph doesn't contain any cycle");
}

Вход: матрица смежности (или предварительно сформированный список ребер)

Текущий неверный вывод: отображает некоторые ребра, но не все ребра цикла

Ожидаемый вывод: для печати всех ребер, которые создают цикл, как показано в примере выше,

Я хотел бы отобразить: 1--2, 2--3, 3--1 Конечная вершина одного ребра является начальной вершиной другого ребра в цикле.

Answer 1

Я не утверждаю, что это лучший способ достижения результата, но это один из способов.

Прежде всего, я бы изменил определение вашего узла:

public class Node {
    int v;
    Node parent;

    public Node(int v, Node parent) {
        this.v = v;
        this.parent = parent;
    }
}

Тогда в вашем методе BFS я бы изменил обнаруженный логический массив на массив Node, чтобы вы знали, какой путь ведет к этому узлу.

// stores booleans if a vertex is discovered or not
Node[]  discovered = new Node[N];

Ваш метод BFS будет работать тогда следующим образом :

public static boolean BFS(Graph graph, int src, int N) {
        // stores booleans if a vertex is discovered or not
        Node[]  discovered = new Node[N];

        // mark source vertex as discovered
        Node start = new Node(src, null);
        discovered[src] = start;

        // create a queue used to do BFS and
        // push source vertex into the queue
        Queue<Node> q = new LinkedList<>();
        q.add(start);

        // run till queue is not empty
        while (!q.isEmpty()) {
            // pop front node from queue and print it
            Node node = q.poll();

            // do for every edge (v -> u)
            for (int u : graph.adjList.get(node.v)) {
                if (discovered[u] == null) {
                    // mark it as discovered
                    Node newNode = new Node(u, node);
                    discovered[u] = newNode;

                    // construct the queue node containing info
                    // about vertex and push it into the queue
                    q.add(newNode);
                }

                // u is discovered and u is not a parent
                else if (u != node.parent.v) {                      
                    Node newNode = new Node(u, node);
                    int commonParent = findCommonParent(discovered[u], newNode);

                    String result = "";

                    Node current;

                    current =  discovered[u];
                    while(current.v != commonParent) {
                        result = current.parent.v + "--" + current.v + ", " + result;
                        current = current.parent;
                    }

                    current = newNode;
                    while(current.v != commonParent) {
                        result = result + current.v + "--" + current.parent.v + ", ";
                        current = current.parent;
                    }
                    result = result.substring(0, result.length() - 2);

                    System.out.println(result);
                    // we found a cross-edge ie. cycle is found
                    return true;
                }
            }
        }

        // No cross-edges found in the graph
        return false;
    }

Метод findCommonParent может быть реализован, например, так:

private static int findCommonParent(Node n1, Node n2) {     
    Set<Integer> n1Parents = new HashSet<Integer>();
    Node temp = n1.parent;
    while(temp != null) {
        n1Parents.add(temp.v);
        temp = temp.parent;
    }       
    temp = n2.parent;
    while(temp != null) {
        if(n1Parents.contains(temp.v)) {
            break;
        }
        temp = temp.parent;
    }

    return temp.v;
}