KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
Is it true that the implementation of BFS, DFS and Dijkstra are almost the same, except that BFS uses queue, DFS uses stack, while Dijkstra uses min priority queue? More precisely. Can we use the following code for all of BFS, DFS, and Dijkstra, with Q being a queue for BFS, and a stack for DFS, and a min priority queue for Dijkstra? Thanks! Init d[]=Inf; // distance from the node s Init c[]='w'; // color of nodes: 'w':undiscovered, 'g':discovered, 'b':fully explored Init p[]=null; // previous node in the path c[s]='g'; d[s]=0; Q.push(s); while(!Q.empty()) { u = Q.front(); Q.pop(); for v in adj[u] { if(c(v)=='w') { c[v]='g'; if(d[u]+w(u,v)<d[v]) { d[v]=d[u]+w(u,v); p[v]=u; } Q.push(v); } } c[u]='b'; }
Tags (comma-separated)
Save Edits
Cancel