2020-06-08 00:52:17
Graph Theory Algorithms
29,397 students enrolled
Graph Theory Algorithms
A complete overview of graph theory algorithms in computer science and mathematics.
Bestseller
29,401 students enrolled
Current price: $139.99
Original price: $199.99
Discount:
30% off
5 hours left at this price!
30-Day Money-Back Guarantee
This course includes
- 9 hours on-demand video
- Full lifetime access
- Access on mobile and TV
- Certificate of Completion
Training 5 or more people?
Get your team access to 4,000+ top Udemy courses anytime, anywhere.
Try Udemy for Business
What you'll learn
- Storage and representation of graphs (networks) on a computer
- Common graph theory problems
- Breadth first search algorithm
- Depth first search algorithm
- Various tree algorithms including: the height or a tree, finding the center of a tree, rooting a tree, and etc...
- Dijkstra's algorithm
- Topological sort algorithm
- Shortest/longest path on a acyclic graph
- Bellman Ford's algorithm
- Floyd-Warshall all pairs shortest path algorithm
- Finding bridges/articulation points
- Finding strongly connected components (Tarjan's)
- Travelling salesman problem (TSP)
- How to find the maximum flow of a flow graph
- Finding bipartite graph matchings
- Various network flow algorithms including: Edmonds-Karp, Capacity Scaling, and Dinic's algorithm
- Kruskal's Minimum Spanning Tree algorithm
- The Lowest Common Ancestor (LCA) Problem
Requirements
- Exposure to computer science fundamentals (e.g: data structures, recursion, classes, OOP)
Description
This course provides a complete introduction to Graph Theory algorithms in computer science.
Topics covered in these videos include: how to store and represent graphs on a computer; common graph theory problems seen in the wild; famous graph traversal algorithms (DFS & BFS); Dijkstra's shortest path algorithm (both the lazy and eager version); what a topological sort is, how to find one, and places it's used; learning about detecting negative cycles and finding shortest paths with the Bellman-Ford and Floyd-Warshall algorithms; discovering bridges and articulation points in graphs; understanding and detecting strongly connected components with Tarjan's algorithm, and finally solving the traveling salesman problem with dynamic programming.
Who this course is for:
- Anybody ready for a deep dive into graph theory!
Featured review
Md Irshad
(
168 courses,
9 reviews
)
6 months ago
I took this course to learn about Graph theory. But i have a feeling now that i can master this. Everything explained here in so intuitive way that those who hate it will fall in love with Graph theory.
Course content
Expand all
46 lectures
09:02:45
+
–
Graph theory introduction and basics
5 lectures
59:37
Depth First Search algorithm
10:39
Breadth First Search algorithm
07:45
Breadth First Search grid shortest path
16:50
+
–
Graph theory and trees
6 lectures
50:36
An introduction to tree algorithms. This video covers how trees are stored and represented on a computer.
Preview
09:56
Rooting a tree
04:57
Finding tree center(s)
05:46
Identifying Isomorphic Trees
10:52
Identifying Isomorphic Trees Source Code
09:34
+
–
Classic graph theory algorithms
16 lectures
03:41:00
Topological sort algorithm
14:04
Shortest/longest path on a Directed Acyclic Graph (DAG)
10:14
Dijkstra's shortest path algorithm
24:31
Dijkstra's shortest path algorithm | source code
09:11
Bellman-Ford algorithm
15:16
Floyd-Warshall all pairs shortest path algorithm
15:55
Floyd-Warshall all pairs shortest path algorithm | source code
09:28
Bridges & Articulation points
20:16
Bridges & Articulation points | source code
09:22
Tarjan's strongly connected components algorithm (UPDATED)
17:41
Tarjan's strongly connected components algorithm | source code
07:11
Travelling Salesman problem
20:48
Travelling Salesman problem | source code
13:32
Existence of Eulerian path and circuits
09:40
Eulerian path algorithm
15:34
Eulerian path source code
08:17
+
–
Network flow
11 lectures
01:54:01
Max Flow Ford Fulkerson | Network Flow
13:05
Max Flow Ford Fulkerson | source code
17:28
Unweighted bipartite matching | Network flow
11:21
Bipartite Matching | The mice and owls problem | Network Flow
08:27
Bipartite Matching | The elementary math problem | Network Flow
10:44
Edmonds Karp | Network Flow
09:31
Edmonds Karp | Network Flow | Source Code
05:47
Capacity Scaling | Network Flow
10:10
Capacity Scaling | Network Flow | Source Code
06:23
Dinic's Algorithm | Network Flow
11:39
Dinic's Algorithm | Network Flow | Source Code
09:26
+
–
Bonus topics
8 lectures
01:37:31
Union Find data structure
05:45
Kruskal's Minimum Spanning Tree Algorithm
06:14
Prim's Minimum Spanning Tree (lazy version)
14:43
Prim's Minimum Spanning Tree (eager version)
14:33
Prim's Minimum Spanning Tree source code
09:08
23:17
Sparse Table Source Code
07:15
Lowest Common Ancestor (LCA) problem
16:36
Bonus topics quiz #1
6 questions