Как найти вершины в цикле графа

Question

Например. для 1->2, 2->3, 3->4, 4->2, я хочу напечатать 2, 3, 4. Я попробовал DFS, и когда я нашел вершину, которую я посетил ранее, я иду к родителю, пока я не получить эту вершину, но она не работает хорошо. Иногда это входит в бесконечный цикл.

Запустите DFS:

int i;
for (i = 0; i < MAX_VER; i += 1)
    if (ver[i].v == 0 && ver[i].nb > 0)
        dfs(i);

ДФС:

ver[v].v = 1;

int i;
for (i = 0; i < ver[v].nb; i += 1) {
    ver[ver[v].to[i]].p = v;

    if (ver[ver[v].to[i]].v == 0)
        dfs(ver[v].to[i]);
    else
        // cycle found
        printCycle(ver[v].to[i]);
}

и цикл печати:

printf("\cycle: %d ", v);

int p = ver[v].p;

while (p != v) {
    printf("%d(%d) ", p, v);

    p = ver[p].p;
}

printf("\n");

Структура вершины:

int *to; // neighbor list

int nb; // how many neighbor
int p; // parent
short v; // was visited? 0 = false, 1 = true

Answer 1

Похоже, вы ищете "Сильно связанные компоненты" - так что вам повезло, есть хорошо известный алгоритм для поиска их в графике. Смотри Тарьян.

Алгоритм довольно хорошо описан в этой статье, но он немного сложен, поэтому я не буду его здесь вставлять. Кроме того, если вы не делаете это для изучения, вам, вероятно, будет лучше использовать существующую реализацию, это не так сложно реализовать, но это не так просто.

РЕДАКТИРОВАТЬ. Похоже, этот вопрос на самом деле дурак... мне больно говорить это, но его, вероятно, нужно закрыть, извините. См. Лучший алгоритм для обнаружения циклов в ориентированном графе

Answer 2

Вы должны использовать раскраску вершин, чтобы избежать бесконечного цикла в DFS. Сначала все вершины помечаются как БЕЛЫЕ. Когда вы впервые обнаруживаете вершину (она помечена как БЕЛАЯ), вы должны пометить ее как СЕРЫЙ. Если бы вы обнаружили СЕРУЮ вершину, вы бы нашли петлю.