# Recent questions tagged graph-algorithms

1 vote
1
I read that the space complexity of Dijasktra is $O(V^2)$ . (http://igraph.wikidot.com/algorithm-space-time-complexity) But how ????
1 vote
2
Prove or disprove: If a directed graph G contains cycles, then TOPOLOGICAL SORT $(G)$ produces a vertex ordering that minimizes the number of “bad” edges that are inconsistent with the ordering produced.
3
How through a BFS we can find graph is connected or disconnected? Plz give some example and explain
4
"edge disjoint spanning tree" means ?
5
Consider the following statements: $A.$ In a weighted undirected graph $G = (V, E, w)$, breadth-first search from a vertex s finds single-source shortest paths from s (via parent pointers) in $O(V + E)$ time. $B.$ ... $v$ happens), then the breadth-first search order of vertices is a valid order in which to tackle the tasks. Which of the above is TRUE?
1 vote
6
Source - Here Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the ... edge. Point being, since (u,v) is an edge in G therefore they can only be SIBLINGS in DFS tree and never have descendant relationship?
7
Consider the tree arcs of a $DFS$ traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing the shortest path between every pair of vertices. the shortest path from $W$ to every vertex in the graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.
8
Source of the question - here A sink in a directed graph is a vertex i such that there is an edge from every vertex $j ≠ i$ to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where ... sink as all the diagonal elements in adjacency matrix is = 0. You can take a Graph with 4 vertices and make anyone of them as a sink.
9
You can refer this question here - https://gateoverflow.in/957/gate2003-70. I have tried so much to understand this question, but I'm not getting it, how to take the sample graph and also, how to consider the options! In fact, options are very hard to comprehend. I've ... 't have a valid explanation at all. So, anyone help me get this in a simple layman terms, I'll be very much thankful to them.
10
Is it Dynamic programming?
11
I know, Kosaraju algorithm and there's one other algorithm which involves reversing of G and using DFS, but two times, but there's some algorithm which uses DFS only time, but I can't be able find that algorithm. Someone please share that.
12
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 ________? Soln. Its a simple piece of cake we just need to find that path which leads to maximum nodes because ... with 0 and when to start counting with 1 because such type of ambiguous question always let my question go wrong and its painful :(
13
1) Kruskal Algorithm 2) Prims Algorithm 3) Dijkstra Algorithm 4) Bellman Ford Algorithm 5) Floyd Warshall Algorithm Among these which one works for only i) Positive edge weight ii) Negative edge weight iii) Negative weight cycle
14
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST? Question2 ) Prim's algorithm works with negative weighted edges?
1 vote
15
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.
16
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
17
Kruskal Time complexity is O(mlogm) then how in upper bound it can be written as - O(m2) ----> How logm = O(m) and O (mn) ---------> How logn = O(n)
18
Some say answer is 2n and someplace else it's been told 2n-1-1. So, what's the corrent one?
19
//Just check create_graph function. #include <iostream> #include <malloc.h> using namespace std; struct Adj_node { int node; struct Adj_node *next; }; typedef struct Adj_node Adj_node; struct Edge { int src, dest; }; typedef struct Edge Edge; struct Graph { int v, e; Edge *edge; ... number of edges:"<<endl; cin>>e; create_graph(v, e); print_adj_list(); return 0; } How to get rid of this problem?
20
I have a small doubt. Chapter 25 All pairs shortest path of CLRS says following: To solve the all-pairs shortest-paths problem on an input adjacency matrix, we need to compute not only the shortest-path weights but also a predecessor matrix $\Pi=(\pi_{ij})$, where $\pi_{ij}$ ... $i$ and predecessor subgraph of $G$ for $i$) the same?
21
How DFS(Depth First Search) modification is used to find whether a graph is planar or not ?
1 vote
22
1 vote
23
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
24
Let T be a depth first search tree in an undirected graph G. Vertices u and ν are leaves of this tree T. The degrees of both u and ν in G are at least 2. In such case in the graph there will be two cycles :- One Cycle will contain u and other one v. There cannot be a graph containig a single cycle and containing both u and v and also satisfy above Constraint. Am I right?
25
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 ____.
26
Let $G$ be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent numbers in the label of $v$. Let $y$ denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z$ = ____