Подсчитайте количество циклов в ориентированном графе, используя DFS

Я хочу подсчитать общее количество ориентированных циклов, доступных в ориентированном графе (требуется только подсчет).

Вы можете предположить, что граф задан как матрица смежности.

Я знаю DFS, но не смог составить работающий алгоритм для этой задачи.

Пожалуйста, предоставьте какой-нибудь псевдокод, используя DFS.


graph algorithm cycle directed-graph depth-first-search
person Sushil Verma    schedule 27.10.2015    source источник
comment
Разве DFS не работает только для ациклических графов...? В противном случае вы просто будете продолжать нырять и нырять вечно.   -  person Kevin    schedule 27.10.2015

Ответы (2)


arrow_upward
0
arrow_downward

Предположим, что мы раскрашиваем узлы тремя типами цветов. Если узел еще не обнаружен, его цвет — белый. Если узел обнаружен, но какие-либо из его потомков еще не обнаружены, то его цвет будет серым. В противном случае его цвет черный. Теперь, выполняя DFS, если мы сталкиваемся с ситуацией, когда между двумя серыми узлами есть ребро, то граф имеет цикл. Общее количество циклов будет общим количеством раз, когда мы сталкиваемся с ситуацией, упомянутой выше, то есть мы находим ребро между двумя серыми узлами.

person Honour    schedule 27.10.2015
comment
При поиске в глубину каждое направленное ребро рассматривается только один раз, поэтому этот алгоритм дает количество циклов меньше, чем количество ребер. К сожалению, циклов может быть намного больше, чем ребер. Рассмотрим полный граф на n вершинах. Каждое подмножество из двух или более вершин описывает по крайней мере один цикл [(n-1)! из них на самом деле], но имеет только n * (n-1) ребер, поэтому количество циклов растет быстрее, чем 2 ^ n, а количество ребер нет. Таким образом, приведенный выше алгоритм может не работать. - person deinst; 29.10.2015

arrow_upward
0
arrow_downward

Этот алгоритм, основанный на DFS, кажется, работает, но у меня нет доказательств.

Этот алгоритм изменен из dfs для топологической сортировки (https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search).

class Solution {
  vector<Edge> edges;
  // graph[vertex_id] -> vector of index of outgoing edges from @vertex_id.
  vector<vector<int>> graph;
  vector<bool> mark;
  vector<bool> pmark;
  int cycles;

  void dfs(int node) {
    if (pmark[node]) {
      return;
    }
    if (mark[node]) {
      cycles++;
      return;
    }
    mark[node] = true;

    // Try all outgoing edges.
    for (int edge_index : graph[node]) {
      dfs(edges[edge_index].to);
    }

    pmark[node] = true;
    mark[node] = false;
  }

  int CountCycles() {
    // Build graph.
    // ...

    cycles = 0;
    mark = vector<bool>(graph.size(), false);
    pmark = vector<bool>(graph.size(), false);
    for (int i = 0; i < (int) graph.size(); i++) {
      dfs(i);
    }

    return cycles;
  }
};
person romanzhg    schedule 03.01.2020