search
Log In

Recent questions tagged graph-algorithms

3 votes
2 answers
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
asked Nov 1, 2017 in Algorithms Shivi rao 304 views
0 votes
1 answer
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 ??
asked Oct 28, 2017 in Algorithms Shubhanshu 179 views
2 votes
0 answers
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.
asked Oct 20, 2017 in Algorithms Shubhanshu 339 views
1 vote
0 answers
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/.
asked Oct 19, 2017 in Programming Shubhanshu 1.3k views
0 votes
1 answer
5
How to solve this question ? Plz describe the detailed solution .
asked Sep 30, 2017 in Algorithms dragonball 141 views
0 votes
0 answers
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)
asked Sep 8, 2017 in Algorithms Chhotu 901 views
3 votes
2 answers
7
asked Aug 30, 2017 in DS Gate Ranker18 194 views
0 votes
1 answer
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??
asked Aug 22, 2017 in DS Hira Thakur 293 views
0 votes
1 answer
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 ?
asked Aug 20, 2017 in Programming Xylene 1.2k views
1 vote
0 answers
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.
asked Aug 5, 2017 in Algorithms bhuv 471 views
2 votes
1 answer
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
asked Jul 15, 2017 in Algorithms Abhisek Saha 168 views
1 vote
3 answers
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 ?
asked Jun 26, 2017 in Algorithms Abhisek Saha 397 views
9 votes
8 answers
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
asked May 10, 2017 in Algorithms Arjun 8k views
5 votes
5 answers
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
asked May 7, 2017 in Algorithms sh!va 2.9k views
1 vote
0 answers
15
can someone pls explain how is the internal path length of complete binary tree is O(n logn)? (if it is correct)
asked Mar 24, 2017 in Algorithms Akriti sood 1.1k views
0 votes
1 answer
16
how many of the above statements are true?
asked Mar 13, 2017 in Algorithms Shubhanshu 118 views
34 votes
5 answers
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
asked Feb 14, 2017 in Algorithms Arjun 6.3k views
24 votes
6 answers
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}$
asked Feb 14, 2017 in Algorithms Madhav 3.3k views
0 votes
0 answers
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 - ?
asked Feb 5, 2017 in Programming yg92 179 views
0 votes
1 answer
20
2 votes
0 answers
21
Show the different minimum spanning Trees Possible in each of the following Algorithms Prims Algorithm Kruskal
asked Jan 26, 2017 in Algorithms Dulqar 253 views
3 votes
2 answers
23
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ? Any example which favours this ?
asked Jan 24, 2017 in Algorithms Kapil 2.2k views
0 votes
1 answer
24
Which of the following statements is true? Adding a constant to every edge weight in a directed graph can change the set of edges that belongs to minimum cost spanning tree. Assume unique weights. Complete graph with 4 vertices, each edges having same weights can have maximum ... no negative cycles). None of these how is 3rd wrong? If there is no negative cycles dijkstra can work just fine right?
asked Jan 24, 2017 in Algorithms S Ram 221 views
...