-1
$\begingroup$

I have the following weighted graph with connected nodes. I've made some connections red just to be easier on the eye. enter image description here

I am applying DFS on this graph and I am not sure if this is correct because on theory DFS takes the first node and that implementation is easy when the graph isn't weighted so we apply alphabetically order. But on weighted graph it's more complicated.

My output solution : 1-3-6-2-5-8-9

Graph front (step by step):

(1)
(3 2)
(6 5 2)
(2 7 5 2)
(5 4 7 5 2)
(8 7 4 7 5 2)
(9 4 7 4 7 5 2)
(4 7 4 7 5 2)

My solution is based on the weights, the nodes are coming to the front on ascending order. They key moment on my solution was when it was on node 6 and moved to 2 because 2 wasn't visited. I need some guidance when it comes to weighted graphs and DFS.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ It is unclear what you want to achieve. DFS or BFS on weighted graphs is exactly the same as on unweighted graphs, since both algorithms don't use any edge weights. Can you tell us why you want to run these algorithms? $\endgroup$
    – adrianN
    Commented Sep 4, 2017 at 13:55
  • $\begingroup$ But what's your question? You've run DFS on your graph, but you don't say what you were trying to achieve by doing that. Nor do you say what was wrong with the result you got. $\endgroup$
    – David Richerby
    Commented Nov 3, 2017 at 10:37

2 Answers 2

Reset to default
4
$\begingroup$

To be short, performing a DFS or BFS on the graph will produce a spanning tree, but neither of those algorithms takes edge weights into account. (Source).

So if you apply the DFS algorithm to a weighted graph it would be simply not consider the weight and print the output. If you want to identify the shortest path, you would use Dijkstra Algorithm

I suggest you to read these slides from a Data Structures & Algorithm Coruse

Improve this answer
$\endgroup$
3
  • $\begingroup$ So , I can say I am using alphabetically order but it doesn't really matter on DFS and BFS? $\endgroup$
    – Manuel Pap
    Commented Sep 3, 2017 at 10:52
  • $\begingroup$ DFS and BFS won't even produce a minimum spanning tree on a weighted graph. $\endgroup$
    – Zephyr
    Commented Sep 3, 2017 at 12:01
  • $\begingroup$ @valkon, what is your real aim to perform DFS in this manner ? If it's to find the shortest path then it's not possible to do it in this way. You have to use Dijkstra's algorithm. $\endgroup$
    – Zephyr
    Commented Sep 3, 2017 at 12:02
1
$\begingroup$

DFS do not use weights in any case. In your solution, you are taking the least weight path for DFS. Your solution is okay, I guess. Just add one more clause in your algorithm. That if the least weight path leads to a node that is already visited, then visit the path with the second-lowest weight and so on for each node pushed in the stack. For each connected component, you will get a tree.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.