Graph Data Structure - Know Program

Graph Data Structure | A graph is a data structure consisting of a collection of nodes (or vertices) and edges that connect pairs of nodes. Graphs are used to represent relationships and connections between different entities, making them ideal for modeling networks, such as social networks, transportation systems, and the Internet. They come in various forms, including directed, undirected, weighted, and unweighted graphs, each serving different types of problems and applications.

Graph (G) = (V, E)
Vertices (V) = { v_1, v_2, v_3, v_4, v_5 }
Edges (E) = { (v_1, v_2), (v_1, v_3), (v_2, v_4), (v_3, v_4), (v_3, v_5) }

  v1 ---- v3
  |        |\
  |        | \
  |        |  v5
  |        | /
  |        |/
  v2 ---- v4

Directed vs Undirect Graph

Directed Graph (Digraph)

Definition: A graph where edges have a direction, indicated by arrows.
Edges: Represented as ordered pairs (u, v) indicating a direction from vertex u to vertex v.
Representation:

Adjacency List: Each vertex points to a list of its outgoing edges.
Adjacency Matrix: A matrix where A[i][j] = 1 indicates a directed edge from vertex i to vertex j.

Applications:

Modeling one-way streets in a city.
Representing dependencies in task scheduling.
Illustrating state transitions in finite state machines.

     v1 → v2
      ↓    ↓
      v4 ← v3

Undirected Graph

Definition: A graph where edges have no direction.
Edges: Represented as unordered pairs {u, v}, implying a connection between u and v in both directions.
Representation:

Adjacency List: Each vertex points to a list of all its neighboring vertices.
Adjacency Matrix: A symmetric matrix where A[i][j] = 1 indicates an edge between vertex i and vertex j.

Applications:

Modeling two-way streets in a city.
Representing social networks where connections are mutual.
Illustrating electrical circuits with undirected connections.

     v1 -- v2
     |    /
     |  / 
     v4 -- v3

Key Differences:

Edge Direction: Directed graphs have edges with directions, while undirected graphs have edges without directions.
Traversal: In directed graphs, you can only traverse edges in the specified direction, whereas in undirected graphs, traversal is possible in both directions.
Representation: Directed graphs need to track direction in their data structures, while undirected graphs only track connectivity.

Practical Example:

Directed Graph: Use a digraph to represent prerequisites in a course dependency where each arrow points from a prerequisite to the dependent course.
Undirected Graph: Use an undirected graph to represent a friendship network where each edge indicates a mutual friendship.

Degree of Vertices in Directed and Undirected Graphs

Undirected Graph: The degree of a vertex is the number of edges connected to it. Each edge contributes 1 to the degree of both vertices it connects.

     v1 -- v2
     |    / 
     |  /
     v3 -- v4

Degrees:

v1: 2 (connected to v2 and v3)
v2: 2 (connected to v1, and v3)
v3: 3 (connected to v1, v2, and v4)
v4: 1 (connected to v3)

Sum of degrees = 2 * |E|
Maximum number of edges = ( |V| * ( |V| – 1 ) ) / 2

Directed Graph:

In-Degree: The number of edges coming into a vertex.
Out-Degree: The number of edges going out from a vertex.

     v1 → v2
      ↓    ↓
      v4 ← v3

In-Degree and Out-Degree:

v1: In-Degree = 0, Out-Degree = 2 (edges to v2 and v3)
v2: In-Degree = 1, Out-Degree = 1 (edge from v1, edge to v4)
v3: In-Degree = 1, Out-Degree = 1 (edge from v1, edge to v4)
v4: In-Degree = 2, Out-Degree = 0 (edges from v2 and v3)

Sum of indegrees = |E|
Sum of outdegrees = |E|
Maximum number of edges = ( |V| * ( |V| – 1 ) )

Terms

Walk: A sequence of vertices and edges where each edge’s endpoints are the preceding and succeeding vertices in the sequence. Example: v1 → v2 → v3 → v4 → v2.
Path: A walk with no repeated vertices or edges. Example: In the graph below, a path could be v1 → v2 → v4.
Cyclic Graph: A graph that contains at least one cycle (a closed path with no repeated edges or vertices, except for the starting/ending vertex). Example: In the graph below, v1 → v2 → v4 → v1 forms a cycle.
Acyclic Graph: A graph with no cycles. Example: Removing an edge from the cyclic graph to ensure no cycles are present.

Examples in the Graph:

Walk: v1 → v2 → v4 → v3 → v1
Path: v1 → v2 → v4
Cycle: v1 → v2 → v4 → v1 (cyclic)
Acyclic: Remove v2 → v4 to make the graph acyclic.

Weighted and Unweighted Graphs

Weighted Graphs: Each edge has an associated numerical value, called a weight. Purpose: Used to represent the cost, distance, or capacity between vertices.

       3
     v1----v2
     |   /  \
  5  | 2/    \4
     | /      \
     v3-------v4
        1

The numbers on the edges represent the weights. Applications: Shortest path algorithms (e.g., Dijkstra’s), network routing, and resource allocation.

Unweighted Graphs: Edges do not have weights; they simply show the connection between vertices. Purpose: Used to represent relationships without any specific cost or distance.

     v1----v2
     |    /  \
     |  /     \
     | /       \
     v3--------v4

All edges are treated equally. Applications: Social networks, basic connectivity, and simple relationship mappings.

Graph Representation

Graphs can be represented in several ways, depending on the use case and efficiency considerations. Here are the most common methods:

Adjacency Matrix
Adjacency List

Adjacency Matrix

Adjacency Matrix: A 2D array where the cell at row (i) and column (j) indicates the presence (and possibly the weight) of an edge between vertices (i) and (j).

Structure:

Undirected Graph: Symmetric matrix.
Directed Graph: Asymmetric matrix.

Undirected Graph Example:

Adjacency Matrix:

How to handle vertices with arbitrary names?

ABC
 | \
 |  CDE---EFG
 | /
BCD

For efficient implementation, one hash table h would also be required to do reverse mapping.
h{ABC} = 0
h{BCD} = 1
h{CDE} = 2
h{EFG} = 3

    0 1 2 3
0 [0 1 0 1]
1 [1 0 1 0]
2 [0 1 0 1]
3 [0 0 1 0]

Properties of Adjacency Matrix Representation

Space Required: Θ(v × v)
Operations:
Check if u and v are adjacent: Θ(1), check matrix[u][v] == 1
Find all vertices adjacent to u: Θ(v), traverse through the row and find those columns where the value is 1.
Find the degree of u: Θ(v), traverse through the row and count 1
Add/Remove an Edge: Θ(1), just add/remove entry from the matrix.
Add/Remove a Vertex: Θ(v²) because we have to create another matrix.

Adjacency matrix:

    0 1 2 3
0 [0 1 0 1]
1 [1 0 1 0]
2 [0 1 0 1]
3 [1 0 1 0]

The adjacency matrix stores both information:- 0 (not connected), and 1 (connected) which creates overhead. Instead of that,t we can store only connected vertices information through the Adjacency list.

Adjacency List

An array of lists. The index of the array represents a vertex, and each element in its list represents the vertices it is connected to.

Structure

Undirected Graph: Each edge is represented twice.
Directed Graph: Each edge is represented once.

Undirected Graph Example:

Adjacency List:

0: [1, 2]
1: [0, 2]
2: [0, 1, 3]
3: [2]

An array of lists where lists are most popularly represented as:-

Dynamic Sized Arrays
Linked Lists

Directed Graph Example:

    0 → 1
    ↓  ↘
    2 ← 3

Adjacency List: In the context of directed graphs, when using an adjacency list, we typically focus on counting the outgoing edges (those that point from the vertex to others).
0: [1, 2]
1: [3]
2: [ ]
3: [2]

Space: Θ(V + E)

Undirected: V + 2*E (2*E because every edge contributes to 2 cells in the adjacency list representation).
Directed: V + E

Operations:

Check if there is an edge from u to v: O(V), traverse through a list, and check.
Find all adjacent of u: Θ(degree(u)), traverse through a list.
Find the degree of u: Θ(1), and return the size of the list.
Add an edge: Θ(1), just add the item to the list.
Remove an edge: O(V), remove the item from all adjacent list

Adjacency List Implementation in Java

0: [1, 2]
1: [0, 2, 3]
2: [0, 1]
3: [1]

import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        int vertices = 4; // optional
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(vertices);

        for (int i = 0; i < vertices; i++) {
            adj.add(new ArrayList<>());
        }
        addEdge(adj, 0, 1);
        addEdge(adj, 0, 2);
        addEdge(adj, 1, 2);
        addEdge(adj, 1, 3);

        printGraph(adj);
    }

    private static void printGraph(ArrayList<ArrayList<Integer>> adj) {
        for (int i = 0; i < adj.size(); i++) {
            for (int j = 0; j < adj.get(i).size(); j++) {
                System.out.print(adj.get(i).get(j) + " ");
            }
            System.out.println();
        }
    }

    private static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }
}

Comparison of Adjacency List and Adjacency Matrix

Property	Adjacency List	Adjacency Matrix
Memory	Θ(V + E)	Θ(V × V)
Check if there is an edge from u to v	O(V)	Θ(1)
Find all adjacent of u	Θ(degree(u))	Θ(V)
Add an Edge	Θ(1)	Θ(1)
Remove an Edge	O(V)	Θ(1)
Undirected Graph Edge Count	0 ≤ E ≤ V * (V – 1) / 2	0 ≤ E ≤ V * (V – 1)

Breadth First Search (BFS)

First Version: Given an undirected graph and a source vertex ‘s’, print BFS from the given source.

s = 0
Output: 0 1 2 3 4

Consider yourself at 0, and 1 and 2 are your friends, 3 and 4 are friends of 2, and so on. So, first, print your friends (in any order), and then your friends.

s = 0
Output: 0 1 2 3

s = 0
Output: 0 1 2 5 3 4
0 has friends 1, 2, and 5. 1 has 3, and 2 has 4.

Steps for BFS:

Initialize Structures:

Create a queue to keep track of vertices to visit.
Create a set (or list) to keep track of visited vertices.

Start with the Source Vertex:

Mark the source vertex s as visited.
Add the source vertex s to the queue.

Process the Queue:

While the queue is not empty, repeat the following:
1. Dequeue a vertex v from the front of the queue.
2. Print or store the dequeued vertex v.
3. For each adjacent vertex u of v:
If u has not been visited, mark it as visited and enqueue it.

private static void BFS(ArrayList<ArrayList<Integer>> adj, int vertices, int source) {
    boolean[] visited = new boolean[vertices + 1];
    Queue<Integer> q = new LinkedList<>();

    visited[source] = true;
    q.offer(source);

    while (!q.isEmpty()) {
        int u = q.poll();
        System.out.print(u + " ");

        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                q.offer(v);
            }
        }
    }
}

In main():-

int source = 0;
BFS(adj, vertices, source);

Second Version: No source is given and the graph may be disconnected. Example of disconnected graph:-

      0        4
   /   \                / \
  1      2    5__6
   \   /
      3

import java.util.ArrayList;

public class Graph {

    private int vertices;
    ArrayList<ArrayList<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u); // since the graph is undirected
    }
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        int vertices = 7; // 7 vertices, from 0 to 6
        Graph graph = new Graph(vertices);

        // Adding edges to the graph
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(4, 5);
        graph.addEdge(4, 6);

        // Perform BFS for the entire graph, even if disconnected
        bfsDisconnected(graph.adjList, vertices);
    }

    private static void bfsDisconnected(ArrayList<ArrayList<Integer>> adjList, int vertices) {
        boolean[] visited = new boolean[vertices];
        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                bfs(adjList, i, i, visited);
            }
        }

    }

    private static void bfs(ArrayList<ArrayList<Integer>> adj, int vertices, 
                 int source, boolean[] visited) {
        Queue<Integer> q = new LinkedList<>();

        visited[source] = true;
        q.offer(source);

        while (!q.isEmpty()) {
            int u = q.poll();
            System.out.print(u + " ");

            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.offer(v);
                }
            }
        }
    }
}

Time complexity: O(V + E).

Counting Connected Components in an Undirected Graph

This question is also asked as the number of islands in a graph.

      0     3   5
   /   \         |       / \
  1 __  2  4  6  7
                                    |
                                      8

public class Main {
    public static void main(String[] args) {
        int vertices = 9;
        Graph graph = new Graph(vertices);

        // Adding edges to the graph
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(3, 4);
        graph.addEdge(5, 6);
        graph.addEdge(5, 7);
        graph.addEdge(7, 8);

        // Perform BFS for the entire graph, even if disconnected
        System.out.println(countConnectedComponents(graph.adjList, vertices));
    }

    private static int countConnectedComponents(ArrayList<ArrayList<Integer>> adjList, 
                int vertices) {
        boolean[] visited = new boolean[vertices];
        int count = 0;
        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                count++;
                bfs(adjList, i, i, visited);
            }
        }
        return count;
    }

    // bfs()
}

Application of BFS

Shortest Path in an Unweighted Graph: BFS finds the shortest path between two vertices in an unweighted graph because it explores all nodes at the present depth level before moving on to nodes at the next depth level. Use Case: Finding the shortest path in road networks or mazes.
Crawler in Search Engines: Search engines like Google use BFS to crawl web pages. Starting from a set of seed URLs, the crawler visits each URL and extracts links, continuing the process in a breadth-first manner. Use Case: Indexing web pages for search engines.
Peer-to-Peer Networks: In peer-to-peer (P2P) networks, BFS is used to search for resources by broadcasting a query message to the nearest nodes, which in turn broadcast to their nearest nodes, and so on. Use Case: File-sharing systems like BitTorrent.
Social Networking Search: BFS is used to find the shortest path or connections between users in a social network, such as finding degrees of separation. Use Case: Friend suggestions or finding mutual friends.
In Garbage Collection (Cheney’s Algorithm): BFS is used in garbage collection to trace live objects starting from root nodes and marking all reachable nodes, ensuring that all live data is retained. Use Case: Memory management in programming languages like Java and C#.
Cycle Detection: BFS can be used to detect cycles in an undirected graph by checking if a vertex is revisited while traversing. Use Case: Detecting deadlocks in resource allocation graphs.
Ford-Fulkerson Algorithm: BFS is used in the Ford-Fulkerson method for finding maximum flow in a flow network. It helps in finding augmenting paths. Use Case: Network flow optimization, such as in transportation and telecommunication networks.
Broadcasting: BFS is used to broadcast a message to all nodes in a network. It ensures that the message reaches every node efficiently. Use Case: Spreading information quickly in a network, such as updates in distributed systems.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!