Можно ли решить алгоритм поиска объединения, используя представление списка смежности для неориентированного графа вместо представления ребер для графа? - PullRequest
Новая
       36

Можно ли решить алгоритм поиска объединения, используя представление списка смежности для неориентированного графа вместо представления ребер для графа?

0 голосов
/ 28 сентября 2018

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

package com.java.algorithm.graph;

import java.util.Arrays;import java.util.Iterator; 

public class DisjointSet {
public static void main(String[] args) {
    UndirectedGraph graph = new UndirectedGraph(4);
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);

// graph.addEdge (3, 0); 

    if (isCycle(graph)) {
        System.out.println("Yes the given undirected graph contains cycle");
    } else {
        System.out.println("The given undirected graph Doesnt contain a cycle");
    }

}

private static boolean isCycle(UndirectedGraph graph) {
    int v = graph.V;

    int[] parent = new int[v];

    Arrays.fill(parent, -1);

    boolean[] visited = new boolean[v];

    for (int i = 0; i < v; i++) {

        if (visited[i] == false) {
            if (isCycleUtil(graph, parent, visited, i))
                return true;

        }

    }

    // for()

    return false;
}

private static boolean isCycleUtil(UndirectedGraph graph, int[] parent, boolean[] visited, int u) {
    visited[u] = true;
    Iterator<Integer> itr = graph.adjList[u].iterator();

    while (itr.hasNext()) {
        int v = itr.next();

        // if(visited[v]==true)
        // continue;

        if (visited[v] == false) {
            if (isCycleUtil(graph, parent, visited, v))
                return true;
        }

        int y = find(parent, v);

        int x = find(parent, u);
        System.out.println("u= " + u + " v= " + v);

        System.out.println("x= " + x + " y= " + y);

        for (int i = 0; i < graph.V; i++) {
            System.out.print(parent[i] + " ");
        }
        System.out.println();

        if (x == y)
            return true;

        union(parent, u, v);



    }

    return false;
}

private static void union(int[] parent, int u, int v) {
    parent[u] = v;

}

private static int find(int[] parent, int v) {
    while (parent[v] != -1) {
        v = parent[v];
    }

    return v;
}

} 

import java.util.LinkedList;

public class UndirectedGraph {
    int V;
    LinkedList[] adjList = null;
    int[][] weight = null;

    public UndirectedGraph(int v) {
        this.V = v;
        adjList = new LinkedList[v];
        weight = new int[v][v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<Integer>();
        }

    }

    public void addEdge(int u, int v)
    {
        adjList[u].add(v);
        adjList[v].add(u);

    }

}
...