Graphs

Graphs

• A graph is a set of nodes (also called vertices) joined by edges (connections).
• Graphs model networks: friends, roads between cities, links between web pages.
• A tree is really a special graph; a general graph can have cycles and many links per node.

Representing a graph: adjacency list

• One common way is an adjacency list: a dictionary mapping each node to its list of neighbours.
• graph["A"] is the list of nodes directly connected to A.
• This is compact when each node has only a few connections.

# A graph as a dict: each node maps to its list of neighbours
graph = {
    "A": ["B", "C"],
    "B": ["A"],
    "C": ["A"],
}
print(graph["A"])    # ['B', 'C']  -- A connects to B and C
print(graph["B"])    # ['A']

Adding an edge

• In an undirected graph, an edge A—B goes both ways.
• So adding it means appending B to A's list and A to B's list.
• If a node is new, start it with an empty list first.

def add_edge(graph, a, b):
    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []
    graph[a].append(b)
    graph[b].append(a)

graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "A", "C")
print(graph)    # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}

Walking the neighbours

• To explore from a node, you read its neighbour list and visit each one.
• A node that is not in the graph has no neighbours — return an empty list, not an error.
• This neighbour lookup is the first step of bigger jobs like searching the whole graph.

Directed vs undirected

• In an undirected graph an edge works both ways (a friendship).
• In a directed graph an edge points one way only (a one-way street, a "follows" link).
• For directed edges you would append in one direction only.

Now you try

• Build the adjacency-list operations: add_edge, neighbours, and count_edges.
• Each task checks your function on a small graph.
• Press Check answer to test it.