Everything about Graph Data Structure : An Overview

Photo by Guille Álvarez on Unsplash

Below is a Graph Data Structure

A graph consists on Vertices (also called as nodes) and Edges.

Claps and Follows are Welcome 😊 . Let’s Begin

Types of Graph

Undirected Graph

A graph which has unordered pair of vertices.

Connectivity in Undirected Graph

1. Connected Graph : An undirected graph where every vertex is reachable from every other vertex.
2. Bridge : It is an edge in a connected graph, which when removed will leave the graph dis-connected.
3. Articulation Point : A vertex in a connected graph which when removed along with its edges then graph will become dis-connected.
4. Biconnected Graph : Connected graph which does not have any articulation point is called Biconnected Graph.

Directed Graph

A graph which has ordered pair of vertices.

Connectivity in Directed Graph

1. Strongly Connected Graph: A Directed Graph in which we can go from any vertex to any other vertex.
2. Weekly Connected Graph: A directed graph in which if we remove the direction of edges then it will be a connected undirected graph.

Terminologies

1. Simple Path: A path in which all vertices are different.
2. Cycle: In a **directed graph**, a path is cycle if first and last vertex is same and number of vertices in that path is at least 2. In an un-directed graph, a path is cycle if first and last vertex is same and number of vertices is at least 3.
3. Simple Cycle: A cycle where except the first and last vertex all vertices are distinct.
4. Pendant Vertex : A vertex in a directed graph which has indegree = 1 and outdegree = 0
5. Maximum no of edges: In an undirected graph number of edges equals n(n-1)/2. In directed graph it equals n(n-1).
6. Isolated Vertex: A vertex with indegree = 0 and outdegree=0.
7. Complete Graph : A graph that has maximum possible number of edges.
8. Multigraph: A graph which has either loop or multiple edges is called a Multigraph.
9. Simple Graph : A graph that does not have any loop or multiple edges.
10. Regular Graph : A graph in which number of adjacent vertices is same for all vertex.

Transitive Closure of a Directed Graph

This is also called path matrix or reachability matrix.
It can be represented as
P(i, j) = 1 if there exist a path from i to j
P(i, j) = 0 if there exist no path from i to j

We can find transitive closure of a graph by two methods.

1. Using Matrix Multiplication
2. Using Warshall’s Algorithm

Do let me know if you need more info on this

Traversals

1. Breadth First Search : This is way of traversal in which the all adjacent vertices are visited before going to other ones.
2. Depth First Search : Here we go like parent -> child fashion till we reach end.

Shortest Path Problem

1. Dijkstra Algorithm : Single Source, Non Negative Weights
2. Bellman Ford Algorithm: Single Source, General Weight
3. Floyd or Modified Warshall’s Algorithm: All pair shortest path, should not contain negative cycle.

Minimum Spanning Tree

1. Prim’s Algorithm
2. Kruskal’s Algorithm

Thanks for reading. This is not an in-depth tutorial but an overview. If you want more articles on more depth, let me know I will write that.

Until Next Time

Saquib Aftab