# Recent questions tagged graph-algorithms

1
We have a Directed Graph with 100 vertexes. v1 --> v2 --> ... v100 and all edges weights is equal to 1. we want to used bellman-ford for finding all shortest paths from v1 to other vertexes. this algorithm in each step check all edges in arbitrary order. if in ... is the minimum and maximum of steps in this problem? ُSolution says 2 and 100. anyone can say how the min and max steps is calculated?
2
Algorithm which solves the all pair shortest path problem is A)Dijkstra's algorithm B)Floyd's algorith C)Prim's algorithmm D)Warshall's algorithm
3
Djikstra&rsquo;s algorithm is used to Create LSAs Flood an internet with information Calculate the routing tables Create a link state database
4
Someone claims that Kruskal's algorithm for finding minimum spanning tree can return different spanning trees for the same input graph $G$. Do you agree with the claim? If so, why? If not, argue briefly why the claim is incorrect.
1 vote
5
Let $G = (V, E)$ be an undirected weighted graph with all edge weights being positive. Design an efficient algorithm to find the maximum spanning tree of $G$.
6
Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also compute, for a given source vertex $s \epsilon V$ , the shortest paths from s to every other ... you claim the statement is true or a counterexample if the statement is false. All the shortest paths from $s$ to the other vertices are unchanged.
7
You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends to help you and each task can be done by either you or any of your ... constraints. Model this problem formally using graphs. Describe an efficient algorithm for the problem and analyze the worst-case complexity of your algorithm.
1 vote
8
Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also compute, for a given source vertex $s \epsilon V$ , the shortest paths from s to every other vertex in ... argument if you claim the statement is true or a counterexample if the statement is false. $T$ is still a minimum cost spanning tree of $G$.
1 vote
9
Let $G=(V,E)$ be a undirected graph. We say $S \subseteq V$ is a clique if and only if for all $u,\: v \: \in S$, the edge $(u, v)$ is in $E$. Now let $G=(V,E)$ be a graph in which each vertex has degree at most 5. Give an algorithm to find the largest clique in $G$. What is the complexity of your algorithm?
10
An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $0 < \mid i-j\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below. The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n=10$ is $11$ $25$ $31$ $41$
11
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 to ... s to V2 separately then also we will have V1 and V2 simulatenously on call stack if we have a path from s to V2 via V1 .
12
I am referring http://www.geeksforgeeks.org/union-find/ I am getting worst case complexity as O(V2), whereas on geeksforgeeks it is given O(ElogV). My Approach:- Consider a graph 1---->2----->3----->4------>5------>6------>7------->.......V 1+2+3+.....V = O(V2). Kindly explain with proper explanation
13
what is the suitable algorithm for the construction of leaf constrined minimum spanning tree .
14
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
15
In an adjacency list representation of an undirected simple graph $G=(V, E)$, each edge $(u, v)$ has two adjacency list entries: $[v]$ in the adjacency list of $u$, and $[u]$ in the adjacency list of $v$. These are called twins of each other. A twin pointer is a pointer from an ... list? $\Theta\left(n^{2}\right)$ $\Theta\left(n+m\right)$ $\Theta\left(m^{2}\right)$ $\Theta\left(n^{4}\right)$
16
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{th}$ vertex in this BFS traversal, then the maximum possible value of $n$ is __________
17
18
Argument: As it a complete tree, maximum BFS level possible are log(n). And as BFS time is O(n+E) , taking E as path cost , it will give O(n+logn) which is O(n). So, I ticked B. Answer is given as C. But, if we take a vertex just in the first level , so the time cost will be Omega(1). So, C must not be true. Where am I going wrong??
19
(A). When a recurrence relation has a cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program. (B). Given a connected graph $G(V,E)$ if a vertex $v$ $\epsilon$ $V$ is visited during level $K$ of a breadth ... every other possible path should have the length of atleast 'k'. Given wording is 'atmost'. So, B should be wrong. Given answer is D.
20
Answer is given as (B). But, shouldn't it relax point 'c' via 'a' .. So, i guess answer should be D. Is it?
21
Acc. to dijkstra's algorithm: What will be the shortest path from A to B ? 1) When the edge of length 15 is present. 2) when the edge of length 15 is removed.
1 vote
22
23
Which of the following statements is/are true? S1: Dijkstra’s algorithm is not affected by negative edge weight cycles in the graph and gives correct shortest path. S2: Bellman ford algorithm finds all negative edge weight cycles present in the graph. a) Only S2 b) Only S1 c) Both S1 and S2 d) Neither S1 and nor S2
24
Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below. Which of the following is not a topological ordering? $1$ $2$ $3$ $4$ $5$ $6$ $1$ $3$ $2$ $4$ $5$ $6$ $1$ $3$ $2$ $4$ $6$ $5$ $3$ $2$ $4$ $1$ $6$ $5$
25
Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best minimum spanning ... minimum spanning tree here. There is unique minimum spanning tree, however there is more than one second-best minimum spanning tree here.
26
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? cost$(a, b) \geq 6$. cost$(b, e) \geq 5$. cost$(e, f) \geq 5$. cost$(a, d) \geq 4$. cost$(b, c) \geq 4$.
Consider the following directed graph. Suppose a depth-first traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the alphabetical order is to be chosen. Suppose the number of tree edges is $T$, the number of back edges is $B$ and the number of cross edges is $C$ ... $T = 3$. $B = 1$, $C = 2$, and $T = 3$. $B = 2$, $C = 2$, and $T = 1$.
Let $G$ be an undirected graph with $n$ vertices. For any subset $S$ of vertices, the set of neighbours of $S$ consists of the union of $S$ and the set of vertices $S'$ that are connected to some vertex in $S$ by an edge of $G$. The graph $G$ has the nice property that every subset of ... $O \left(\sqrt{n}\right)$ but not $O (\log n)$ $O (n)$ but not $O \left(\sqrt{n}\right)$
Given a weighted directed graph with $n$ vertices where edge weights are integers (positive, zero, or negative), determining whether there are paths of arbitrarily large weight can be performed in time $O(n)$ $O(n . \log(n))$ but not $O (n)$ $O(n^{1.5})$ but not $O (n \log n)$ $O(n^{3})$ but not $O(n^{1.5})$ $O(2^{n})$ but not $O(n^{3})$