Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

67 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
1k views

Shortest Path using DFS on weighted graphs

I read that shortest path using DFS is not possible on a weighted graph. I pretty much understood the reason of why we can't apply on DFS for shortest path using this example:- Here if we follow ...
0
votes
0answers
144 views

Distance of a Graph node to a group of nodes?

Consider a graph where edges represent the similarity of two nodes. In general, the graph is sparse with edges existing between only similar nodes (I can achieve this by deleting edges with similarity ...
0
votes
0answers
183 views

Efficient algorithm to find an vertex that is not an articulation vertex

This is a question from the book The Algorithm Design Manual by Steven Skiena, Page no- 201. Articulation vertex : An articulation vertex of a graph (undirected) G is a vertex whose deletion ...
0
votes
0answers
40 views

Finding continuous line consisted of points surrounding points of different color

I have a problem with creating an algorithm that would find continuous line consised of points of one color (say blue) that surrounds points of different color (say red). This problem occurs in "Dots"...
0
votes
0answers
318 views

What is the time and space complexity of unidirectional bfs and bidirectional bfs?

How do time and space complexity compare for unidirectional bfs and bi-directional bfs in worst and practical case such as a social network?
0
votes
0answers
470 views

Finding a path visiting most nodes in complete digraph with cost limit and positive or negative edge weights

I'm leaving out some specifics because this is a challenge problem and I don't want to be spoon-fed the answer, but I need a nudge in the right direction. I am given a complete digraph with the ...
0
votes
0answers
278 views

Making DFS more efficient

I was looking for non-recursive implementation of DFS algorithm. I found the following pseudocode on this page. ...
0
votes
0answers
35 views

How to choose the maximum vertices you can delete from set while atleast 1 of its neighbors is in set?

We have a graph with connections to vertices given to us. For example, consider that following pairs of vertices are connected: ...
0
votes
0answers
168 views

What is the algorithmic complexity of DFS under the cache oblivious model?

Consider the basic non-recursive DFS algorithm on a graph G=(V,E) (python-like pseudocode below) that uses array-based adjacency lists, a couple of arrays of size V, and a dynamic array stack of size &...
0
votes
0answers
596 views

Traveling Salesman problem solution for small graph?

So let's say i have a graph like this and salesman starts his journey at "A" How do i solve the TSP problem for this graph with pen and paper on exam?
0
votes
0answers
470 views

Fastest Algorithm to find shortest path between two edges in a graph

If I just want to find shortest between a single source and destination, can I do better Dijkstra (which finds from one source to all destinations)? I am trying to answer a question in the EPI book. ...
0
votes
0answers
47 views

optimal path for traversing nodes

So here is the problem: There are n objects in a super market that you need to retrieve, then you need to go to the cashier register in the end. How do you find the best path of traversing the least ...
0
votes
0answers
581 views

Failing to understand the pseudo code of the inorder traversal

Edit: Solved, see comments I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is: ...
0
votes
0answers
159 views

Generalized steps to find tree traversal for any m-ary tree

So far I've read traversal techniques $(Pre-Order, In-Order, Post-Order)$ on binary trees. But In exam I've thrown up with a question, which requires me to find in-order traversal of a ternary tree. I ...
0
votes
0answers
498 views

Hopcroft–Karp algorithm time complexity

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph: https://dl.dropboxusercontent.com/u/64823035/04569670.pdf The ...
0
votes
1answer
393 views

Strict-Binary Tree - Same Post-order & Pre-order sequences?

I'm going through some past exam papers for my course and I'm having trouble completing this one question. It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order ...
-1
votes
1answer
3k views

Minimum spanning tree using DFS and BFS

Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs? I have gone through many answers but each answer says something different and I am not convinced....