The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+5 votes

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.1k points)
edited by | 389 views

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?

@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.

from CLRS :

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

Please see DFS visulization on some disconnected graphs here :

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 

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.


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

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

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


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 : and 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.4k points)
edited by
@lucky,they are saying same number of tree edges,which i think is true as each traversal will give same number of edges.
There is difference between same tree and same tree edges.

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

Number of tree edges will always be same. :) I overlooked the statement.
but i have got a doubt now..will number of tree edges will be same??
Tree edges will always be n-1 if n is the number of nodes.
i am getting confused with 'edges' and 'tree edges' here..are they same terms..they are not same.right??
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.

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

0 are absolutely correct.

Related questions

+1 vote
0 answers
0 votes
0 answers
asked Aug 27, 2018 in Operating System by Avik Chowdhury Junior (621 points) | 16 views
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
49,823 questions
54,818 answers
80,991 users