Поиск всех контуров (циклов в орграфе)

261
03 мая 2018, 09:57

Необходимо найти все контуры графа. Примерно понимаю, что это делается через поиск в глубину, но вот как ни старайся, не выходит найти их полностью и без повторений. Вот то, что у меня пока есть:

private class Graph {
    private int V; 
    private ArrayList<Integer> 
    Graph(int v) {
        V = v;
        adj = new ArrayList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new ArrayList<>();
    }
    void addEdge(int v, int w) {
        adj[v].add(w);  // Add w to v's list.
    }
    void DFSUtil(int v, boolean visited[], LinkedList<Integer> tempList, ArrayList<String> globalPathList) {
        TextView out = findViewById(R.id.textView2);
        visited[v] = true;
        tempList.addLast(v);
        if (v == globalVer) {
            globalPathList.add(tempList.toString());
            Log.w("CHECK", tempList.toString());
            if (tempList.size() > 1)
                tempList.removeLast();
        }
        for (Integer i : adj[v]) {
            if (!visited[i] | i == globalVer) {
                DFSUtil(i, visited, tempList, globalPathList);
                if (tempList.size() > 1)
                    tempList.removeLast();
            }
        }
        visited[v] = false;
    }
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++){
            visited[i] = false;
        }
    }
}
public void findPath(View view) {
    LinkedList<Integer> tempList = new LinkedList<>();
    ArrayList<String > globalPathList = new ArrayList<>();
    Graph g = new Graph(6);
    g.addEdge(0, 1);
    g.addEdge(0, 3);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 4);
    g.addEdge(1, 5);
    g.addEdge(2, 3);
    g.addEdge(2, 4);
    g.addEdge(2, 5);
    g.addEdge(3, 1);
    g.addEdge(3, 4);
    g.addEdge(4, 5);
    g.addEdge(5, 0);
    globalVer = 1;
    g.DFS(globalVer, tempList, globalPathList);
        Log.w("FINAL_CHECK", globalPathList.toString());
}
READ ALSO
Остаток от деления бинарных чисел java

Остаток от деления бинарных чисел java

Какой есть алгоритм нахождения остатка от деления двоичных чисел?нужно реализовать деление полиномов,представил их в виде 110010 mod 1010 а дальше...

223
Как переходить между JFrame окнами?

Как переходить между JFrame окнами?

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

253
Сложение значений datetime

Сложение значений datetime

Нужно вывести список сотрудников, которые отработали суммарно менее 8 часов в офисе от первого входа до последнего выходаЯ правильно понимаю...

259
SQL - дубликаты записи

SQL - дубликаты записи

при парсинге магазинов у товаров возникает одна проблема:

263