Register

Recent questions tagged graph-algorithms

1 votes
1 answer
151
Self doubt
Is this statement correct?? and why? .If there are negative weight cycles than dijkstra will surely fail but if there are negative weight edges(need not be cycle) then dijkstra may or may not fail.
Is this statement correct?? and why?.If there are negative weight cycles than dijkstra will surely fail but if there are negative weight edges(need not be cycle) then dij...
User Avatar
4 votes
2 answers
152
ISRO2018-33
Which of the following is application of Breath First Search on the graph? Finding diameter of the graph Finding bipartite graph Both (a) and (b) None of the above
Which of the following is application of Breath First Search on the graph?Finding diameter of the graphFinding bipartite graphBoth (a) and (b)None of the above
User Avatar
3 votes
2 answers
153
#Graph Theory #Algorithms Self Doubt about Dense Graphs.
Please give some example regarding number of edges in dense graph is - |E| < |V2| I get that when we take log both sides we get O(ElogV), but I can't get this |E| < |V2|
Please give some example regarding number of edges in dense graph is - |E| < |V2|I get that when we take log both sides we get O(ElogV), but I can't get this |E| < |V2|
User Avatar
0 votes
1 answer
154
#Algorithms How is this equivalent in Kruskal's Algorithm's Time Complexity?
Kruskal Time complexity is O(mlog m) then how in upper bound it can be written as - O(m2) ----> How log m = O(m) and O (mn) ---------> How log n = O(n)
Kruskal Time complexity is O(mlog m) then how in upper bound it can be written as - O(m2) How log m = O(m)and O (mn) - How log n = O(n)
User Avatar
0 votes
0 answers
159
DFS Modification
How DFS(Depth First Search) modification is used to find whether a graph is planar or not ?
How DFS(Depth First Search) modification is used to find whether a graph is planar or not ?
User Avatar
1 votes
0 answers
161
Minimum Spanning Tree Problem
Given a graph with positive and distinct edge weights. If I double or triple.. the edge weights then:- 1. Shortest path will remain same 2. Mst will remain same Right? Note : Here i am doubling or tripling or four times ..... not increasing by +c
Given a graph with positive and distinct edge weights. If I double or triple.. the edge weights then:- 1. Shortest path will remain same2. Mst will remain sameRight?Note ...
User Avatar
35 votes
9 answers
163
GATE CSE 2018 | Question: 47
Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.
Consider the following undirected graph $G$:Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $...
User Avatar
3 votes
3 answers
166
Ace Test Series: Graph Theory - Number Of Spanning Trees
How to approach such questions ? Please provide detailed solution. Answer given is option C
How to approach such questions ? Please provide detailed solution. Answer given is option C
User Avatar
2 votes
2 answers
172
DFS Traversal
If DFS algorithm applied starting from vertex ‘A’ which uses stack data structure then the height of stack is needed in worst case for DFS traversal is _________.
If DFS algorithm applied starting from vertex ‘A’ which uses stack data structure then the height of stack is needed in worst case for DFS traversal is _________.
User Avatar
2 votes
0 answers
174
NO Of BFS traversal
what is the question asking exactly?
what is the question asking exactly?
User Avatar
5 votes
0 answers
175
minimum spanning tree
User Avatar
2 votes
0 answers
176
MadeEasy Test Series 2018: Algorithms - Graph Algorithms
For a directed graph, the absence of back edges in a DFS tree can have cycle. true or fale.please explain with an example.
For a directed graph, the absence of back edges in a DFS tree can have cycle.true or fale.please explain with an example.
User Avatar
Page: