Graph Representation

Graph Representation Using Adjacency List - String

Problem Statement

Given a list of edges which represents the connection between different cities. Create an adjacency list to represent the Graph.

💡

This time, you are not given numbers to represent the nodes. Instead, you're given strings to represent each node.

Example

Input:
edges = [
    ["DEL", "BOM"], 
    ["DEL", "KNP"], 
    ["DEL", "BLR"], 
    ["DEL", "HYD"], 
    ["DEL", "PNQ"],
    ["BLR", "HYD"],
    ["BLR", "PNQ"],
    ["BLR", "BOM"]
]
Output:
DEL : BOM KNP BLR HYD PNQ
BOM : DEL BLR
KNP : DEL
BLR : DEL HYD PNQ BOM
HYD : DEL BLR
PNQ : DEL BLR

Video Explanation

Java Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class AdjacencyListString {

    public Map<String, List<String>> buildGraph(String[][] edges) {
        Map<String, List<String>> graph = new HashMap<>();

        for(String[] edge : edges) {
            String src = edge[0];
            String dest = edge[1];
            
            if(!graph.containsKey(src)) {
                graph.put(src, new ArrayList<>());
            }
            graph.get(src).add(dest);

            if(!graph.containsKey(dest)) {
                graph.put(dest, new ArrayList<>());
            }
            graph.get(dest).add(src);
            
        }

        return graph;
    }

    public static void main(String[] args) {
        String[][] edges = new String[][]{
            {"DEL", "BOM"}, 
            {"DEL", "KNP"}, 
            {"DEL", "BLR"}, 
            {"DEL", "HYD"}, 
            {"DEL", "PNQ"},
            {"BLR", "HYD"},
            {"BLR", "PNQ"},
            {"BLR", "BOM"}
        };
        
        AdjacencyListString adjacencyList = new AdjacencyListString();
        
        Map<String, List<String>> graph = adjacencyList.buildGraph(edges);
        for(Map.Entry<String, List<String>> entry : graph.entrySet()) {
            System.out.print(entry.getKey() + " : ");
            for(String nbr : entry.getValue()) {
                System.out.print(nbr + " ");
            }
            System.out.println();
        }
    }
}

C++ Code

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

class AdjacencyListString {
public:
    map<string, vector<string>> buildGraph(vector<vector<string>> &edges) {
        map<string, vector<string>> graph;

        for(auto &edge : edges) {
            string src = edge[0];
            string dest = edge[1];

            graph[src].push_back(dest);
            graph[dest].push_back(src);
        }

        return graph;
    }   
};

int main(int argc, char const *argv[]) {
    vector<vector<string>> edges = {
        {"DEL", "BOM"}, 
        {"DEL", "KNP"}, 
        {"DEL", "BLR"}, 
        {"DEL", "HYD"}, 
        {"DEL", "PNQ"},
        {"BLR", "HYD"},
        {"BLR", "PNQ"},
        {"BLR", "BOM"}
    };

    AdjacencyListString adjacencyList;
    
    map<string, vector<string>> graph = adjacencyList.buildGraph(edges);
    for(auto &entry : graph) {
        cout << entry.first << " : ";
        for(auto &nbr : entry.second) {
            cout << nbr << " ";
        }
        cout << endl;
    }
}

Python Code

class AdjacencyListString:

    def build_graph(self, edges):
        graph = dict()

        for edge in edges:
            src = edge[0]
            dest = edge[1]
            
            if src not in graph:
                graph[src] = list()
            graph[src].append(dest)
            
            if dest not in graph:
                graph[dest] = list()
            graph[dest].append(src)

        return graph

if __name__ == '__main__':
    edges = [
        ["DEL", "BOM"], 
        ["DEL", "KNP"], 
        ["DEL", "BLR"], 
        ["DEL", "HYD"], 
        ["DEL", "PNQ"],
        ["BLR", "HYD"],
        ["BLR", "PNQ"],
        ["BLR", "BOM"]
    ]

    adjacencyList = AdjacencyListString()
    
    graph = adjacencyList.build_graph(edges)
    for (key, value) in graph.items():
        print(key, end = " : ")
        for nbr in value:
            print(nbr, end = " ")
        print()

Javascript Code

class AdjacencyListString {
    buildGraph(edges) {
        const graph = new Map();

        for (const edge of edges) {
            const [src, dest] = edge;

            if (!graph.has(src)) {
                graph.set(src, []);
            }
            graph.get(src).push(dest);

            if (!graph.has(dest)) {
                graph.set(dest, []);
            }
            graph.get(dest).push(src);
        }

        return graph;
    }
}

const edges = [
    ["DEL", "BOM"],
    ["DEL", "KNP"],
    ["DEL", "BLR"],
    ["DEL", "HYD"],
    ["DEL", "PNQ"],
    ["BLR", "HYD"],
    ["BLR", "PNQ"],
    ["BLR", "BOM"]
];

const adjacencyList = new AdjacencyListString();
const graph = adjacencyList.buildGraph(edges);

for (const [key, value] of graph.entries()) {
    console.log(`${key} : ${value.join(" ")}`);
}

Go Code

package main

import "fmt"

type AdjacencyListString struct{}

func (als *AdjacencyListString) buildGraph(edges [][]string) map[string][]string {
	graph := make(map[string][]string)

	for _, edge := range edges {
		src, dest := edge[0], edge[1]

		if _, ok := graph[src]; !ok {
			graph[src] = make([]string, 0)
		}
		graph[src] = append(graph[src], dest)

		if _, ok := graph[dest]; !ok {
			graph[dest] = make([]string, 0)
		}
		graph[dest] = append(graph[dest], src)
	}

	return graph
}

func main() {
	edges := [][]string{
		{"DEL", "BOM"},
		{"DEL", "KNP"},
		{"DEL", "BLR"},
		{"DEL", "HYD"},
		{"DEL", "PNQ"},
		{"BLR", "HYD"},
		{"BLR", "PNQ"},
		{"BLR", "BOM"},
	}

	var adjacencyList AdjacencyListString
	graph := adjacencyList.buildGraph(edges)

	for key, value := range graph {
		fmt.Printf("%s : %v\n", key, value)
	}
}

Output

DEL : BOM KNP BLR HYD PNQ
BOM : DEL BLR
KNP : DEL
BLR : DEL HYD PNQ BOM
HYD : DEL BLR
PNQ : DEL BLR

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) * K), where V is the number of vertex, E is the number of edges, and K is the average length of each string. This space is contributed by Adjacency List. You might ignore K because the length of each string will almost be constant like 10 to 20.

Introduction to Graph