📘 What I Learned About Graphs Today

🌐 What is a Graph?

A graph is a collection of:

• Vertices (nodes): The entities (e.g., cities, people).

• Edges: Connections between them (e.g., roads, friendships).

---

🔗 Graph Representations

There are two common ways to represent graphs in code:

1. Adjacency Matrix

• A 2D array where matrix[i][j] is 1 if there's an edge from node i to j, else 0.

• Great for dense graphs.

Example for a graph with 3 nodes:

    0 -- 1
     \   
      2

Adjacency Matrix:
[
 [0, 1, 1],
 [1, 0, 0],
 [1, 0, 0]
]

2. Adjacency List

• A dictionary where each key is a node and the value is a list of its neighbors.

• Better for sparse graphs.

Example:

graph = {
    0: [1, 2],
    1: [0],
    2: [0]
}

---

🧭 Types of Graphs

• Directed vs. Undirected: Edges have direction or not.

• Weighted vs. Unweighted: Edges may have weights (e.g., distance).

• Cyclic vs. Acyclic: Whether you can form a loop.

• Connected vs. Disconnected: Whether all nodes are reachable from each other.

---

🚶‍♂️ Graph Traversal

How do we move through a graph? Two popular methods:

🔍 1. DFS (Depth-First Search)

• Goes deep into the graph before backtracking.

• Implemented using stack or recursion.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

dfs(graph, 0)

🌊 2. BFS (Breadth-First Search)

• Explores all neighbors before going deeper.

• Implemented using a queue.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

bfs(graph, 0)

---

🧠 Summary