Найдите цикл, содержащий более 3 вершин, используя DSF, если это возможно - PullRequest
Новая
       64

Найдите цикл, содержащий более 3 вершин, используя DSF, если это возможно

0 голосов
/ 17 апреля 2019

Я реализую алгоритм оптимального решения и мне нужно найти цикл, который содержит более 3 вершин, потому что диагональные соединения не разрешены (только вверх / вниз, влево / вправо).Я был бы очень признателен, если у кого-либо есть какие-либо предложения или он может указать мне направление на ресурсы.

Я уже реализовал метод связного списка с использованием матрицы смежности.Я основал его на this , но он останавливается только на первом цикле, который содержит только 3 вершины.

Мой текущий код использует коллекцию пользовательских объектов, поэтому он немного отличается от этого. 

// A Java Program to detect cycle in a graph 
class Graph { 
    private final int V; 
    private final List<List<Integer>> adj; 

    public Graph(int V)  
    { 
        this.V = V; 
        adj = new ArrayList<>(V); 

        for (int i = 0; i < V; i++) 
            adj.add(new LinkedList<>()); 

    }     

    // This function is a variation of DFSUytil() in  

    // https://www.geeksforgeeks.org/archives/18212 

    private boolean isCyclicUtil(int i, boolean[] visited, 

                                      boolean[] recStack)  

    { 

        // Mark the current node as visited and 
        // part of recursion stack 
        if (recStack[i]) 

            return true; 

        if (visited[i]) 

            return false; 

        visited[i] = true;   

        recStack[i] = true; 

        List<Integer> children = adj.get(i);          

        for (Integer c: children) 
            if (isCyclicUtil(c, visited, recStack)) 
                return true;                

        recStack[i] = false; 

        return false; 

    } 

    private void addEdge(int source, int dest) { 

        adj.get(source).add(dest); 
    } 

    // Returns true if the graph contains a  
    // cycle, else false. 
    // This function is a variation of DFS() in  
    // https://www.geeksforgeeks.org/archives/18212 
    private boolean isCyclic()  
    { 
        // Mark all the vertices as not visited and 
        // not part of recursion stack 

        boolean[] visited = new boolean[V]; 

        boolean[] recStack = new boolean[V]; 

        // Call the recursive helper function to 

        // detect cycle in different DFS trees 

        for (int i = 0; i < V; i++) 

            if (isCyclicUtil(i, visited, recStack)) 

                return true; 
        return false; 

    } 
    public static void main(String[] args) 

    { 
        Graph graph = new Graph(5); 
        graph.addEdge(0, 1); 
        graph.addEdge(0, 2); 
        graph.addEdge(1, 2); 
        graph.addEdge(2, 0); 
        graph.addEdge(2, 3); 
        graph.addEdge(3, 3); 

        graph.isCyclic();

    } 
}

Я не могу опубликовать свой точный код, так как я могу быть помечен на плагиат 

An example of a cycle I would like to find is:
00000
01010
01010
Where the 4 edged cycle is represent by 1s
At the moment I get a result where a cycle
00000
00000
01110
and this is not what I need.
...