Day 23: Introduction to Graphs and Their Properties – Types and Representations Explained

Graphs are one of the fundamental data structures in computer science. Understanding graphs and their properties is essential for tackling problems in areas such as networking, social media analysis, and even game development.

What is a Graph?

A graph is a collection of nodes (also called vertices) and edges (connections between nodes). In a graph, nodes can represent objects, and edges represent the relationships between those objects.

Types of Graphs: Directed vs. Undirected

There are two primary types of graphs:

  • Undirected Graphs: The edges in an undirected graph do not have a direction. This means that if there is an edge between node A and node B, you can travel both from A to B and from B to A.
  • Directed Graphs (Digraphs): In a directed graph, the edges have a direction. An edge from node A to node B doesn’t imply you can travel from B to A unless explicitly stated by a reverse edge.

Graph Representation

Graphs can be represented in two major ways:

  1. Adjacency Matrix: A 2D array where the cell at position [i][j] is 1 if there is an edge from node i to node j, otherwise 0.
  2. Adjacency List: An array of lists where each node has a list of adjacent nodes (nodes that it is connected to).

Example in Python (Adjacency List Representation):

pythonCopy codegraph = {
    0: [1, 4],
    1: [0, 2],
    2: [1, 3],
    3: [2],
    4: [0]
}

Applications of Graphs

  • Networking: Representing connections between devices.
  • Social Networks: Modeling relationships between users.
  • Recommendation Systems: Graphs help in representing products and their interrelations.

Example of Adjacency List Representation in Java:

javaCopy codeimport java.util.*;

public class Graph {
    Map<Integer, List<Integer>> graph = new HashMap<>();

    // Add edge
    public void addEdge(int node, int neighbor) {
        graph.computeIfAbsent(node, k -> new ArrayList<>()).add(neighbor);
    }

    // Print the graph
    public void printGraph() {
        for (int node : graph.keySet()) {
            System.out.print(node + " -> ");
            for (int neighbor : graph.get(node)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(0, 1);
        g.addEdge(0, 4);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 2);
        g.addEdge(4, 0);
        g.printGraph();
    }
}