Graphs

vertex (node)   — a point in the graph
edge            — a connection between two vertices
degree          — number of edges at a vertex
path            — sequence of vertices connected by edges
cycle           — path that starts and ends at the same vertex
connected graph — path exists between every pair of vertices
DAG             — Directed Acyclic Graph (no cycles, directed edges)
weight          — numeric value assigned to an edge

# Undirected graph — edges have no direction
# A --5-- B
# |       |
# 3       2
# |       |
# C --1-- D
# Edge (A,B) == edge (B,A)

# Directed graph (digraph) — edges are one-way arrows
# A → B → C
#     ↓
#     D
# Edge (A,B) does NOT imply (B,A)

# Weighted graph — each edge carries a numeric weight
# Used in shortest path and MST algorithms

from collections import defaultdict

# Undirected graph as adjacency list
graph = defaultdict(list)

def add_edge(u, v):
    graph[u].append(v)
    graph[v].append(u)   # omit this line for directed graph

add_edge("A", "B")
add_edge("A", "C")
add_edge("B", "D")
add_edge("C", "D")

print(dict(graph))
# {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']}

# Neighbours of A
print(graph["A"])   # ['B', 'C']

# 4-vertex graph (0-indexed)
# Vertices: 0=A, 1=B, 2=C, 3=D
n = 4
matrix = [[0] * n for _ in range(n)]

def add_edge_matrix(u, v):
    matrix[u][v] = 1
    matrix[v][u] = 1   # undirected

add_edge_matrix(0, 1)   # A-B
add_edge_matrix(0, 2)   # A-C
add_edge_matrix(1, 3)   # B-D
add_edge_matrix(2, 3)   # C-D

# Print matrix
for row in matrix:
    print(row)
# [0, 1, 1, 0]  — A connects to B and C
# [1, 0, 0, 1]  — B connects to A and D
# [1, 0, 0, 1]  — C connects to A and D
# [0, 1, 1, 0]  — D connects to B and C

# Edge check: O(1)
print(matrix[0][1])  # 1 — A→B exists

# Weighted adjacency list — each neighbour is (vertex, weight)
wgraph = defaultdict(list)

def add_weighted_edge(u, v, w):
    wgraph[u].append((v, w))
    wgraph[v].append((u, w))

add_weighted_edge("A", "B", 5)
add_weighted_edge("A", "C", 3)
add_weighted_edge("B", "D", 2)
add_weighted_edge("C", "D", 1)

print(wgraph["A"])   # [('B', 5), ('C', 3)]

# Weighted adjacency matrix — store weight instead of 1
INF = float('inf')
wmatrix = [[INF] * n for _ in range(n)]
for i in range(n):
    wmatrix[i][i] = 0   # distance to self = 0

class Graph:
    def __init__(self, directed=False):
        self.adj      = defaultdict(list)
        self.directed = directed

    def add_edge(self, u, v, weight=1):
        self.adj[u].append((v, weight))
        if not self.directed:
            self.adj[v].append((u, weight))

    def neighbours(self, v):
        return self.adj[v]

    @property
    def vertices(self):
        return list(self.adj.keys())

g = Graph(directed=True)
g.add_edge("A", "B", 4)
g.add_edge("A", "C", 2)
g.add_edge("B", "D", 5)
g.add_edge("C", "D", 1)

print(g.neighbours("A"))   # [('B', 4), ('C', 2)]