Graph Representation

Graph Representation Using Adjacency List

Problem Statement

Given a list of edges and number of nodes n. Create an adjacency list to represent the Graph.

Example

Input:
edges = [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 5], [3, 4], [3, 5]]
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

Video Explanation

Java Code

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

class AdjacencyList {

    public List<List<Integer>> buildGraph(int[][] edges, int n) {
        List<List<Integer>> graph = new ArrayList<>();
        
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for(int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        return graph;

    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 4}, {3, 5}};
        int n = 6;
        
        AdjacencyList adjacencyList = new AdjacencyList();
        
        List<List<Integer>> graph = adjacencyList.buildGraph(edges, n);
        for(int i = 0; i < n; i++) {
            System.out.print(i + " : ");
            for(int nbr : graph.get(i)) {
                System.out.print(nbr + " ");
            }
            System.out.println();
        }
    }
}

C++ Code

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

class AdjacencyList {
public:
    vector<vector<int>> buildGraph(vector<vector<int>> &edges, int n) {
        vector<vector<int>> graph;
        
        for(int i = 0; i < n; i++) {
            vector<int> nbrs;
            graph.push_back(nbrs);
        }

        for(auto &edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        return graph;
    }   
};

int main(int argc, char const *argv[]) {
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 4}, {3, 5}};
    int n = 6;

    AdjacencyList adjacencyList;
    
    vector<vector<int>> graph = adjacencyList.buildGraph(edges, n);
    for(int i = 0; i < n; i++) {
        cout << i << " : ";
        for(auto &nbr : graph[i]) {
            cout << nbr << " ";
        }
        cout << endl;
    }
}

Python Code

class AdjacencyList:

    def build_graph(self, edges, n):
        graph = []

        for i in range(n):
            graph.append(list())

        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])

        return graph

if __name__ == '__main__':
    edges = [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 5], [3, 4], [3, 5]]
    n = 6

    adjacencyList = AdjacencyList()
    
    graph = adjacencyList.build_graph(edges, n)
    for i in range(n):
        print(i, end = " : ")
        for nbr in graph[i]:
            print(nbr, end = " ")
        print()

Javascript Code

class AdjacencyList {
    buildGraph(edges, n) {
        const graph = new Array(n).fill(null).map(() => []);
        
        for (const edge of edges) {
            graph[edge[0]].push(edge[1]);
            graph[edge[1]].push(edge[0]);
        }

        return graph;
    }
}

const edges = [[0, 1], [0, 2], [1, 2], [1, 3], [1, 4], [2, 5], [3, 4], [3, 5]];
const n = 6;

const adjacencyList = new AdjacencyList();
const graph = adjacencyList.buildGraph(edges, n);

for (let i = 0; i < n; i++) {
    console.log(`${i} : ${graph[i].join(' ')}`);
}

Go Code

package main

import "fmt"

type AdjacencyList struct{}

func (al *AdjacencyList) buildGraph(edges [][]int, n int) [][]int {
	graph := make([][]int, n)

	for i := 0; i < n; i++ {
		graph[i] = make([]int, 0)
	}

	for _, edge := range edges {
		graph[edge[0]] = append(graph[edge[0]], edge[1])
		graph[edge[1]] = append(graph[edge[1]], edge[0])
	}

	return graph
}

func main() {
	edges := [][]int{{0, 1}, {0, 2}, {1, 2}, {1, 3}, {1, 4}, {2, 5}, {3, 4}, {3, 5}}
	n := 6

	var adjacencyList AdjacencyList
	graph := adjacencyList.buildGraph(edges, n)

	for i := 0; i < n; i++ {
		fmt.Printf("%d : %v\n", i, graph[i])
	}
}

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 + E), where V is the number of vertex and E is the number of edges. In the worst-case scenario, each node can be connected to every other node. Therefore, the total number of edges would be V² and hence in such a case, we can say that the Time Complexity would be O(V²).

Space Complexity

O(V + E), where V is the number of vertex and E is the number of edges. This space is contributed by Adjacency List.

Introduction to Graph