I want to find shortest path from node to some other node in Strongly Connected Component, the nodes could by chosen arbitrarily. Two searching methods come to mind Depth First Search or Breadth First Search.
Can be proven that for some situation is one preferable over the other?
One situation could be sparse graph vs. dense graph SCC.
Is DFS faster than BFS when searching a specific node in SSC?
962 views Asked by world-r-u-ok At
2
There are 2 answers
Related Questions in GRAPH-THEORY
- Algorithm for total flow through weighted directed acyclic graph
- Finding path with smallest GCD of nodes's weights in directed graph
- The plot function in the 'gRc' library gives an error (also in the demo)
- Color edges distinctly in network based on attribute value
- Make a stack of adjacency matrices from a dataframe in R
- What is an efficient algorithm to identify multi-degree email chains in a mock company network?
- Approximation Algorithms for the Longest Simple Path in a Directed Graph
- Eliminate edges in a routing graph which aren't used in the shortest path between a subset of nodes
- PageRank Algorithm on a Graph with a Sink Node
- Algorithm to cover time periods
- Prims minimum spanning
- DFS Maze generation
- Find the node with the minimum maximum distance in a graph
- Undirected connected graph - Finding edges with specific weight that belong to MST
- Why is my graph coloring code not coloring the graph correctly?
Related Questions in DEPTH-FIRST-SEARCH
- Finding the Longest Consecutive Path in a Matrix
- Why DFS and not BFS for finding cycle in graph
- Approach for solving a Breadth first search(BFS) components problem
- How can I improve the iterative approach to be faster than recursive implementation, as usual?
- Issue solving DFS Flood Fill problem while iterating through branching options
- Debugging Boggle Solver Implemented in Elixir with Trie Structure
- How to solve boat movements using Graph algorithm?
- TIDEMAN CS50-how can i check if the pair.winner is a winner elsewhere, i.e we have more than 1 edge going from some candidate
- Count Unguarded Cells in the Grid (recursion)
- Finding goal through BFS and DFS
- Number of islands problem Leetcode recursive DFS and non recursive BFS
- DOM diff algorithm with HTML streaming?
- Recursive Search on 2D grid
- Permutation brute force vs Selection brute force algorithm. When to use what?
- how to fix this problem with start-dfs.sh command
Related Questions in BREADTH-FIRST-SEARCH
- Leetcode BFS Set insertion giving TLE (200. Number of Islands)
- Why DFS and not BFS for finding cycle in graph
- Approach for solving a Breadth first search(BFS) components problem
- Breadth First Search Causing Heap Memory Error With exponentially growing graph
- Undirected Graph, get list of all nodes that can be visited
- Struggling to separate breadth first search section of my main loop into its own function
- Algorithm to connect every node between each level of a graph / tree
- Generate tuples of non-negative integers closed under promotion?
- Finding goal through BFS and DFS
- Number of islands problem Leetcode recursive DFS and non recursive BFS
- Print path to node in a 2D dictionary-structured graph
- BFS Maximize Minimum Distance from a Monster along a path
- Find the path with the minimum number of transfers between stations?
- BFS ever failing for a unweighted and undirected graph?
- How would I show the parenthesis theorem doesn't work for Breadth First Search?
Related Questions in STRONGLY-CONNECTED-GRAPH
- Relationship Between Intermediate Vertices and Strongly Connected Components (SCCs) in Graphs
- How to get a list of edges in python corresponding to a set?
- Strongly connected component for the graph is giving different result for Kosaraju's Algorithm and Tarjan's Algorithm
- A graph with maximum number of strongly connected components
- How to break down Strongly Connected Components (SCC) in a graph to obtain smaller and smaller nested cycles in JavaScript?
- Difference between a directed cycle and a strongly connected component
- Let G=(V, E) directed graph. Let v be a vertex in G, find the number of vertices that take part in non-simple directed paths to v
- Generate random directed connected graph using networkx?
- Given a list of words, determine whether the words can be chained to form a circle
- Finding no. of strongly connected components - wrong answer by my code
- Neo4j find n largest connected graphs with specific node types
- Returning connected parts of a graph (dfs & graphs)
- "A connected graph is connected if and only if a depth first search starting from any node visits every other node"
- Find Strongly Connected Graph such that the difference between the maximum and minimum edges is minimum
- Strongly Connected Components
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
DFS does not guarantee that if node 1 is visited before another node 2 starting from a source vertex, then node 1 is closer to the source than node 2.
This can be easily seen from recursive nature of DFS. It visits the 'deeper' nodes or you can say farther from source nodes first. It goes as far as it can from the source vertex and then returns back to unvisited adjacent nodes of visited vertices.
On the other hand BFS always visits nodes in increasing order of their distance from the source. It first visits all nodes at same 'level' of the graph and then goes on to the next level.
Besides, the use of a non-recursive algorithm (BFS) is more productive purely in practical terms.