0% completed

All LessonsFree Lessons (5)

Introduction

Introduction to Graph Algorithms Directed and Undirected Graphs Graph Terminology I Graph Terminology II Weighted Graphs Excursion: Algorithm Analysis Quiz: Introduction to Graph Algorithms

Graph Representations

Adjacency Matrix

Representing Weighted Graphs

Comparison of Graph Representations

Quiz: Graph Representations

Challenge: Converting Graph Representations

Graph Traversal

Depth-first Search (DFS)Implementation of DFS Breadth First Search (BFS)Implementation of BFS Application 1: Topological Sort Application 2: Strongly Connected Components Implementation of Kosaraju's Algorithm Quiz: Graph Traversal Challenge: Bipartite Graph Check

Shortest Paths

Shortest Path Problems Dijkstra's Algorithm for the SSSP Implementation of Dijkstra Floyd-Warshall Algorithm for the ASSP Implementation of Floyd-Warshall Quiz: Shortest Paths Challenge: Bellmann-Ford

Spanning Trees

The Minimum Spanning Tree Problem Kruskal's Algorithm Implementation of Kruskal's Algorithm Quiz: Spanning Trees Challenge: Maximum Spanning Trees

Flow Problems

The Max Flow Problem The Ford-Fulkerson Method Max Flow = Min Cut Implementation of Ford Fulkerson (Edmonds-Karp)Quiz: Flow Problems Challenge: Bipartite Matchings

Conclusion

Recap and Next Steps

Appendix

Disjoint Set Union Data Structure

Learn Graph Algorithms in C++/

...

/

Quiz: Graph Representations

Quiz: Graph Representations

Quiz yourself on graph representations.

We'll cover the following...

Comparing graph representations

1.

Which graph representation requires less memory for storing sparse graphs?

A.

The adjacency matrix.

B.

The adjacency list.

C.

A and B have the same memory footprint.

1 / 2