Skip to main content

Graph

Concept#

Graph is an extension of trees, where there is no root node, and is used to represent real world connections and scenarios, for example, connections on facebook or linkedin is a graph where you are a node and you are connected to other nodes in the graph. In order to get started with graph you must first know the basic terminology of graph and build a visual picture of what a graph looks like, the following articles will help you do so.

Graph Representation#

There are 2 ways to represent graphs, you will have to learn about them in detail, each having their own advantages and disadvantages. To know you must read on, be sure to learn the basics properly.

Depth First Search aka DFS#

Depth First Search or DFS is an algorithm for graph traversal, just like you have learnt about tree traversal previously, this time you will learn about graph traversals, which is a must know because they help in solving more difficult advance level graph problems. So what is DFS? What is the basic principle behind DFS? How is it implemented? What is the time complexity? What are the applications of DFS? All of these are important questions you should be able to answer once you have read about it from these good articles.

Q: Can you use implement DFS using stack?

Types of Edges in DFS#

While performing DFS, you can store the arrival and departure times of a node/vertex which can be used to identify the type of edge between two vertices, this perspective of DFS will be critical and useful to your problem solving analysis.

Breadth First Search aka BFS#

You have studied about DFS, now you are going to study about BFS which is another graph traversal algorithm. The questions that you have answered for DFS, the same questions must be answered for BFS, which are, what is BFS? What is the basic principle behind BFS? How is it implemented? What is the time complexity? What are the applications of BFS? So you better start reading.

Connected Components#

Bridges#

RESOURCES

Bridges Online#

Articulation Points#

Strongly Connected Component#

Union-Find#

The basic use case of an edge is to connect two vertices, but if you observe closely it is not just connecting two vertices but all other vertices connected to these two vertices are now connected to each other via this edge, as if a union has happened. Suppose given two vertices with no direct edge between them, you are asked to find if the two vertices are connected in O(1) time, one approach is to use DFS/BFS but it will give you O(n) time complexity, the solution lies in the concept of Union-Find which helps in solving a specific pattern of problems very easily, just like this one. So what is this union-find algorithm? What is the time complexity? How is it implemented? All of these questions you must be able to answer after reading these wonderful articles .

Dijkstra's Algorithm#

Dijkstra’s algorithm is used to find the shortest distance path from the source or starting vertex to all other vertices in the graph. Using dijkstra's uber knows the shortest distance between your pick up point and your drop off point. Now that you have a faint idea of what dijkstra's algorithm is there are few other questions left to answer. What is the basic principle behind dijkstra's algorithm? How is it implemented? What is the time complexity? All of these questions you must be able to answer after reading these wonderful articles. Make sure you are able to visualise this algorithm to understand completely how it functions.

Caution

Dijkstra’s algorithm does not work when the edge weights have negative values.

0-1 BFS#

It so happens that finding the single source shortest path using dijkstra’s algorithm can be an overkill if the edge weights contain one of the only two possible values. For this special scenario 0-1 BFS can be deployed to find the Single Source Shortest Path aka SSSP, which is easier to understand and code. So why does having this one special condition make it possible to use BFS? The answer you will find in this article but you must read on.

RESOURCES

QUESTION

Dijkstra's on Sparse Graph#

When it comes to graphs based on its representation adjacency matrix or adjacency list, the dijkstra’s algorithm has different time complexity, here you will learn about the time complexity and implementation of dijkstra's algorithm for sparse graph which is represented using adjacency list.

The Dijkstra’s algorithm can be implemented using either set or priority queue, with proper understanding of both the containers you can use the more appropriate container for your implementation. It is recommended you go through both the implementations.

Bellman Ford Algorithm#

Bellman Ford algorithm overcomes the shortcoming of dijkstra's algorithm, it enables you to find the single source shortest path when the graph has negative edge weights. So the question that arises, what is the basic principle behind Bellman Ford algorithm? How is it implemented? What is the time complexity? All of these questions you must be able to answer after reading these wonderful articles.

Floyd-Warshall Algorithm#

So far you have learned about algorithms that find the shortest path from a single source vertex to all other vertices, but what if you have to find the shortest path from every vertex to every other vertex, is there any algorithm better than dijkstra's? Fortunately there is, Floyd-Warshall algorithm is a dynamic programming based approach that will help you to find the all pair shortest path easily. You know that dynamic programming is behind this approach, but do you know how it is implemented or what is the time complexity? If you don’t you must read these wonderful articles to find out.

Spanning Tree#

Spanning Tree is a type of graph which is a tree, all the vertices will be connected and the number of edges will be one less than the number of vertices, building a spanning tree is usually a sub-problem to more difficult and challenging problems, but how do you build a spanning tree? Is there any other useful variation to a spanning tree? All these questions will be answered, you have to just read on, stay on track.

Kruskal's Algorithm#

Kruskal's Agorithm helps you create a minimum spanning tree from a graph, it follows a greedy approach to do so. So what is the principle behind Kruskal’s algorithm? How is it implemented? What is the time complexity? All these questions you must be able to answer after reading these wonderful articles. As a spoiler, Kruskal’s algorithm uses a greedy approach alongside union-find to find the minimum spanning tree.

Prim's Algorithm#

As an alternative to Kruskal’s algorithm to find the minimum spanning tree, you can use Prim’s algorithm which also follows a greedy approach. So what is different about Prim’s algorithm? How is it implemented? What is the time complexity? All these questions you must be able to answer after reading these wonderful articles.

Topological Sort#

For Directed Acyclic Graph aka DAG there is a special ordering of the vertices such that there is no backward edge. This ordering is a special condition that exists in many day to day scenarios, so it is very useful to learn about topological sort which will help you to find this ordering of vertices. But remember that a graph must be a DAG. So what is a topological sort? How is it implemented? What is the time complexity? All these questions you must be able to answer after reading these wonderful articles.

Questions#

Bipartite Graph#

QUESTION

Random#