9. Breadth-First Search

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

This class covers graph definitions, neighbor sets and adjacencies, graph representations in data structures, and paths. It also discusses shortest paths trees and breadth-first search.

License: Creative Commons BY-NC-SA

[ParthPatel-vjzv]

0:00 intro
1:58 graph terminology
5:13 applications of graph
9:20 simple graph
11:36 important property of a simple graph
15:37 neighbors, degree of a node
20:58 representation of a graph
26:33 path in a graph
29:36 model graph problems
32:31 shortest path tree
41:38 computing shortest path in a graph (BFS using level set)

[Jimming]

Teaching myself discrete math out of an old textbook and it's crazy how applicable everything is already while watching this. Thanks again MIT for the great content!

[KatlegoMasego]

Great lecture. I appreciate MIT for rolling out so many informative videos for the last 2 hours. I'd rather binge-watch them than content on Netflix. Thank you.

[TimothyRourke]

Phenomenal lecture, demonstrates BFS by gradually building up from simpler ideas

[parkerh]

i like how excited he got at the chalk forking... I wish my graduate teacher would have any of this optimism

[mytech]

Lecture skill is improved over that first lecture on sets and sorts, must be getting settled in or just more comfortable with this material.

[tanvirwaseer]

Everything makes sense except the last part form here 45:20

[able]

pretty sure it's Erik on 27:14 in blue T-shirt

[ashishjain]

Good lecture. More mathematical than most lectures on BFS.

[kobbyfynn]

I wouldn’t say an edge list is the dumbest way to store a graph. It proves to useful in an algorithm like kruskals algo for finding minimum spanning tree

[enisten]

Well, that was a pedagogically genius approach to teaching BFS. 👍

[AniRec-eu]

0:31 that time i got reincarnated as a theoretical computer scientist and I maxed out my knowledge and became mit professor.

[mstep]

I already know BFS and the end of this lecture is still confusing to me. Did he run out of time?

[antutucat]

Am I stupid or this teacher makes it so hard

[AmarjeetKumar-engk]

Title is misleading, only basic stuff

[SumoCumLoudly]

Terrible lecturer, put me right off watching in first few mins