Матрица смежности - ›Направленный граф -› DFS

Это код, который мы с друзьями придумали после того, как возились. То, что мы пытаемся сделать, это прочитать матрицу смежности (input.txt), а затем создать из нее ориентированный граф, чтобы мы могли выполнять поиск с помощью поиска в глубину. Мы хотим, чтобы в выводе нашей программы был указан порядок посещаемых узлов.

Код Java: http://pastebin.com/bAzBadxi

Файл input.txt: http://pastebin.com/r72J34uA

Мой вопрос в том, чем мы инициализируем "n"? (строка 32 в java-коде)

Любая помощь будет оценена по достоинству.


java adjacency-matrix directed-graph depth-first-search
person kangtong    schedule 02.04.2013    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Перед использованием создайте объект вершины.

Vertex n;    // before g.addVertex(n);

Я не проверяю ваш алгоритм, просто удаляю ошибку компилятора, если ваш алгоритм верен, он должен работать нормально

person AurA    schedule 02.04.2013
comment
Спасибо, скомпилировал, но алгоритма точно не хватает. - person kangtong; 02.04.2013

arrow_upward
0
arrow_downward

Вы пытаетесь решить проблему топологической сортировки.

Топологическая сортировка

В этом случае не имеет значения, каким n вы инициализируете, вы можете просто использовать первую вершину в матрице смежности в качестве начала.

А матрица смежности (которая должна быть квадратной матрицей) является правильным представлением ориентированного графа, вы можете использовать матрицу для прямого поиска в графе.

person user2172816    schedule 02.04.2013
comment
Спасибо. Теперь он компилируется, но ничего не отображается, хотя я изменил матрицу на квадратную (спасибо за подсказку). Есть подсказки, как это исправить? Есть ли способ установить n в первую вершину в матрице смежности? - person kangtong; 02.04.2013