Graph Data Structure

Welcome to this in-depth guide on the concept of graphs in computer science. Whether you're a complete novice or an advanced learner looking to refine your understanding, this tutorial will guide you through the core concepts, representations, and practical applications of graphs, ensuring a robust understanding of this fundamental concept.

Introduction to Graphs

A graph is a data structure that consists of a set of nodes (also called vertices) and a set of edges that connect these nodes. Graphs are used to represent pairwise relationships between objects. In a graph, nodes can represent any type of entities such as people, cities, web pages, or even abstract concepts, while edges represent the relationships or connections between these entities.

Graphs are used to model a wide variety of real-world situations, from social networks (like Facebook, LinkedIn) to computer networks (like the internet), from biological systems (like protein-protein interaction networks) to transportation networks (like air traffic).

Components of a Graph

Graphs are primarily defined by two components:

  • Vertices (Nodes): The entities in a graph. Each vertex can represent an object or a piece of data.
  • Edges (Links): The connections between the vertices. An edge can represent a relationship or a pathway between two vertices.

Let's visualize this with a simple graph:

Graph G:

    A - B - D
    |   |   |
    C   E - F

Vertices: A, B, C, D, E, F
Edges: AB, AC, BD, BE, DF

Types of Graphs

Graphs can be classified into various types based on their properties:

  • Undirected Graphs: A graph where edges have no direction. The edges indicate a two-way relationship, in that each edge can be traversed in both directions.
  • Directed Graphs (Digraphs): A graph where edges have directions. Here, if an edge is directed from node A to node B, you can only travel from A to B and not from B to A.
  • Weighted Graphs: A graph where edges have weights associated with them. These weights can represent distances, costs, or any measurable attribute corresponding to the edge.
  • Unweighted Graphs: A graph where edges do not have weights. They only represent a connection between vertices.

Graph Representations

Graphs can be represented in computer memory in the following ways:

  • Adjacency Matrix: A 2D array where each cell [i][j] represents the presence or absence of an edge between the ith and jth vertex. Suitable for dense graphs.
  • Adjacency List: An array of lists. The size of the array is equal to the number of vertices. An entry array[i] represents the list of vertices adjacent to the ith vertex. Suitable for sparse graphs.
Graph Representations by Example

Graph:


       A
      / \
     B - C
    / \   \
   D - E - F

1. Adjacency Matrix Representation

In an adjacency matrix, each cell [i][j] in a 2D array represents the presence (1) or absence (0) of an edge between the ith and jth vertex. For our graph:

  • Vertices: A, B, C, D, E, F (indexed as A=0, B=1, C=2, D=3, E=4, F=5)
  • Matrix Size: 6x6 (since we have 6 vertices)
    A B C D E F
  A 0 1 1 0 0 0
  B 1 0 0 1 1 0
  C 1 0 0 0 0 1
  D 0 1 0 0 1 0
  E 0 1 0 1 0 1
  F 0 0 1 0 1 0

2. Adjacency List Representation

An adjacency list uses a dictionary where each vertex is a key, and the corresponding value is a list of edges (source, destination) adjacent to the key vertex. For our graph:

A: [(A, B), (A, C)]
B: [(B, A), (B, D), (B, E)]
C: [(C, A), (C, F)]
D: [(D, B), (D, E)]
E: [(E, B), (E, D), (E, F)]
F: [(F, C), (F, E)]

3. Adjacency List Representation (if graph has some weight)


	       A
	      / \
	    1/	 \2
	    /  2  \
	   B ----- C
	  / \       \
	3/  2\      4\
        /     \       \
       D ----- E ----- F
          2       3

In an adjacency list representation with weights, we use a dictionary where each vertex is a key, and the corresponding value is a list of weighted edges (source, destination, weight) adjacent to the key vertex. For our graph:

A: [(A, B, 1), (A, C, 2)]
B: [(B, A, 1), (B, D, 3), (B, E, 2),(B, C, 2)]
C: [(C, A, 2), (C, F, 4),(C, B, 2)]
D: [(D, B, 3), (D, E, 2)]
E: [(E, B, 2), (E, D, 2), (E, F, 3)]
F: [(F, C, 4), (F, E, 3)]

Comparison

  • Adjacency Matrix:
    • Pros: Directly shows if a connection exists between two vertices.
    • Cons: Consumes more space, particularly in sparse graphs. Slower to check connections.
  • Adjacency List:
    • Pros: More efficient space usage for sparse graphs. Faster traversal of edges.
    • Cons: Less direct when checking for a specific edge.

These representations highlight how different graph structures can be more or less efficient depending on the graph's characteristics and the operations performed on it.

Implementing Graphs in Code

Implementation of a graph structure can vary based on its intended use case and the chosen programming language. Here, we present implementations in Java, C++, Python, and JavaScript for a basic graph structure using adjacency lists.


       A
      / \
     B - C
    / \   \
   D - E - F


import java.util.*;

class Node {
    char id;

    public Node(char id) {
        this.id = id;
    }
}

class Edge {
    Node source;
    Node destination;
    
    /* 
    * we can use here int weight; if we work for weighted graph
    * so in case if weighted graph we have three fields:
    * 1.source, 2.destination and 3.weight.
    * but, we are currently going with only two 
    * fields source and destination.
    */

    public Edge(Node source, Node destination) {
        this.source = source;
        this.destination = destination;
    }
}

public class Graph {

    private Map<Node, List<Edge>> adjList;

    public Graph(int vertices) {
        adjList = new HashMap<>();
        for (char c = 'A'; c < 'A' + vertices; c++) {
            adjList.put(new Node(c), new LinkedList<>());
        }
    }

    public void addEdge(Node source, Node destination) {
        adjList.get(source).add(new Edge(source, destination));
        // For undirected graph, add the reverse edge
        adjList.get(destination).add(new Edge(destination, source));
    }

    public void printGraph() {
        for (Node node : adjList.keySet()) {
            System.out.print("Vertex " + node.id + ": ");
            for (Edge edge : adjList.get(node)) {
                System.out.print(edge.destination.id + " ");
            }
            System.out.println();
        }
    }

    public List<Node> getNeighbors(Node node) {
        List<Node> neighbors = new ArrayList<>();
        for (Edge edge : adjList.get(node)) {
            neighbors.add(edge.destination);
        }
        return neighbors;
    }

    public static void main(String[] args) {
        Graph g = new Graph(6); // Create a graph with 6 vertices

        // Adding edges based on the given graph
        g.addEdge(new Node('A'), new Node('B')); // A - B
        g.addEdge(new Node('A'), new Node('C')); // A - C
        g.addEdge(new Node('B'), new Node('C')); // B - C
        g.addEdge(new Node('B'), new Node('D')); // B - D
        g.addEdge(new Node('B'), new Node('E')); // B - E
        g.addEdge(new Node('C'), new Node('F')); // C - F
        g.addEdge(new Node('D'), new Node('E')); // D - E
        g.addEdge(new Node('E'), new Node('F')); // E - F

        g.printGraph(); // Print the graph
    }
}


#include <iostream>
#include <list>
#include <vector>

class Node {
public:
    char id;
    Node(char _id) : id(_id) {}
};

class Edge {
public:
    Node* source;
    Node* destination;
    Edge(Node* _source, Node* _destination) : source(_source), destination(_destination) {}
};

class Graph {
    int numVertices;
    std::vector<std::list<Edge>> adjLists;

public:
    Graph(int vertices) : numVertices(vertices), adjLists(vertices) {}

    // Function to add an edge from src to dest
    void addEdge(Node* src, Node* dest) {
        adjLists[src->id - 'A'].push_back(Edge(src, dest));
        // For an undirected graph, add the reverse edge as well
        adjLists[dest->id - 'A'].push_back(Edge(dest, src));
    }

    // Function to print the graph
    void printGraph() {
        for (int i = 0; i < numVertices; i++) {
            std::cout << "Vertex " << char('A' + i) << ": ";
            for (Edge e : adjLists[i]) {
                std::cout << e.destination->id << " ";
            }
            std::cout << "\n";
        }
    }
    
    // Function to get neighbors of a node
    std::list getNeighbors(Node* node) {
        return adjLists[node->id - 'A'];
    }
    
};

int main() {
    Graph g(6); // Create a graph with 6 vertices

    // Adding edges based on the given graph
    g.addEdge(new Node('A'), new Node('B')); // A - B
    g.addEdge(new Node('A'), new Node('C')); // A - C
    g.addEdge(new Node('B'), new Node('C')); // B - C
    g.addEdge(new Node('B'), new Node('D')); // B - D
    g.addEdge(new Node('B'), new Node('E')); // B - E
    g.addEdge(new Node('C'), new Node('F')); // C - F
    g.addEdge(new Node('D'), new Node('E')); // D - E
    g.addEdge(new Node('E'), new Node('F')); // E - F

    g.printGraph(); // Print the graph
    return 0;
}

class Node:
    def __init__(self, _id):
        self.id = _id

class Edge:
    def __init__(self, _source, _destination):
        self.source = _source
        self.destination = _destination

class Graph:
    def __init__(self, num_vertices):
        # Initialize the graph with num_vertices vertices
        self.adj_list = {Node(chr(i + ord('A'))): [] for i in range(num_vertices)}

    def add_edge(self, src, dest):
        # Add an edge from src to dest
        # Since this is an undirected graph, add the reverse edge as well
        self.adj_list[src].append(Edge(src, dest))
        self.adj_list[dest].append(Edge(dest, src))

    def print_graph(self):
        # Print the adjacency list of each vertex
        for key in self.adj_list:
            print(f"Vertex {key.id}: {[edge.destination.id for edge in self.adj_list[key]]}")

    def get_neighbors(self, node):
        # Return a list of neighbors of the given node
        return [edge.destination for edge in self.adj_list[node]]

# Create a graph with 6 vertices (A to F)
g = Graph(6)

# Adding edges based on the given graph
g.add_edge(Node('A'), Node('B')) # A - B
g.add_edge(Node('A'), Node('C')) # A - C
g.add_edge(Node('B'), Node('C')) # B - C
g.add_edge(Node('B'), Node('D')) # B - D
g.add_edge(Node('B'), Node('E')) # B - E
g.add_edge(Node('C'), Node('F')) # C - F
g.add_edge(Node('D'), Node('E')) # D - E
g.add_edge(Node('E'), Node('F')) # E - F

g.print_graph() # Print the graph

class Graph {
    constructor(numVertices) {
        this.adjList = new Map();
        // Initialize the adjacency list
        for (let i = 0; i < numVertices; i++) {
            this.adjList.set(String.fromCharCode(65 + i), []);
        }
    }

    addEdge(src, dest) {
        // Add an edge from src to dest
        // Since this is an undirected graph, also add the edge from dest to src
        this.adjList.get(src).push(dest);
        this.adjList.get(dest).push(src);
    }

    printGraph() {
        // Print the adjacency list for each vertex
        for (let [key, value] of this.adjList) {
            console.log(`Vertex ${key}: ${value.join(', ')}`);
        }
    }

    getNeighbors(node) {
        // Return an array of neighbors of the given node
        return this.adjList.get(node);
    }
}

// Create a graph with 6 vertices (A to F)
const g = new Graph(6);

// Adding edges based on the given graph
g.addEdge('A', 'B'); // A - B
g.addEdge('A', 'C'); // A - C
g.addEdge('B', 'C'); // B - C
g.addEdge('B', 'D'); // B - D
g.addEdge('B', 'E'); // B - E
g.addEdge('C', 'F'); // C - F
g.addEdge('D', 'E'); // D - E
g.addEdge('E', 'F'); // E - F

g.printGraph(); // Print the graph

Graph: Concept and Important Algorithms

1. Basics of Graph Data Structure
2. Breadth-First Search (BFS) in Graph
3. Depth-First Search (DFS) in Graph 
4. Topological Sort in Graph
5. Union-Find Algorithm in Graph
6. Prim's Algorithm in Graph 
7. Dijkstra's Algorithm in Graph
8. Kruskal's Algorithm in Graph

Comments

Popular Posts on Code Katha

Java Interview Questions for 10 Years Experience

Spring Boot Interview Questions for 10 Years Experience

Sql Interview Questions for 10 Years Experience

Visual Studio Code setup for Java and Spring with GitHub Copilot

Spring Data JPA

Java interview questions - Must to know concepts

Data Structures & Algorithms Tutorial with Coding Interview Questions

Elasticsearch Java Spring Boot

Spring Boot Kafka Tutorial