A Graph is a non‑linear data structure consisting of a set of vertices (also called nodes) and a set of edges connecting pairs of vertices. Graphs are used to model relationships and connections between entities, making them one of the most versatile and widely used data structures in computer science.

Basic Terminology

• Vertex (Node): A fundamental unit of a graph representing an entity.
• Edge: A connection between two vertices. Can be directed or undirected.
• Degree: The number of edges incident to a vertex. In directed graphs: in-degree and out-degree.
• Path: A sequence of vertices where each adjacent pair is connected by an edge.
• Cycle: A path that starts and ends at the same vertex.
• Weight: A value assigned to an edge (e.g., cost, distance, time).

Types of Graphs

1. Based on Edge Direction

• Undirected Graph: Edges have no direction. The connection is mutual (e.g., friendship on Facebook).
• Directed Graph (Digraph): Edges have a direction (one‑way). (e.g., Twitter followers, road networks with one‑way streets).

2. Based on Edge Weight

• Unweighted Graph: All edges have the same weight (or no weight).
• Weighted Graph: Each edge has a numerical weight (e.g., distance, cost).

3. Based on Cycles

• Cyclic Graph: Contains at least one cycle.
• Acyclic Graph: Does not contain any cycles. A Directed Acyclic Graph (DAG) is a special case.

4. Based on Connectivity

• Connected Graph: There is a path between every pair of vertices (undirected).
• Disconnected Graph: Some vertices are not reachable from others.
• Strongly Connected: In a directed graph, there is a path from every vertex to every other vertex.
• Weakly Connected: The underlying undirected graph is connected.

5. Special Types

• Complete Graph: Every pair of vertices is connected by an edge.
• Bipartite Graph: Vertices can be divided into two disjoint sets such that every edge connects vertices from different sets.
• Tree: An undirected graph with no cycles (a special case of a graph).
• Multigraph: Multiple edges between the same pair of vertices.
• Simple Graph: No multiple edges or self‑loops.

Graph Representations

1. Adjacency Matrix

A 2D array where matrix[i][j] = 1 indicates an edge from vertex i to j (or weight if weighted).

# Example: 4 vertices
#   0 1 2 3
# 0[0,1,1,0]
# 1[1,0,1,1]
# 2[1,1,0,1]
# 3[0,1,1,0]

class GraphMatrix:
    def __init__(self, vertices):
        self.V = vertices
        self.matrix = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, u, v):
        self.matrix[u][v] = 1
        self.matrix[v][u] = 1  # For undirected graph

    def print_matrix(self):
        for row in self.matrix:
            print(row)

2. Adjacency List

An array of lists where each list contains the neighbors of a vertex. More memory‑efficient for sparse graphs.

# Example: 4 vertices
# 0: [1, 2]
# 1: [0, 2, 3]
# 2: [0, 1, 3]
# 3: [1, 2]

class GraphList:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)  # For undirected graph

    def print_adj(self):
        for i, neighbors in enumerate(self.adj):
            print(f"{i}: {neighbors}")

3. Edge List

A list of all edges (u, v, weight). Simple but less efficient for most operations.

edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
# For weighted: [(0, 1, 5), (0, 2, 3), ...]

Implementation in Python

Adjacency List (Most Common)

class Graph:
    def __init__(self, directed=False):
        self.graph = {}
        self.directed = directed

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, u, v, weight=None):
        self.add_vertex(u)
        self.add_vertex(v)
        if weight is not None:
            self.graph[u].append((v, weight))
            if not self.directed:
                self.graph[v].append((u, weight))
        else:
            self.graph[u].append(v)
            if not self.directed:
                self.graph[v].append(u)

    def get_neighbors(self, vertex):
        return self.graph.get(vertex, [])

    def print_graph(self):
        for vertex, neighbors in self.graph.items():
            print(f"{vertex}: {neighbors}")

# Example usage
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.print_graph()
# Output:
# 0: [1, 2]
# 1: [0, 2, 3]
# 2: [0, 1, 3]
# 3: [1, 2]

# Weighted graph
gw = Graph()
gw.add_edge(0, 1, 5)
gw.add_edge(0, 2, 3)
gw.add_edge(1, 2, 2)
gw.add_edge(1, 3, 4)
gw.add_edge(2, 3, 1)
gw.print_graph()

Implementation in Java

Adjacency List

import java.util.*;

class Graph {
    private Map> adjList;
    private boolean directed;

    public Graph(boolean directed) {
        this.directed = directed;
        adjList = new HashMap<>();
    }

    public void addVertex(int v) {
        adjList.putIfAbsent(v, new ArrayList<>());
    }

    public void addEdge(int u, int v) {
        addVertex(u);
        addVertex(v);
        adjList.get(u).add(v);
        if (!directed) {
            adjList.get(v).add(u);
        }
    }

    public List getNeighbors(int v) {
        return adjList.getOrDefault(v, new ArrayList<>());
    }

    public void printGraph() {
        for (Map.Entry> entry : adjList.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }

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

Weighted Graph

import java.util.*;

class WeightedGraph {
    private Map> adjList;
    private boolean directed;

    static class Edge {
        int to;
        int weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public WeightedGraph(boolean directed) {
        this.directed = directed;
        adjList = new HashMap<>();
    }

    public void addEdge(int u, int v, int weight) {
        adjList.putIfAbsent(u, new ArrayList<>());
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.get(u).add(new Edge(v, weight));
        if (!directed) {
            adjList.get(v).add(new Edge(u, weight));
        }
    }

    public List getNeighbors(int v) {
        return adjList.getOrDefault(v, new ArrayList<>());
    }
}

Implementation in C++

Adjacency List

#include 
#include 
#include 
#include 
using namespace std;

class Graph {
private:
    unordered_map> adjList;
    bool directed;

public:
    Graph(bool dir = false) : directed(dir) {}

    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        if (!directed) {
            adjList[v].push_back(u);
        }
    }

    void printGraph() {
        for (auto& pair : adjList) {
            cout << pair.first << ": ";
            for (int neighbor : pair.second) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(false);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.printGraph();
    return 0;
}

Weighted Graph

#include 
#include 
#include 
#include 
using namespace std;

class WeightedGraph {
private:
    struct Edge {
        int to;
        int weight;
        Edge(int t, int w) : to(t), weight(w) {}
    };

    unordered_map> adjList;
    bool directed;

public:
    WeightedGraph(bool dir = false) : directed(dir) {}

    void addEdge(int u, int v, int weight) {
        adjList[u].push_back(Edge(v, weight));
        if (!directed) {
            adjList[v].push_back(Edge(u, weight));
        }
    }

    void printGraph() {
        for (auto& pair : adjList) {
            cout << pair.first << ": ";
            for (auto& edge : pair.second) {
                cout << "(" << edge.to << "," << edge.weight << ") ";
            }
            cout << endl;
        }
    }
};

Complexity Analysis

Advantages & Disadvantages

Advantages

• Versatile: Models many real‑world relationships (social networks, maps, dependencies).
• Rich Theory: Many well‑studied algorithms for traversal, shortest path, connectivity, etc.
• Flexible Representations: Can be represented in multiple ways (matrix, list, edge list).

Disadvantages

• Memory Intensive: For dense graphs, adjacency matrix uses O(V²) memory.
• Complex Implementation: More complex than simpler data structures.
• Traversal: Requires careful handling to avoid cycles.

Applications

• Social Networks: Facebook, LinkedIn, Twitter (users as vertices, connections as edges).
• Navigation Systems: GPS, maps, route planning (intersections as vertices, roads as weighted edges).
• Web Crawling: Web pages as vertices, hyperlinks as edges.
• Network Routing: Computer networks, packet routing.
• Dependency Management: Task scheduling, build systems (DAGs).
• Recommendation Systems: Users and items as vertices, interactions as edges.
• Neural Networks: Neurons as vertices, connections as weighted edges.
• Knowledge Graphs: Entities and relationships in AI systems.

Common Graph Problems

• Shortest Path: Dijkstra's, Bellman‑Ford, Floyd‑Warshall.
• Traversal: Breadth‑First Search (BFS), Depth‑First Search (DFS).
• Minimum Spanning Tree: Kruskal's, Prim's.
• Cycle Detection: Detect cycles in directed/undirected graphs.
• Topological Sorting: Ordering of vertices in a DAG.
• Connected Components: Finding all connected components.
• Graph Coloring: Assign colors to vertices so adjacent vertices have different colors.
• Maximum Flow: Ford‑Fulkerson algorithm.

Key Takeaways

• A graph consists of vertices and edges connecting them.
• Graphs can be directed or undirected, weighted or unweighted, cyclic or acyclic.
• Common representations: adjacency matrix (dense graphs) and adjacency list (sparse graphs).
• Graphs are used to model real‑world networks and relationships.
• Key algorithms: BFS, DFS, Dijkstra's, Kruskal's, Prim's, and topological sort.