Graph Data Structure

A Graph consists of a finite set of nodes (or vertices) and a set of edges that connect a pair of nodes.

Types of Edges

Edges are classified in two ways,

• Directed edge
• Undirected edge

And,

• Weighted edge
• Unweighted edge

Types of Graphs

Edges are classified in two ways,

• Connected
• Disconnected

And,

• Cyclic
• Acyclic

All trees are graphs. But all graphs are not trees.

Degree

In the directed graph, the degree can be classified into two types.

• Indegree
• Outdegree

Code Implementation

• Adjacency Matrix
• Adjacency List

Adjacency Matrix

Adjacency Matrix is a 2D array of size N x N where N is the number of nodes in a graph.

• Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. The adjacency matrix for an undirected graph is always symmetric.
• Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.
• Time Complexity for lookup the edge connectivity — O(1).
• Space Complexity — O(N²).

Adjacency List

An array of lists is used. The size of the array is equal to the number of nodes.

• Let the array be an array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs.

Graph Traversal

• DFS — Depth First Search.
• BFS — Breadth First Search.

Thanks….

I Am…..

I am a Software Engineer having experience in mobile app development with expertise in Java, Android and Flutter. Interested people can contact me through LinkedIn and Instagram.