Graph — Explained with Examples

A graph is a data structure of nodes (vertices) connected by edges, modeling relationships and networks across domains.

Graphs consist of vertices (V) and edges (E). They can be directed (edges have direction, like Twitter follows) or undirected (bidirectional, like Facebook friends). Edges can be weighted (with costs/distances) or unweighted. Graphs are represented as adjacency lists (each vertex stores its neighbors) or adjacency matrices (2D array of edge existence). Common graph algorithms include BFS, DFS, Dijkstra, and topological sort.

Think of a graph like a city metro map. Stations are vertices, rail lines are edges. Some lines run one way (directed), some have distances between stations (weighted). The map helps you find routes, shortest paths, and connections.

Graphs model countless real-world systems: social networks, web pages (links are directed edges), road networks, dependency trees, and communication networks.

# Adjacency list representation
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B', 'E', 'F'],
    'E': ['C', 'D'],
    'F': ['D']
}

# Weighted graph as adjacency list
weighted_graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 5)],
    'C': [('A', 2), ('E', 1)],
    'D': [('B', 5), ('E', 3), ('F', 6)],
    'E': [('C', 1), ('D', 3)],
    'F': [('D', 6)]
}

# Check if path exists (DFS)
def has_path(graph, start, end, visited=None):
    if visited is None:
        visited = set()
    if start == end:
        return True
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            if has_path(graph, neighbor, end, visited):
                return True
    return False

print(has_path(graph, 'A', 'F'))  # True

Graph size is measured as V vertices and E edges. Sparse graphs (E « V²) use adjacency lists; dense graphs use matrices. Many real-world graphs follow a power-law degree distribution (scale-free networks).

BFS, DFS, Tree, Linked List

Graph Traversal with BFS