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?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

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

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.

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

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

+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?

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

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.

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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 6k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 16

40,958 questions

47,599 answers

146,674 comments

62,335 users