menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Recent questions tagged graph-algorithms

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions tagged graph-algorithms

1 vote
0 answers
2
Cormen 3rd edition chapter 22 question: 22.4.4
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.
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.
asked Jul 4, 2018 in Algorithms Abhilash Mishra 207 views
0 votes
2 answers
3
BFS Traversal
How through a BFS we can find graph is connected or disconnected? Plz give some example and explain
How through a BFS we can find graph is connected or disconnected? Plz give some example and explain
asked Jun 30, 2018 in Algorithms srestha 179 views
0 votes
1 answer
4
graph_doubt
"edge disjoint spanning tree" means ?
"edge disjoint spanning tree" means ?
asked Jun 30, 2018 in Algorithms air1ankit 71 views
0 votes
0 answers
5
Testbook Test Series: Algorithms - Graph Algorithms
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.$ In a ... , then the breadth-first search order of vertices is a valid order in which to tackle the tasks. Which of the above is TRUE?
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?
asked Jun 19, 2018 in Algorithms Sandy Sharma 574 views
1 vote
1 answer
6
#Algortihms Gate 2000 Question Self Doubt
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 ... being, since (u,v) is an edge in G therefore they can only be SIBLINGS in DFS tree and never have descendant relationship?
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?
asked May 29, 2018 in Algorithms iarnav 237 views
4 votes
1 answer
7
#Algorithms #DFS
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$ ... in the graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.
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.
asked May 28, 2018 in Algorithms iarnav 417 views
3 votes
1 answer
8
#Algorithms Gate 2005 Question Self Doubt.
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 ... the diagonal elements in adjacency matrix is = 0. You can take a Graph with 4 vertices and make anyone of them as a sink.
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.
asked May 23, 2018 in Algorithms iarnav 538 views
0 votes
0 answers
9
Gate 2003 Graph-Algorithms Question Doubt.
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 ... valid explanation at all. So, anyone help me get this in a simple layman terms, I'll be very much thankful to them.
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.
asked May 18, 2018 in Algorithms iarnav 189 views
0 votes
0 answers
11
#Algorithms #DFS How to find if a directed graph G is strongly connected using DFS in one pass?
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.
asked May 13, 2018 in Algorithms iarnav 189 views
0 votes
1 answer
12
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 ________? Soln. Its a simple piece of cake we just need to find that path which leads to maximum nodes ... 0 and when to start counting with 1 because such type of ambiguous question always let my question go wrong and its painful :(
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 :(
asked May 6, 2018 in Algorithms Na462 673 views
4 votes
1 answer
13
Minimum Spanning Tree
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
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
asked Apr 30, 2018 in Algorithms srestha 1.2k views
0 votes
3 answers
14
#Algorithms #MST Doubt in MST Questions.
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST? Question2 ) Prim's algorithm works with negative weighted edges?
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST? Question2 ) Prim's algorithm works with negative weighted edges?
asked Apr 29, 2018 in Algorithms iarnav 306 views
1 vote
1 answer
15
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 dijkstra may or may not fail.
asked Apr 24, 2018 in Algorithms Sandy Sharma 266 views
2 votes
3 answers
16
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 graph Finding bipartite graph Both (a) and (b) None of the above
asked Apr 22, 2018 in Algorithms Arjun 1.5k views
0 votes
1 answer
17
#Algorithms How is this equivalent in Kruskal's Algorithm's Time Complexity?
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)
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)
asked Apr 21, 2018 in Algorithms iarnav 365 views
0 votes
0 answers
19
Implementing Graph Data structure in C++
//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; ... endl; cin>>e; create_graph(v, e); print_adj_list(); return 0; } How to get rid of this problem?
//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?
asked Apr 8, 2018 in Programming Jason 171 views
0 votes
0 answers
20
Equality of shortest path tree for given node as a root and
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 ... isnt both things (shortest-paths tree with root $i$ and predecessor subgraph of $G$ for $i$) the same?
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?
asked Mar 24, 2018 in Programming GateAspirant999 115 views
0 votes
0 answers
21
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 ?
asked Mar 21, 2018 in Algorithms ankitgupta.1729 431 views
1 vote
2 answers
22
Minimum Spanning Tree Problem
asked Mar 19, 2018 in Algorithms pankaj_vir 919 views
1 vote
0 answers
23
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 same 2. Mst will remain same Right? Note : Here i am doubling or tripling or four times ..... not increasing by +c
asked Feb 19, 2018 in Algorithms Na462 347 views
0 votes
0 answers
24
DFS-Algorithm
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?
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?
asked Feb 18, 2018 in Algorithms Na462 324 views
25 votes
7 answers
25
GATE2018-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 $G$ for this value of $x$ is ____.
asked Feb 14, 2018 in Algorithms gatecse 8.2k views
46 votes
4 answers
26
GATE2018-43
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 ... $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z$ = ____
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$ = ____
asked Feb 14, 2018 in Algorithms gatecse 9.8k views
2 votes
3 answers
27
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
asked Feb 2, 2018 in Graph Theory kapilbk1996 1.5k views
6 votes
1 answer
28
Back edge,tree edge,forward edges in BFS
Consider the following statements: 1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff it has at least two children. 2. When BFS is carried out on a directed ... back edge, or cross edge and not forward edge as in the case of DFS. Find TRUE or FALSE for both the statements
Consider the following statements: 1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff it has at least two children. 2. When BFS is carried out on a directed graph G, the edges of G will ... as tree edge, back edge, or cross edge and not forward edge as in the case of DFS. Find TRUE or FALSE for both the statements
asked Jan 27, 2018 in DS MIRIYALA JEEVAN KUMA 5.1k views
6 votes
2 answers
29
True/False
Which of the following statements related to graphs are True? Minimum Spanning Tree has ALWAYS Minimum weight edge included in it. Minimum Spanning Tree MIGHT have Maximum weight edge weight included in it. Maximum Spanning Tree has ALWAYS Maximum weight edge included ... edge included in it. Longest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
Which of the following statements related to graphs are True? Minimum Spanning Tree has ALWAYS Minimum weight edge included in it. Minimum Spanning Tree MIGHT have Maximum weight edge weight included in it. Maximum Spanning Tree has ALWAYS Maximum weight edge included in ... weight edge included in it. Longest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
asked Jan 27, 2018 in Graph Theory Balaji Jegan 624 views
4 votes
1 answer
30
DFS- depth first search
asked Jan 25, 2018 in DS budhu 225 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...