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
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'|)
@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.
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.
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).
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 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 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.
@@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)
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
he seems so happy as if i understand what hes talking about.
His enthusiasm is contagious. This guy loves what he does.
Love this professor's class. He is always enthusiastic. It is kind of contagious.
I noticed that this professor has the best videos on UA-cam about computer science.
What if your neighbors don't like it when you traverse them?
😂
Then the weight would be infinity.
13:00 How did the professor write the "4" like that???
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'|)
So this is the first lecture(not including recitations) that the whole classrooom is empty due to COVID?
@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.
I love how he says dubya (w). But yes, great vid, tysm
A complete playlist in a day? Nice
41:51 bro just threw it on the floor because he needed to free his hand 🤣🤣
31:20 : new life goal: be in a blood oath with Justin and Erik
I like this guy's teaching style.
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.
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).
Great lecture. Doesn't BFS on a graph with |V| vertices and no edges take O(1)?
We still need |V| time for initialization. Watch lecture 9 for explanation
ua-cam.com/video/oFVYVzlvk9c/v-deo.htmlsi=uJI_9TsWikCnkCl9 (50:10)
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 .
The runtime of both BFS and DFS algorithms is O ( |V| ) + O ( |E| )
@@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.
@@carlosmateosamudiolezcano2463 exactly,why did the proffesor told it is O(|E|) time about the depth first search
@@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.
@@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)
fire guys really cool thanks!
damnnn why aint nobody show up for this lecture 😭😭
COVID began or was beginning this week (I assume mid March 2020)
Can you put a trigger warning for ASMR?
Without power point was better
90% of the students decided to skip class
This was first lecture post COVID in March 2020
Why do there seem to be fewer students, I think this guy is excellent
My only guess is COVID. He's great.
Justin Solomon is the most interesting professor in this course, the other two are boring.