Byte-Sized-Chunks: Graph Algorithms and Problems in Java

Name: Byte-Sized-Chunks: Graph Algorithms and Problems in Java
Rating: 4.5 (63 reviews)

Djisktra, Prim, Kruskal, Bellman-Ford, the topological sort - all will make sense now!

Created byLoony Corn

Last updated 3/2016

English

What you'll learn

Design and implement software using canonical graph algorithms - Djikstra, Prim, Kruskal, Bellman Ford and topological sort
Understand the use-cases for the common graph algorithm

Course content

5 sections • 28 lectures • 5h 13m total length

You, This Course, and Us!1:14
Introducing The Graph15:40
The graph is a data structure that is used to model a very large number of real world problems. It's also an programming interview favorite. The study of graphs and algorithms associated with graphs forms an entire field of study called graph theory.
Types Of Graphs7:21
Edges in a graph can be directed or undirected. A graph with directed edges forms a Directed Graph and those with undirected edges forms an Undirected Graph. These edges can be likened to one-way and two-way streets.
The Directed And Undirected Graph14:29
Different relationships can be modeled using either Directed or Undirected graphs. When a graph has no cycles it's called an acyclic graph. A graph with no cycles is basically a tree.
Representing A Graph In Code8:09
There are a number of different ways in which graphs can be implemented. However they all follow they same basic graph interface. The graph interface allows building up a graph by adding edges and traversing a graph by giving access to all adjacent vertices of any vertex.
Graph Using An Adjacency Matrix15:25
An adjacency matrix is one way in which a graph can be represented. The graph vertices are rows and columns of the matrix and the cell value shows the relationship between the vertices of a graph.
Graph Using An Adjacency List And Adjacency Set17:53
The adjacency list and the adjacency set are alternate ways to represent a graph. Here the connection between the vertices is represented using either a linked list or a set.
Comparison Of Graph Representations10:08
Compare the adjacency matrix, adjacency list and the adjacency set in terms of space and time complexity of common operations
Graph Traversal - Depth First And Breadth First14:56
Common traversal methods of trees apply to graphs as well. There is an additional wrinkle with graphs, dealing with cycles and with unconnected graphs. Otherwise the algorithms are exactly the same as those we use to traverse trees.

Introduction To Shortest Path In An Unweighted Graph - The Distance Table12:38
Graphs with simple edges (directed or undirected) are unweighted graphs. The distance table is an important data structure used to find the shortest path between any two vertices on a graph. This is used in almost every shortest path algorithm.
The Shortest Path Algorithm Visualized14:15
Visualize the shortest path algorithm using the distance table, step by step.
Implementation Of The Shortest Path In An Unweighted Graph6:19
Shortest path implementation in Java.
Introduction To The Weighted Graph3:29
So far we only deal with unweighted graphs. Graphs whose edges have a weight associated are widely used to model real world problems (traffic, length of path etc).
Shortest Path In A Weighted Graph - A Greedy Algorithm18:47
A greedy algorithm is one which tries to find the local optimum by looking at what is the next best step at every iteration. It does not look at the overall picture. It's best used for optimization problems where the solution is very hard and we want an approximate answer.

Finding the shortest path in a weighted graph is a greedy algorithm.
Dijkstra's Algorithm Visualized14:14
Dijkstra's algorithm is a greedy algorithm to find the shortest path in a weighted graph.
Implementation Of Dijkstra's Algorithm8:15
The implementation of Dijkstra's algorithm in Java.
Introduction To The Bellman Ford Algorithm8:40
A weighted graph can have edge weights which are negative. Dealing with negative weights have some quirks which are dealt with using the Bellman Ford algorithm.
The Bellman Ford Algorithm Visualized11:22
Visualize how the Bellman Ford works to find the shortest path in a graph with negative weighted edges.
Dealing With Negative Cycles In The Bellman Ford Algorithm7:36
If a graph has a negative cycle then it's impossible to find a shortest path as every round of the cycle makes the path shorter!
Implementation Of The Bellman Ford Algorithm6:54

Prim's Algorithm For a Minimal Spanning Tree17:27
A minimal spanning tree is a tree which covers all the vertices of of the graph and has the lowest cost. Prim's algorithm is very similar to Dijkstra's shortest path algorithm with a few differences.
Use Cases And Implementation Of Prim's Algorithm9:52
The minimal spanning tree is used when we want to connect all vertices at the lowest cost, it's not the shortest path from source to destination.

Let's see how we implement Prim's algorithm in Java.
Kruskal's Algorithm For a Minimal Spanning Tree8:43
Kruskal's algorithm is another greedy algorithm to find a minimal spanning tree.
Implementation Of Kruskal's Algorithm7:34

Requirements

Basic knowledge of programming is assumed, preferably in Java

Description

Note: This course is a subset of our much longer course 'From 0 to 1: Data Structures & Algorithms' so please don't sign up for both:-)

This is an animated, visual and spatial way to learn data structures and algorithms

Our brains process different types of information differently - evolutionarily we are wired to absorb information best when it is visual and spatial i.e. when we can close our eyes and see it
More than most other concepts, Data Structures and Algorithms are best learnt visually. These are incredibly easy to learn visually, very hard to understand most other ways
This course has been put together by a team with tons of everyday experience in thinking about these concepts and using them at work at Google, Microsoft and Flipkart

Taught by a Stanford-educated ex-Googler.

The graph is a data structure that is used to model a very large number of real world problems. It's also an programming interview favorite. The study of graphs and algorithms associated with graphs forms an entire field of study called graph theory.

Directed and undirected graphs
Adjacency matrices, lists and sets
Breadth and Depth-First traversal
Topological sort
Djikstra's algorithm
Bellman-Ford algorithm
Prim's algorithm
Kruskal's algorithm

Who this course is for:

Nope! Please don't enroll for this class if you have already enrolled for our 15-hour course 'From 0 to 1: Data Structures and Algorithms'
Yep! Computer Science and Engineering grads who are looking to really visualise data structures, and internalise how they work
Yep! Experienced software engineers who are looking to refresh important fundamental concepts
Yep! MBA graduates or business professionals who are looking to move to a heavily quantitative role

Byte-Sized-Chunks: Graph Algorithms and Problems in Java

What you'll learn

Explore related topics

Course content

Its A Connected World!9 lectures • 1hr 45min

Graph Algorithms2 lectures • 24min

Shortest Path Algorithms11 lectures • 1hr 52min

Spanning Tree Algorithms4 lectures • 44min

Graph Problems2 lectures • 28min

Requirements

Description

Who this course is for: