Representation of Graph Data Structure

Basic Operations on Graph Data Structure:

There are two ways to store a graph:

Adjacency Matrix
Adjacency List

Adjacency Matrix Representation of Graph Data Structure:

In this method, the graph is stored in the form of the 2D matrix where rows and columns denote vertices. Each entry in the matrix represents the weight of the edge between those vertices.

Below is the implementation of Graph Data Structure represented using Adjacency Matrix:

C++

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> >
createAdjacencyMatrix(vector<vector<int> >& graph,
                      int numVertices)
{
    // Initialize the adjacency matrix with zeros
    vector<vector<int> > adjMatrix(
        numVertices, vector<int>(numVertices, 0));

    // Fill the adjacency matrix based on the edges in the
    // graph
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            if (graph[i][j] == 1) {
                adjMatrix[i][j] = 1;
                adjMatrix[j][i]
                    = 1; // For undirected graph, set
                         // symmetric entries
            }
        }
    }

    return adjMatrix;
}

int main()
{
    // The indices represent the vertices, and the values
    // are lists of neighboring vertices
    vector<vector<int> > graph = { { 0, 1, 0, 0 },
                                   { 1, 0, 1, 0 },
                                   { 0, 1, 0, 1 },
                                   { 0, 0, 1, 0 } };

    int numVertices = graph.size();

    // Create the adjacency matrix
    vector<vector<int> > adjMatrix
        = createAdjacencyMatrix(graph, numVertices);

    // Print the adjacency matrix
    for (int i = 0; i < numVertices; ++i) {
        for (int j = 0; j < numVertices; ++j) {
            cout << adjMatrix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

Java

import java.util.ArrayList;
import java.util.Arrays;

public class AdjacencyMatrix {
    public static int[][] createAdjacencyMatrix(
        ArrayList<ArrayList<Integer> > graph,
        int numVertices)
    {
        // Initialize the adjacency matrix with zeros
        int[][] adjMatrix
            = new int[numVertices][numVertices];

        // Fill the adjacency matrix based on the edges in
        // the graph
        for (int i = 0; i < numVertices; ++i) {
            for (int j = 0; j < numVertices; ++j) {
                if (graph.get(i).get(j) == 1) {
                    adjMatrix[i][j] = 1;
                    adjMatrix[j][i]
                        = 1; // For undirected graph, set
                             // symmetric entries
                }
            }
        }

        return adjMatrix;
    }

    public static void main(String[] args)
    {
        // The indices represent the vertices, and the
        // values are lists of neighboring vertices
        ArrayList<ArrayList<Integer> > graph
            = new ArrayList<>();
        graph.add(
            new ArrayList<>(Arrays.asList(0, 1, 0, 0)));
        graph.add(
            new ArrayList<>(Arrays.asList(1, 0, 1, 0)));
        graph.add(
            new ArrayList<>(Arrays.asList(0, 1, 0, 1)));
        graph.add(
            new ArrayList<>(Arrays.asList(0, 0, 1, 0)));

        int numVertices = graph.size();

        // Create the adjacency matrix
        int[][] adjMatrix
            = createAdjacencyMatrix(graph, numVertices);

        // Print the adjacency matrix
        for (int i = 0; i < numVertices; ++i) {
            for (int j = 0; j < numVertices; ++j) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

// This code is contributed by shivamgupta310570

Python

def create_adjacency_matrix(graph):
    # Get the number of vertices in the graph
    num_vertices = len(graph)

    # Initialize the adjacency matrix with zeros
    adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

    # Fill the adjacency matrix based on the edges in the graph
    for i in range(num_vertices):
        for j in range(num_vertices):
            if graph[i][j] == 1:
                adj_matrix[i][j] = 1
                # For undirected graph, set symmetric entries
                adj_matrix[j][i] = 1

    return adj_matrix


# The indices represent the vertices, and the values are lists of neighboring vertices
graph = [
    [0, 1, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [0, 0, 1, 0]
]

# Create the adjacency matrix
adj_matrix = create_adjacency_matrix(graph)

# Print the adjacency matrix
for row in adj_matrix:
    print(' '.join(map(str, row)))

# This code is contributed by shivamgupta0987654321

JavaScript

function createAdjacencyMatrix(graph) {
    const numVertices = graph.length;

    // Initialize the adjacency matrix with zeros
    const adjMatrix = Array.from(Array(numVertices), () => Array(numVertices).fill(0));

    // Fill the adjacency matrix based on the edges in the graph
    for (let i = 0; i < numVertices; ++i) {
        for (let j = 0; j < numVertices; ++j) {
            if (graph[i][j] === 1) {
                adjMatrix[i][j] = 1;
                adjMatrix[j][i] = 1; // For undirected graph, set symmetric entries
            }
        }
    }

    return adjMatrix;
}

// The indices represent the vertices, and the values are lists of neighboring vertices
const graph = [
    [0, 1, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [0, 0, 1, 0]
];

// Create the adjacency matrix
const adjMatrix = createAdjacencyMatrix(graph);

// Print the adjacency matrix
for (let i = 0; i < adjMatrix.length; ++i) {
    console.log(adjMatrix[i].join(' '));
}

Adjacency List Representation of Graph:

This graph is represented as a collection of linked lists. There is an array of pointer which points to the edges connected to that vertex.

Below is the implementation of Graph Data Structure represented using Adjacency List:

C++

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> createAdjacencyList(vector<vector<int> >& edges, int numVertices)
{
    // Initialize the adjacency list 
    vector<vector<int> > adjList(numVertices);

    // Fill the adjacency list based on the edges in the
    // graph
    for (int i=0; i < edges.size(); i++) {
        int u = edges[i][0];
          int v = edges[i][1];
          // Since the graph is undirected, therefore we push the edges in both the directions
          adjList[u].push_back(v);
          adjList[v].push_back(u);
    }

    return adjList;
}

int main()
{
      // Undirected Graph of 4 nodes
      int numVertices = 4;
      vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}, {3, 1}};
  
    // Create the adjacency List
    vector<vector<int>> adjList = createAdjacencyList(edges, numVertices);

    // Print the adjacency List
    for (int i = 0; i < numVertices; ++i) {
          cout << i << " -> ";
        for (int j = 0; j < adjList[i].size(); ++j) {
            cout << adjList[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static List<List<Integer> >
    createAdjacencyList(List<List<Integer> > edges,
                        int numVertices)
    {
        // Initialize the adjacency list
        List<List<Integer> > adjList
            = new ArrayList<>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjList.add(new ArrayList<>());
        }

        // Fill the adjacency list based on the edges in the
        // graph
        for (List<Integer> edge : edges) {
            int u = edge.get(0);
            int v = edge.get(1);
            // Since the graph is undirected, therefore we
            // push the edges in both the directions
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }

        return adjList;
    }

    public static void main(String[] args)
    {
        // Undirected Graph of 4 nodes
        int numVertices = 4;
        List<List<Integer> > edges = new ArrayList<>();
        edges.add(List.of(0, 1));
        edges.add(List.of(0, 2));
        edges.add(List.of(1, 2));
        edges.add(List.of(2, 3));
        edges.add(List.of(3, 1));

        // Create the adjacency list
        List<List<Integer> > adjList
            = createAdjacencyList(edges, numVertices);

        // Print the adjacency list
        for (int i = 0; i < numVertices; ++i) {
            System.out.print(i + " -> ");
            for (int j = 0; j < adjList.get(i).size();
                 ++j) {
                System.out.print(adjList.get(i).get(j)
                                 + " ");
            }
            System.out.println();
        }
    }
}

Python

def create_adjacency_list(edges, num_vertices):
    # Initialize the adjacency list
    adj_list = [[] for _ in range(num_vertices)]

    # Fill the adjacency list based on the edges in the graph
    for u, v in edges:
        # Since the graph is undirected, push the edges in both directions
        adj_list[u].append(v)
        adj_list[v].append(u)

    return adj_list

if __name__ == "__main__":
    # Undirected Graph of 4 nodes
    num_vertices = 4
    edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 1)]

    # Create the adjacency list
    adj_list = create_adjacency_list(edges, num_vertices)

    # Print the adjacency list
    for i in range(num_vertices):
        print(f"{i} -> {' '.join(map(str, adj_list[i]))}")

using System;
using System.Collections.Generic;

class MainClass {
    public static List<List<int> >
    CreateAdjacencyList(List<List<int> > edges,
                        int numVertices)
    {
        // Initialize the adjacency list
        List<List<int> > adjList
            = new List<List<int> >(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjList.Add(new List<int>());
        }

        // Fill the adjacency list based on the edges in the
        // graph
        foreach(List<int> edge in edges)
        {
            int u = edge[0];
            int v = edge[1];
            // Since the graph is undirected, push the edges
            // in both directions
            adjList[u].Add(v);
            adjList[v].Add(u);
        }

        return adjList;
    }

    public static void Main(string[] args)
    {
        // Undirected Graph of 4 nodes
        int numVertices = 4;
        List<List<int> > edges = new List<List<int> >{
            new List<int>{ 0, 1 }, new List<int>{ 0, 2 },
            new List<int>{ 1, 2 }, new List<int>{ 2, 3 },
            new List<int>{ 3, 1 }
        };

        // Create the adjacency list
        List<List<int> > adjList
            = CreateAdjacencyList(edges, numVertices);

        // Print the adjacency list
        for (int i = 0; i < numVertices; i++) {
            Console.Write($"{i} -> ");
            foreach(int vertex in adjList[i])
            {
                Console.Write($"{vertex} ");
            }
            Console.WriteLine();
        }
    }
}

JavaScript

function createAdjacencyList(edges, numVertices) {
    // Initialize the adjacency list
    const adjList = new Array(numVertices).fill(null).map(() => []);

    // Fill the adjacency list based on the edges in the graph
    edges.forEach(([u, v]) => {
        // Since the graph is undirected, push the edges in both directions
        adjList[u].push(v);
        adjList[v].push(u);
    });

    return adjList;
}

// Undirected Graph of 4 nodes
const numVertices = 4;
const edges = [[0, 1], [0, 2], [1, 2], [2, 3], [3, 1]];

// Create the adjacency list
const adjList = createAdjacencyList(edges, numVertices);

// Print the adjacency list
for (let i = 0; i < numVertices; i++) {
    console.log(`${i} -> ${adjList[i].join(' ')}`);
}

Output

Comparison between Adjacency Matrix and Adjacency List

When the graph contains a large number of edges then it is good to store it as a matrix because only some entries in the matrix will be empty. An algorithm such as Prim’s and Dijkstra adjacency matrix is used to have less complexity.

Action	Adjacency Matrix	Adjacency List
Adding Edge	O(1)	O(1)
Removing an edge	O(1)	O(N)
Initializing	O(N*N)	O(N)

Introduction to Graph Data Structure

Graph Data Structure is a non-linear data structure consisting of vertices and edges. It is useful in fields such as social network analysis, recommendation systems, and computer networks. In the field of sports data science, graph data structure can be used to analyze and understand the dynamics of team performance and player interactions on the field.

Table of Content

What is Graph Data Structure?
Components of Graph Data Structure
Types Of Graph Data Structure
Representation of Graph Data Structure

Adjacency Matrix Representation of Graph Data Structure
Adjacency List Representation of Graph

Basic Operations on Graph Data Structure
Difference between Tree and Graph
Real-Life Applications of Graph Data Structure
Advantages of Graph Data Structure
Disadvantages of Graph Data Structure
Frequently Asked Questions(FAQs) on Graph Data Structure

Representation of Graph Data Structure

Adjacency Matrix Representation of Graph Data Structure:

Adjacency List Representation of Graph:

Comparison between Adjacency Matrix and Adjacency List

Introduction to Graph Data Structure

Similar Reads

Contact Us