#java #algorithm #graph #depth-first-search #graph-traversal
#java #алгоритм #График #поиск в глубину #обход графика
Вопрос:
Я хочу реализовать dfs для узлов, которые имеют тип long в Java.
Мой алгоритм правильно вычисляет количество узлов и количество
ребер, но не последовательности узлов. Не могли бы вы мне помочь
измените мой алгоритм, чтобы я вычислял порядок, в котором расположены узлы
посещено, правильно?
Это мой код:
private int getNumberOfNodes(long firstNode) {
List<Long> marked = new ArrayList<>(); //------------------------------------------->
Stack<Long> stack = new Stack<Long>(); //step 1 Create/declare stack
stack.push(firstNode); //Step 2 Put/push inside the first node
while (!stack.isEmpty()) { //Repeat till stack is empty:
Long node = stack.pop(); //Step 3 Extract the top node in the stack
marked.add(node); //------------------------------------------->
long[] neighbors = xgraph.getNeighborsOf(node); //Get neighbors
if (neighbors.length % 2 == 0) {
} else {
numOfNodesWithOddDegree ;
}
int mnt = 0;
for (long currentNode : neighbors) {
if (!marked.contains(currentNode) amp;amp; !stack.contains(currentNode) ) { //amp;amp; !stack.contains(currentNode)
stack.push(currentNode);
} else {
}
if (!marked.contains(currentNode)) {
numOfEdges ;
}
}
}
return marked.size(); //(int) Arrays.stream(neighbors).count();
}
Комментарии:
1. Вы помещаете всех соседей узла в стек, а затем исследуете их. Это BFS, а не DFS
2. Как я должен вместо этого подталкивать их? Не могли бы вы, пожалуйста, опубликовать пример кода?
3. Можете ли вы пояснить с помощью небольшого примера графика, где этот алгоритм выдает неправильную последовательность? Что это дает в виде последовательности и чего ожидалось? Ваша функция возвращает число, поэтому мне непонятно, где вы проверяете последовательность узлов.
4. @c95 geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph
5. @AbhinavMathur ошибочен, поскольку OP использует стек, это DFS, поскольку стек — это FILO. отмеченный список будет содержать последовательность посещенных узлов.
Ответ №1:
Я предполагаю, что вы проверяете marked список на предмет последовательности действий.
Поскольку ваш график неориентирован, последовательность обходов может варьироваться в зависимости от того, какого соседа вы вставили в стек первым. что означает логику вашей функции:
xgraph.getNeighborsOf(node)
может повлиять на вашу последовательность. смотрите порядок вершин из этой вики https://en.wikipedia.org/wiki/Depth-first_search
итак, мой вывод таков: у вас может быть другая последовательность обхода, это не означает, что ваш DFS неверен, пока это глубокий первый поиск, можно немного отличаться от заданного ответа.