10. Depth-First Search

MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Justin Solomon

This class builds on the previous lecture of breadth-first search (BFS) by introducing depth-first search (DFS) and full-BFS and full-DFS. The lecture continues with topological sorts and cycle detection.

License: Creative Commons BY-NC-SA

[ParthPatel-vjzv]

0:00 review of prev class
7:10 single source reachability
10:52 DFS algorithm
14:11 proof of correctness of DFS algo
25:08 connectivity in an undirected graph, connected components
28:32 full DFS to find all connected components of a graph
32:03 DAGs, topological order, finishing order
36:49 proof of 'reverse finishing order is a topological order'
44:22 cycle detection in a directed graph
47:45 returning (vertices, edges) forming a cycle

[brian]

he seems so happy as if i understand what hes talking about.

His enthusiasm is contagious. This guy loves what he does.

[webdevelopmentwithjavascri]

Love this professor's class. He is always enthusiastic. It is kind of contagious.

[ahmadbittar]

I noticed that this professor has the best videos on YouTube about computer science.

[alfredwindslow]

I believe the time complexity of efficient implementations of both DFS and BFS would be O(|V'| + |E'|) where V' and E' are the number of vertices and edges in the subgraph of (V, E) in which nodes are reachable from the source. In the 'worst' case where every node is reachable from the source this would simply be O(|V| + |E|), but if the graph is heavily disconnected then it could be considerably less.

The number of vertices |V'| in the reachable graph from the source would have to be bound by the number of edges within it. As a vertex cannot be connected without an edge connecting it. So I suppose we could simplify the complexity to just O(|E'|)

[alfredwindslow]

@30:30, Full BFS is stated to be O(|V| + |E|) time. However with the implementation given in lecture 9 where for each BFS invocation we initialise a parent array of size |V|, then worst case full BFS would take O(|V|^2) time as for example we could have a graph where each node is disconnected/not reachable from every other node. So we would have |V| * |V| initialisations of the parent array of size |V|.

I suppose we could actually get away with reusing the parent array across BFS invocations as each one should be using distinct subsets of the elements inside the parent array as each connected component has distinct vertices. Or we could use a hash map which dynamically grows in proportion to the number of vertices found so far in the BFS. But neither of these are what the implementation given is doing.

[TimothyRourke]

What if your neighbors don't like it when you traverse them?

[nathantaylor]

31:20 : new life goal: be in a blood oath with Justin and Erik

[sanjaykrishnan]

I love how he says dubya (w). But yes, great vid, tysm

[sungjuyea]

So this is the first lecture(not including recitations) that the whole classrooom is empty due to COVID?

[hanyanglee]

13:00 How did the professor write the "4" like that???

[ashishjain]

Instructor mentions DFS takes O(|E|) time as opposed to O(|V|+|E|) time taken by BFS. This is not true because the initialization itself (for example the parents array) will take O(|V|) time, and therefore, the DFS algorithm should take O(|V|+|E|) time. We can of course maintain a hash table for the parent, and therefore, we don't need to initialize anything. Now the absence of a node in the hash table can signal that the node is not reachable from the source. If we do that, then, sure, DFS can take O(|E|) time as per the instructor's DFS algorithm.

[longmen]

I like this guy's teaching style.

[milanlazov]

41:51 bro just threw it on the floor because he needed to free his hand 🤣🤣

[johnultra]

Great lecture. Doesn't BFS on a graph with |V| vertices and no edges take O(1)?

[brendandesjardins]

damnnn why aint nobody show up for this lecture 😭😭

[karthikKarthik-byws]

Help me out!!!!
I have doubt on the efficiency of BFS : Is it O ( |E| ) or O ( |V| ) + O ( |E| ) ???
You proved, ' recursive neighbors are reachable'
number of comparisons operation : = O(1) * |deg+(recursive neighbors)| = O ( |deg+(recursive neighbors)| )
setting parent operation : = O(1) *| recursive neighbors| = O (| recursive neighbors|)
efficiency of BFS : = O ( |deg+(recursive neighbors)| ) + O (| recursive neighbors|)
In the worst case,
efficiency of BFS : = O ( |V| ) + O ( |E| ) when each vertex can reach every other vertices .

[qiguosun]

Why do there seem to be fewer students, I think this guy is excellent

[crestz]

90% of the students decided to skip class