Vertices, edges, and graph types

What is a graph?

A graph is a collection of vertices and edges. A vertex, also called a node, represents an item. An edge represents a connection between two items. Edges can have a direction or a weight. Graph traversal visits connected vertices while remembering which have already been visited.

Example: Let A, B, and C be vertices, with edges A–B and B–C. A can reach C through B. A directed edge A → B permits movement from A to B but does not automatically permit movement back.

Helpful before this chapter

If these ideas are new, begin with:

Hash maps and sets Queues and deques Recursion

Understand the idea

Vertices are entities; edges encode a relation. Direction, weight, parallel edges, and self-loops affect valid algorithms. Model exactly what one traversal step means before choosing a method.

Work through an example

A friendship edge is usually undirected; a prerequisite A→B is directed. Travel time needs weights, while one move in an equal-cost grid can use unweighted edges.

Time and space complexity

V vertices/E edges determine graph bounds; directed E counts each stored directed edge.

Why it works

The graph contains precisely the transitions permitted by the problem.

Common mistakes

Treating one-way roads as undirected invents routes.
Reachability differs from cheapest-path distance.

Chapter lab · Python implementation

A graph models entities and connections; edges can be directed or undirected, weighted or unweighted. Our lab uses adjacency lists and marks BFS vertices when enqueuing. The diagram has a cycle A-B-D-C-A, so visited state is essential. Distances count edges because every edge has equal cost.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from collections import deque

def bfs(graph,start):
    distances={start:0}
    parent={start:None}
    queue=deque([start])
    while queue:
        node=queue.popleft()
        for neighbor in graph.get(node,[]):
            if neighbor not in distances:
                distances[neighbor]=distances[node]+1
                parent[neighbor]=node
                queue.append(neighbor)
    return distances,parent

def components(graph):
    seen=set(); count=0
    for start in graph:
        if start in seen: continue
        count+=1; seen.add(start); stack=[start]
        while stack:
            node=stack.pop()
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor); stack.append(neighbor)
    return count

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

g={'A':['B','C'],'B':['A','D'],'C':['A','D'],'D':['B','C'],'E':[]}
d,p=bfs(g,'A'); assert d=={'A':0,'B':1,'C':1,'D':2}
assert p['D'] in ['B','C']
assert components(g)==2
assert bfs({'X':[]},'X')[0]=={'X':0}

CHECK YOUR UNDERSTANDING