Представление графика в C++

Question

Я просматриваю книгу The Design and Analysis of Computer Algorithms Чтение через главу графа, я пытаюсь реализовать DFS. Читая определение этого алгоритма, он говорит, что график G=(V,E) разделяет края в E на два набора T и B. Край (v,w) это место в наборе T если Вертеш w не ранее посещенных, когда мы находимся на вершине v учитывая обрезной (v,w), в противном случае ребра `(v, w) является место в множестве B.

В основном его алгоритм DFS будет дайте мне новый график, который будет G=(V,T). Я хочу знать, как реализовать это на C++.

Я попытался с помощью adjacency list, но я путаю есть необходимость хранения edges от всего map из list должно быть хорошо.

Answer 1

В VTK края хранятся в vector и всегда сохраняют пару (v, w). Рядом с этим вектором есть два других вектора векторов для хранения в и из ребер узлов графа. Когда добавляется новый край, он добавляется к реберному вектору, его узлы (v, w) добавляются к вектору векторов векторов векторов и из них.

Answer 2

Я не совсем понимаю, что такое ваш точный вопрос. Я предполагаю, что вы спрашиваете о том, как поддерживать два набора T и B, чтобы различать ребра, которые были посещены с ребрами, которые не были во время DFS. Я думаю, что самый простой способ сделать это - добавить в таблицу смежности добавленное поле bool для посещения структуры узла. Начальное значение этого поля для всех узлов «false». Предположим, что в приведенном выше случае, когда DFS приходит в v, а край (v, w) не посещается, то узел в списке v, который соответствует w, будет иметь значение «false» для «посещенных» в это время , В противном случае оно будет иметь значение «true».

Я думаю, что автор просто попытается дать вам представление о том, что ребра будут разделены на два вида: посещенные и не посещенные в конце DFS. Но я не думаю, что нужно поддерживать два явных набора, поддерживающих эти два типа ребер. Вы всегда можете распечатать посещенные ребра после DFS в соответствии с их обновленным «посещенным» значением.