Я использую алгоритм DFS и хочу отмечать каждое ребро, как было посещено. Подходом было бы искать узел и заменять его некоторым дозорным, но это было бы дорого, если бы я сделал список смежности сохраните значение, соответствующее посещаемому узлу, что увеличит время поиска, матрица будет потреблять много места. для чего это лучший алгоритм?Посещение ребер на графике
Вам просто нужно поддерживать набор пар вершин. Например, в Java HashMap<Pair<Vertex, Vertex>>. В Python, Set двухэлементных кортежей.
Посещение края происходит, когда вы перечисляете потомков только что найденной вершины и добавляете их в стек DFS. Если вы используете рекурсивную DFS, то это так же, как вы делаете рекурсивный вызов для каждого потомка. Вот версия стека:
dfs(graph)
visitedVertices = \emptyset
visitedEdges = \emptyset
// Try all vertices as search roots
for each vertex r in graph
push r onto empty stack
while notEmpty(stack)
u = pop stack
if u not in visitedVertices
add u to visitedVertices
foreach v such that u->v is in graph
add (u,v) to visitedEdges // Visit the edge
push v on stack
Сказав это, я не уверен, почему вы хотите это сделать. Правильно реализованная DFS естественным образом пересекает каждый край ровно один раз. Вы можете доказать это сами, посмотрев на алгоритм выше. Посещение (u,v) возможно только в том случае, если раньше u не был посещен.
Возможно, у вас есть еще одна тема, которая следит за ходом поиска или фактически добавляет другую информацию к краям при посещении?
Я хочу создать схему эйлера графа, перенаправляя ребра, и алгоритм Флери слишком сложный (отнимающий много времени) для моего ограничения, я не могу позволить себе удалить ребро и снова применить dfs, чтобы проверить, был ли он мостом или нет. Не думаете ли вы, что выше алгоритм не удается в случае, когда я пытаюсь посетить узел более одного раза? и если отмечено 1-> 2, ребро 2-> 1 все еще возможно, потому что оно не было в отмеченных краях, но это создавало бы и неориентированный край? – idk
@idk Извините, я не понимаю, о чем вы спрашиваете. – Gene
Учитывая, что искаженная схема эйлера означает, что ребра были перегруппированы, я хочу снова создать схему эйлеров, перенаправляя края, которые были помещены в неправильном порядке, чтобы создать схему эйлеров графа. – idk
Нужно ли записывать края во время посещения? Для того, чтобы вы дважды повторяли ребро, вам нужно было пройти один и тот же узел дважды. Слежение за посещаемыми узлами должно быть проще. Что именно ты пытаешься сделать? –
@ A.Sokol Я посещаю край, и мне нужно записать его, поэтому я бы не стал снова посещать его, хотя я бы это сделал, если бы такой случай существовал. 1-> 2 && 2-> 1. Мне нужно напечатать порядок, в котором Я посещаю край, поэтому мне нужно их хранить. – idk
так почему бы вам не напечатать его, когда идете? – CodingYoshi