Graph Representation

Graph Representation Using Adjacency Matrix

Problem Statement

Given a 2D matrix grid and number of nodes n. Print an adjacency list from the given grid to represent the Graph.

Example

Input:
grid = [[0, 1, 1, 0, 0, 0],
        [1, 0, 1, 1, 1, 0],
        [1, 1, 0, 0, 0, 1],
        [0, 1, 0, 0, 1, 1],
        [0, 1, 0, 1, 0, 0],
        [0, 0, 1, 1, 0, 0]]
n = 6
Output:
0 : 1 2 
1 : 0 2 3 4 
2 : 0 1 5 
3 : 1 4 5 
4 : 1 3 
5 : 2 3

💡

Note: This is not any standard problem statement, it's just that we want to know how a matrix is represented as a Graph and how we can iterate on the neighbors of any matrix.

Video Explanation

Let's look at the code.

Java Code

class AdjacencyMatrix {

    public void printGraph(int[][] grid, int n) {
        for(int i = 0; i < n; i++) {
            System.out.print(i + " : ");
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    System.out.print(j + " ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{
            {0, 1, 1, 0, 0, 0},
            {1, 0, 1, 1, 1, 0},
            {1, 1, 0, 0, 0, 1},
            {0, 1, 0, 0, 1, 1},
            {0, 1, 0, 1, 0, 0},
            {0, 0, 1, 1, 0, 0}
        };
        int n = 6;
        
        AdjacencyMatrix adjacencyMatrix = new AdjacencyMatrix();
        adjacencyMatrix.printGraph(grid, n);
        
    }
}

C++ Code

#include <bits/stdc++.h>
using namespace std;

class AdjacencyMatrix {
public:
    void printGraph(vector<vector<int>> &grid, int n) {
        for(int i = 0; i < n; i++) {
            cout << i << " : ";
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    cout << j << " ";
                }
            }
            cout << endl;
        }
    }   
};

int main(int argc, char const *argv[]) {
    vector<vector<int>> grid = {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 1, 1, 1, 0},
        {1, 1, 0, 0, 0, 1},
        {0, 1, 0, 0, 1, 1},
        {0, 1, 0, 1, 0, 0},
        {0, 0, 1, 1, 0, 0}
    };
    int n = 6;

    AdjacencyMatrix adjacencyMatrix;
    adjacencyMatrix.printGraph(grid, n);
}

Python Code

class AdjacencyMatrix:

    def print_graph(self, grid, n):
        for i in range(n):
            print(i, end = " : ")
            for j in range(n):
                if grid[i][j] == 1:
                    print(j, end = " ")
            print()

if __name__ == '__main__':
    grid = [
        [0, 1, 1, 0, 0, 0],
        [1, 0, 1, 1, 1, 0],
        [1, 1, 0, 0, 0, 1],
        [0, 1, 0, 0, 1, 1],
        [0, 1, 0, 1, 0, 0],
        [0, 0, 1, 1, 0, 0]
    ]
    n = 6

    adjacencyMatrix = AdjacencyMatrix() 
    adjacencyMatrix.print_graph(grid, n)

Javascript Code

class AdjacencyMatrix {
    printGraph(matrix, n) {
        for (let i = 0; i < n; i++) {
            // this line prints the number and doesn't end with next line.
            // Keeps the cursor in the same line.
            process.stdout.write(`${i} : `);
            for (let j = 0; j < n; j++) {
                if (matrix[i][j] === 1) {
                    process.stdout.write(`${j} `);
                }
            }
            console.log();
        }
    }
}

const matrix = [
    [0, 1, 1, 0, 0, 0],
    [1, 0, 1, 1, 1, 0],
    [1, 1, 0, 0, 0, 1],
    [0, 1, 0, 0, 1, 1],
    [0, 1, 0, 1, 0, 0],
    [0, 0, 1, 1, 0, 0]
];
const n = 6;

const adjacencyMatrix = new AdjacencyMatrix();
adjacencyMatrix.printGraph(matrix, n);

Go Code

package main

import "fmt"

type AdjacencyMatrix struct{}

func (am *AdjacencyMatrix) printGraph(grid [][]int, n int) {
	for i := 0; i < n; i++ {
		fmt.Printf("%d : ", i)
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				fmt.Printf("%d ", j)
			}
		}
		fmt.Println()
	}
}

func main() {
	grid := [][]int{
		{0, 1, 1, 0, 0, 0},
		{1, 0, 1, 1, 1, 0},
		{1, 1, 0, 0, 0, 1},
		{0, 1, 0, 0, 1, 1},
		{0, 1, 0, 1, 0, 0},
		{0, 0, 1, 1, 0, 0},
	}
	n := 6

	var adjacencyMatrix AdjacencyMatrix
	adjacencyMatrix.printGraph(grid, n)
}

Output

0 : 1 2 
1 : 0 2 3 4 
2 : 0 1 5 
3 : 1 4 5 
4 : 1 3 
5 : 2 3

Time Complexity

O(V²), where V is the number of vertex. Because we are iterating the entire matrix of size V x V.

Space Complexity

O(1), because except for the input matrix, we are not utilizing any extra space to represent the graph.

Introduction to Graph