10. Depth-First Search

Рет қаралды 38,543

Күн бұрын

Пікірлер: 37

@ParthPatel-vj2zv 3 жыл бұрын

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

@brian87147 3 жыл бұрын

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

Жыл бұрын

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

@webdevelopmentwithjavascri8020 2 жыл бұрын

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

@ahmadbittar4618 3 жыл бұрын

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

@alfredwindslow1894 4 ай бұрын

@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 3 жыл бұрын

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

@259_parthpatidar9 2 жыл бұрын

😂

@freeeagle6074 2 жыл бұрын

Then the weight would be infinity.

@alfredwindslow1894 4 ай бұрын

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

@w1d3r75 3 жыл бұрын

A complete playlist in a day? Nice

@sanjaykrishnan2052 3 жыл бұрын

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

@sungjuyea4627 2 жыл бұрын

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

@longmen8622 2 жыл бұрын

I like this guy's teaching style.

@hanyanglee9018 2 жыл бұрын

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

@qiguosun129 3 жыл бұрын

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

@TimothyRourke 3 жыл бұрын

My only guess is COVID. He's great.

@nathantaylor7026 3 ай бұрын

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

@ashishjain871 5 ай бұрын

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.

@alfredwindslow1894 4 ай бұрын

This is a valid point. BFS was claimed to be O(|V| + |E|) as we initialise a parent array of size |V| at the start of the algorithm which of course takes O(|V|) time. DFS was claimed to be O(|E|), but it still requires some method of tracking the parent of each node in the parent/path tree. Why would we say this takes O(|V|) time for BFS and not O(|V|) time for DFS search when it is the same requirement? As you said, we could initialise a hash map and have it grow dynamically for tracking the parents. This would be O(1) to build, and have O(1) expected and amortised inserts resulting in O(|E|) time for the algorithm (as the number of vertices in our final path tree must be bound by the number of edges).

@milanlazov Жыл бұрын

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

@johnultra4546 Жыл бұрын

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

@coding99 Жыл бұрын

We still need |V| time for initialization. Watch lecture 9 for explanation kzbin.info/www/bejne/pXe5iomwodueb8Usi=uJI_9TsWikCnkCl9 (50:10)

@kafychannel Жыл бұрын

fire guys really cool thanks!

@karthikKarthik-by6ws 2 жыл бұрын

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 .

@yasirejaz199 2 жыл бұрын

The runtime of both BFS and DFS algorithms is O ( |V| ) + O ( |E| )

@carlosmateosamudiolezcano2463 Жыл бұрын

@@yasirejaz199 Correct. For DFS you still need to initialize a list of size |V| to keep track of visited vertices. Otherwise you will just keep recursing if there is a loop.

@ritikraj07 Жыл бұрын

@@carlosmateosamudiolezcano2463 exactly,why did the proffesor told it is O(|E|) time about the depth first search

@TheSdsaad Жыл бұрын

@@ritikraj07 The O(|E|) runtime is about a single run of DFS starting from some node. If your entire graph is one single connected component, then running DFS from any arbitrary vertex will touch every other vertex. It is O(|E|) because you need |V| - 1 edges to connect a graph with |V| nodes and once you touch a vertex you will never see it again in one iteration of DFS. The runtime of DFS in a graph with more than one connected component is O(|V| + |E|) which they mention later in the video under Full DFS.

@VedantKumar Жыл бұрын

@@TheSdsaadDon't we still need a O(V) array of Parents to keep track of the vertices? We can either use a parent array or use a visited array but it will be needed in any case. That would make the complexity O(V+E)