The Gateway to Computer Science Excellence
+5 votes
393 views

Which of the following statements are false ?

$1.$ A depth-first search of a directed graph always produces the same number of tree edges (i.e., independent of the order in which the vertices are provided and independent of the order of the adjacency list).

$2.$ Both DFS and BFS require $\Omega(n)$ storage for their operation.

$3.$ If we double the weight of every edge in the graph shortest path between any two vertices will not change.

$4.$ Dijkstra's algorithm may not terminate if the graph contains negative weight edges.

in Algorithms by Boss (12.2k points)
edited by | 393 views
0

@mcjoshi ..what you are showing from wiki is the dfs function. That I think does not represent depth first search on a graph. I might be wrong, that is what I think.

0

@sushant ??

@Debashish. Rahul is considering 2 diff graphs because of the statement in brackets

  1. Order of giving vertices input to dfs. 
  2. Order of storing adjacency list 

You think these two statements make a connected graph disconnected? 

Or 

You think these two statements make a disconnected graph connected?

0

@rahul same QS to you : please explain :

If we consider same graph then yes same edges but if we consider all possible cases, false. Idenpendent of the order of vertices adjacency list, means they want to say for a same graph??

 order of vertices adjacency list : will this delete some edge to make a already connected graph disconnected?

Or in the reverse way ,

 order of vertices adjacency list : will this add some edges to make a earlier disconnected graph connected ?

+1
@Debashish. I think you are right. Given a directed graph, any way we arrange the list, the structure of graph doesnt change
0

what about this???

0

Debasish, first statement is false.

Tree resulted from DFS spans to only one connected component. Now if a graph contains $2$ connected components, then applying DFS on graph of any vertex in first and in second of two component may result different number of tree edges.

In graph above DFS, starting from vertex $2$ gives $3$ tree edges, but only $1$ tree edge if i apply DFS on vertex-3

+1

@rahul These two are different graph $G1$ and $G2$:

  • Assume $G1$ list is $adj1$
  • Order of storing vertices in $adj1$ can not make $G1$ turned into $G2$ 
  • If you can show any such $adj1$ storing patterns, then please show.
0
No, it's one graph having two connected components. forming adj matrix for above one will be time consuming.
But Suppose adjaceny matrix of a graph contains all $0's$ in 2'nd row and 2'nd column, than it forms 2 components one just a vertex-2 and another remaining part.
+1

mcjoshi  I got your idea in the very first comment of yours.

Tree resulted from DFS spans to only one connected component.

Do we need no of edges in that tree ? Or, no of edges in the complete graph search

  • You are exploring only one tree. And terminated after searching only one component of a GIVEN GRAPH
  • and giving different vertices to ONE DFS CALL from different component and trying to see different no of tree edges to make statement $1$ false.
  • My argument was ONE DFS CALL MAY NOT SUFFICE a complete graph search
0
DFS() is simply a function, which when applied gives a tree by marking them in visited array and stops, so not necessary to cover whole graph.

Debashish, I have not drawn above graph, i simply took it from a online DFS visulization tool.
+1

Ok my last QS ?

so not necessary to cover whole graph.

Using DFS search  (not function or something else)  you will visit only ONE component, whatever may be the graph always?

+1
@Debashish I got my mistake they wanted to say order of vertices can be different in adj. List but I was taking different  adjacency lists itself.
+1

from CLRS :

0
Yes, DFS on a graph having many components covers only $1$ component.

Please see DFS visulization on some disconnected graphs here : https://www.cs.usfca.edu/~galles/visualization/DFS.html
+1

That simulation based on some code.

Yes, DFS on a graph having many components covers only 1 component.

If this is true. I have nothing to say 

0
no i don't think mc_joshi here is correct! This staement "DFS on  graph having many components covers only 1 component" it can never be true. when we run DFS algo, the loop covers  all the vertex and in case of disconnected graph, we can always be sure that the component will always get visited even if it is disconnected. as forr loop will cover the disconnected component too because thta disconnected componenet is unmarked, and i agree with deabshish here. option a should be true.
0

@pikachu

I don't know how to make you believe that it is true.

0
That quora thread discuss how to find a graph is connected or not using dfs.
+1

mc_joshi, i want to ask you a counter ques. for sake of arg. , for 2 mins, forget any reasoning for this statement.

The first and foremost basic point is DFS is graph travrsing algo.right!!i.e we can traverse a graph using this algo. and traversing of graph is visiting each node once. it does not matter if graph is connected or not, the condition for any traversal graph is to traverse each node because this is algo's primary purpose which is why it is created . i have not seen that quora link but yeah it is true that DFS_VISIT funt(recursive one)  inside the cde when we call, if graph is disconnected it will return after covering all the vertexes of that component but do remember DFS also contain an outer loop too which goes from 0 to v-1. it is added due to this case itself. if it would have been only the DFS visit procedure, you are right. but here we are talking of whole DFS algo, and it will run for all the vertex, and tree edges won't change. correct me if i am wrong!

@debashish, @mc_joshi

+1

Debasish, right but i just wanted to make point that simple DFS does not find no. of connected components, it finds yes or no by seeing visited array after DFS.

pikachu, According to me DFS on a graph means Simply using DFS() function, which spans to only $1$ component, and if it contains outer loop that (for all vertex if not visited apply DFS()) then necessarily all components are covered. Agree!!!

So, Our main disagreement is which one these two implementations is DFS()

I tried two visulization tools : https://visualgo.net/dfsbfs and https://www.cs.usfca.edu/~galles/visualization/DFS.html on disconnected graphs, but still you may disagree as it depends on how they implemented it (as their implementation need not be correct)

I searched wikipedia for Pseducode :::

I searched stackoverflow didn't get results, so asked a new question. I don't know what else to say, but as of now for me DFS() means above implementation. (but i may be wrong)

1 Answer

0 votes
When we traverse a graph, and we get a tree.

By depth first traversal, we get DFT. So the edges of graph that are present in DFT are called tree edges. There are back edges, cross edges, which are not present in the tree.

So, he is saying in first statement that, no matter how we traverse the graph, we will get the  same number of tree edges.

Which is correct.
by Active (4.5k points)
edited by
+1
@lucky,they are saying same number of tree edges,which i think is true as each traversal will give same number of edges.
0
There is difference between same tree and same tree edges.

In DFT , we always get same edges. DFT is spanning tree, right?
0
oh yes yes.

Number of tree edges will always be same. :) I overlooked the statement.
0
but i have got a doubt now..will number of tree edges will be same??
0
Tree edges will always be n-1 if n is the number of nodes.
0
i am getting confused with 'edges' and 'tree edges' here..are they same terms..they are not same.right??
0
Edges are the part of graph right. It may be a tree.

Here if he would have said just edges. We cannot say that what he is talking. Generally we will assume graph edges only.

Don't pay too much attention on this thing. In exam it will be clearly mentioned.
+1

here,all blue ones are tree edges..right?that is tree edges are edges of DFT..am i correct?and hence,they will be equal in number in any DFT

0
Yes..you are absolutely correct.
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
50,650 questions
56,242 answers
194,293 comments
95,943 users