# Recent questions tagged graph-algorithms

1
Consider vertices V1 and V2 that are simultaneously on function call stack at some point during DFS from vertex s. Which of the following are always true for this digraph ? 1. There exists a directed path from s to V1 and s to V2 . 2.There exists a directed path from ... V1 . I think only statement 3 is correct......How can we say that statement 1 is also correct please someone explain the reason
2
Q1. Consider the following DFS algorithm for cycle detection in a graph. DFS(G) for each vertex u Belongs G.V u.color = WHITE U.pi = NIL time = 0 for each vertex u Belongs G.V if u.color == WHITE DFS-VISIT(G , u) DFS-VISIT(G, u) time = time + 1 u. ... after getting DFS tree if we draw an edge from one leaf node to another leaf node then that edge is called cross edge. Is this statement is true ??
3
Which of the following are true:- 1. DFS continues to visited first unvisited successor of each node as long as possible. 2. Certain nodes are pushed into the stack. 3. DFS first visits all the immediate successors of a node before moving to their successors 4. Certain nodes are ... iterative all nodes are pushed into the stack. 3. False -- this happens in BFS not in DFS. 4. True -- Iterative DFS.
1 vote
4
I have seen these following question:- Number of Vertices pushed more than once. https://gateoverflow.in/5296/number-of-vs-that-are-pushed-more-than-once-in-a-dfs https://gateoverflow.in/98484/dfs-using-stack Vertices not pushed onto the stack:- https:// ... is showing that each and every vertex pushed exactly once into the stack http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/.
5
How to solve this question ? Plz describe the detailed solution .
6
I have few doubts related to Longest distance problem. From Wikipedia --> The NP-hardness of the unweighted longest path problem can be shown using a reduction from the Hamiltonian path problem: a graph G has a Hamiltonian path if and only if ... negative then use normal algorithm as asked in (https://stackoverflow.com/questions/42500120/floyd-warshall-for-longest-distance-for-undirected-graph)
7
8
suppose there are N number of nodes. How many ways we can write DFS and BFS sequence for it. how many are the valid sequence??? how many are invalid?? can we generalized the formula for it??
9
If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge. True or false ?
1 vote
10
Here the graph that I was trying to find MST using algo in cormen.(If you need algo to ask, I supposed you have it) Algorithms uses min queue in process, my dobut is when it came to choice b/w vertex 'c' and 'd' as at that time both will have 8 has key ... we get wrong answer, so prism deal with this case? If you need algo I will given you, or just please refer chapter 23 cormen prim's algorithm.
11
The problem of finding the set of vertices reachable from a given vertex in a graph can be solved in time A. O(|V|^2) B. O(|V| + |E|) C. O(|V||E|) D. none of these
1 vote
12
For a given undirected weighted graph G with V number of vertices, if you want to find all pair shortest paths then which one of the following is true ? a) run dijkstra's shortest path algorithm only once. b) run dijkstra's shortest path algorithm V times. What if the given graph is directed ?
13
Which of the following data structure is useful in traversing a given graph by breadth first search? Stack Queue List None of the above
14
Which of the following algorithms solves the all pair shortest path problem? Prim's algorithm Dijkstra's algorithm Bellman ford algorithm Floyd warshalls algorithm
1 vote
15
can someone pls explain how is the internal path length of complete binary tree is O(n logn)? (if it is correct)
16
how many of the above statements are true?
17
Let $G=\left ( V,E \right )$ be $any$ connected, undirected, edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements: Minimum Spanning Tree of $G$ is always unique. Shortest path between any two vertices of $G$ is always unique. Which of the above statements is/are necessarily true? I only II only both I and II neither I nor II
18
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below? $\text{MNOPQR}$ $\text{NQMPOR}$ $\text{QMNROP}$ $\text{POQNMR}$
19
No of Simple Undirected Graph with unablled vertices - 2nC2 No of Simple Undirected Graph with labelled vertices - ? No of Simple Undirected Connected Graph with unablled vertices - ? No of Simple Undirected Connected Graph with labelled vertices - ?
20
Will dijiktras's algoritm fail for the graph given in the question (or the question has been framed wrongly)?
21
Show the different minimum spanning Trees Possible in each of the following Algorithms Prims Algorithm Kruskal
1 vote
22