Testbook live Testseries

Question

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.

Comments

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 : 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)

Answer 1

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.

Comments

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 DFT..am i correct?and hence,they will be equal in number in any DFT

---

Yes..you are absolutely correct.