search
Log In

Recent questions tagged graph-algorithms

0 votes
1 answer
1
0 votes
1 answer
2
What are the appropriate data structures for graph traversal using Breadth First Search(BFS) and Depth First Search(DFS) algorithms? Stack for BFS and Queue for DFS Queue for BFS and Stack for DFS Stack for BFS and Stack for DFS Queue for BFS and Queue for DFS
asked Mar 30 in DS Lakshman Patel RJIT 95 views
0 votes
1 answer
3
Let $G$ be a graph with $n$ vertices and $m$ edges.What is the tightest upper bound on the running time of Depth First Search of $G$, when $G$ is represented using adjacency matrix? $O(n)$ $O(m+n)$ $O(n^2)$ $O(mn)$
asked Mar 30 in Algorithms Lakshman Patel RJIT 132 views
0 votes
1 answer
4
The diameter of a tree $T= (V, E)$ is defined as $max_{u,v\ \epsilon\ V}\ \delta(u,v)$, that is, the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.
asked Nov 12, 2019 in Algorithms KUSHAGRA गुप्ता 170 views
1 vote
1 answer
5
There are two types of professional wrestlers: babyfaces ( good guys ) and heels ( bad guys ). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of ... that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it.
asked Nov 12, 2019 in Algorithms KUSHAGRA गुप्ता 220 views
1 vote
1 answer
6
Give an example of a directed graph $G=(V, E)$, a source vertex $s\ \epsilon\ V$ , and a set of tree edges $E_{\Pi}\subseteq E$ such that for each vertex $v\ \epsilon\ V$ , the unique simple path in the graph $(V, E_{\Pi})$ from s to v is a shortest path in G, yet the set of edges $E_{\Pi}$ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.
asked Nov 12, 2019 in Algorithms KUSHAGRA गुप्ता 188 views
2 votes
3 answers
7
Match List-I with List-II: ... (c)-(i); (d)-(ii) (a) - (ii); (b)-(i); (c)-(iv); (d)-(iii) (a) - (iii); (b)-(i); (c)-(iv); (d)-(ii)
asked Jul 2, 2019 in Algorithms Arjun 540 views
2 votes
3 answers
8
If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ? A O(m logn) B O(n) C O(m) D O(n logm)
asked Jun 9, 2019 in Algorithms Hirak 406 views
1 vote
1 answer
9
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?
asked Apr 28, 2019 in Graph Theory gmrishikumar 198 views
0 votes
0 answers
10
Suppose that instead of a linked list, each array entry $adj[u]$ is a hash table containing the vertices $v$ for which $(u,v) \in E$. If all edge lookups are equally likely, what is the expected time to determine whether an edge is in ... have ? Suggest an alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table ?
asked Apr 7, 2019 in Algorithms akash.dinkar12 60 views
0 votes
0 answers
11
Most graph algorithms that take an adjacency-matrix representation as input require time $\Omega(V^2)$,but there are some exceptions. Show how to determine whether a directed graph $G$ contains a universal link $-$ a vertex with in-degree $|V-1|$ and out-degree $0$ in time $O(V)$ , given an adjacency matrix for $G$.
asked Apr 7, 2019 in Algorithms akash.dinkar12 63 views
0 votes
0 answers
12
The square of a directed graph $G=(V,E)$ is the graph $G^2=(V,E^2)$ such that $(u,v) \in E^2$ if and only $G$ contains a path with at most two edges between $u$ and $v$ .Describe efficient algorithms for computing $G^2$ and $G$ for both the adjacency list and adjacency-matrix representations of G. Analyze the running times of your algorithms.
asked Apr 7, 2019 in Algorithms akash.dinkar12 52 views
0 votes
1 answer
13
Given an adjacency-list representation of a multi graph $G=(V,E)$, describe an $O(V+E)$ time algorithm to compute the adjacency-list representation of the “equivalent” undirected graph $G’=(V,E’)$ , where $E’$ is consists of the edges in $E$ with all multiple edges between two vertices replaced by a single edge and with all self-loops removed.
asked Apr 7, 2019 in Algorithms akash.dinkar12 109 views
0 votes
0 answers
14
The transpose of a directed graph $G=(V,E)$ is the graph $G^T=(V,E^T)$, where $E^T=\{(v,u) \in V * V :(u,v) \in E \ \}$ .Thus ,$G^T$ is $G$ with all its edges reversed . Describe efficient algorithms for computing $G^T$ from $G$,for both the adjacency list and adjacency matrix representations of $G$. Analyze the running times of your algorithms.
asked Apr 7, 2019 in Algorithms akash.dinkar12 54 views
0 votes
1 answer
15
Give an adjacency-list representation for a complete binary tree on $7$ vertices. Give an equivalent adjacency-matrix representation. Assume that vertices are numbered from $1\ to\ 7$ as in a binary heap.
asked Apr 7, 2019 in Algorithms akash.dinkar12 53 views
0 votes
1 answer
16
Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex ? How long does it take to compute the in-degrees ?
asked Apr 7, 2019 in Algorithms akash.dinkar12 53 views
0 votes
0 answers
17
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between (A) k and n (B) k – 1 and k + 1 (C) k – 1 and n – 1 (D) k + 1 and n – k The answer is C . how is it k-1?? I mean if we have only one component .?Please explain
asked Mar 31, 2019 in Algorithms Doraemon 124 views
0 votes
0 answers
18
FOR THE EXTENDED-SHORTEST-PATH if we want to find the distance between 1->4 and the 1->5 +5->4 gives the shortest path and if 1->5 gets its shortest path as 1->2->5 and 5>4 gets its shortest path as 5->3->4 then how will we get it?? as one of the operands is always from the initial array.
asked Mar 30, 2019 in Programming Doraemon 52 views
1 vote
1 answer
19
0 votes
1 answer
20
Suppose that you are running Dijkstra’s algorithm on the edge-weighted diagram below, starting from vertex A. The Table gives ‘Distance’ and ‘Parent’ entry of each vertex after vertex E has been deleted from the priority queue and relaxed. Vertex Distance Parent A 0 Null B 2 A C 13 F D 23 A E 11 F F 7 B G 36 F H 19 E What could be the possible value of expression x+y?
asked Mar 10, 2019 in Algorithms noob_coder 672 views
1 vote
2 answers
21
What will be the path from A-H if BFS is used in the following graph?
asked Feb 2, 2019 in Algorithms saptarshiDey 183 views
0 votes
2 answers
22
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?
asked Jan 26, 2019 in Algorithms screddy1313 160 views
1 vote
1 answer
23
1 vote
2 answers
24
Which of the following statement is true? For a directed graph, the absence of back edges in a DFS tree can have cycle. If all edge in a graph have distinct weight then the shortest path between two vertices is unique. The depth of any DFS (Depth First Search) tree rooted at a vertex is atleast as depth of any BFS tree rooted at the same vertex. Both (a) and (c)
asked Jan 4, 2019 in Algorithms Abhishek Kumar 38 697 views
0 votes
0 answers
25
If the DFS finishing time f[u] < f[v] for two vertices u and v in a directed graph G, and u and v are in the same DFS tree in the DFS forest, then u is an ancestor of v in the depth first tree ? True /False can anyone explain it ?
asked Jan 2, 2019 in Algorithms Prince Sindhiya 143 views
0 votes
0 answers
26
Can someone please explain what are the types of edges possible in BFS and DFS for DIRECTED as well as UNDIRECTED graphs? Individual meaning of BACK, FRONT and CROSS edges is clear, but can’t decide which are present and which are not for Traversals. an example would be of great help or any specific reference on this.
asked Dec 30, 2018 in Algorithms Markzuck 437 views
3 votes
1 answer
27
Which of the following statements is/are correct with respect to Djikstra Algorithm? (P) It always works perfectly for graphs with negative weight edges. (Q) It does not work perfectly for graphs with negative weight cycles. (R) It may or may not work for graphs with negative weight edges. (S) It ... Only P, Q, S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct
asked Dec 27, 2018 in Algorithms Ruturaj Mohanty 301 views
0 votes
0 answers
28
According To Me Answer Should Be 6… Anyone Please Try Once!!! Given Is 5 With No Explaination !!!! like 11-12-12 then for second square 4 times 13 so c(4,2) any two of then lead to me @ answer @6.
asked Dec 26, 2018 in Algorithms CHïntän ÞäTël 113 views
0 votes
1 answer
29
True or False , with reason. For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic? Answer is False Explanation: FALSE. It is true that the absence of back edges with respect to a DFS tree implies ... construct a cycle using such cross edges (which decrease the level) and using forward edges (which increase the level) Can someone explain it ?
asked Dec 25, 2018 in Algorithms Sandy Sharma 357 views
1 vote
1 answer
30
Which of the following condition is sufficient to detect cycle in a directed graph? (A) There is an edge from currently being visited node to an already visited node. (B) There is an edge from currently being visited node to an ancestor of currently visited node in DFS forest. (C) Every node is seen twice in DFS. (D) None of the bove here option B is right, but why not option A?
asked Dec 12, 2018 in Algorithms Gangani_Son 2k views
...