Graphs

Graph definition and notation

Definition. A graph $G=(V,E)$ has a set V of vertices and a set E of edges. In an undirected graph, an edge is an unordered pair; in a directed graph, it is an ordered pair called an arc. A simple graph has no self-loops or parallel edges unless the problem allows them.

Example. V={A,B,C}, E={{A,B},{B,C}} is an undirected path.

Exam point. State whether edges are directed and whether parallel edges count separately.

Order, size, and degree

Definition. The order of a graph is $|V|$ and its size is $|E|$. In an undirected graph, degree counts incident edges, with a loop contributing two if loops are allowed. In a directed graph, indegree counts incoming arcs and outdegree counts outgoing arcs.

Example. In A—B—C, degree(B)=2 and degree(A)=1.

Exam point. The sum of undirected degrees is $2|E|$.

Solved calculation. An undirected graph has vertex degrees 3,2,2,1. How many edges does it have?

1. Degree sum is $3+2+2+1=8$.
2. Each edge contributes 2 to the degree sum.
3. Therefore $|E|=8/2=4$. Answer. 4 edges.

Walks, trails, paths, and cycles

Definition. A walk is a sequence of adjacent vertices and may repeat vertices or edges. A trail does not repeat edges. A path does not repeat vertices. A cycle is a closed path subject to the graph's convention for minimum length. In directed graphs, each step must follow arc direction.

Example. A→B→C→B is a directed walk but not a simple path because B repeats.

Exam point. Check what repetition is forbidden in the requested object.

Connectivity and components

Definition. An undirected graph is connected if a path exists between every pair of vertices. Its connected components are maximal connected vertex sets. A directed graph is strongly connected if every vertex can reach every other by directed paths; weak connectivity ignores edge directions.

Example. Two separate undirected triangles form two connected components.

Exam point. A directed graph can be weakly connected but not strongly connected.

Solved example. Directed vertices A,B,C have arcs A→B and B→C. Is the graph weakly or strongly connected?

1. Ignoring direction, all vertices lie on the chain A—B—C, so the underlying undirected graph is connected.
2. There is a directed path from A to C.
3. There is no directed path from C back to A.
4. Strong connectivity therefore fails. Answer. Weakly connected, not strongly connected.

Adjacency matrix

Definition. For n vertices, an adjacency matrix is an n×n table whose entry indicates whether an edge or arc connects a vertex pair. In an undirected simple graph it is symmetric with zero diagonal. It uses O(n²) space and tests adjacency in O(1) time.

Example. Edge A—B sets both matrix entries M[A,B] and M[B,A] to 1.

Exam point. For a directed graph, the matrix need not be symmetric.

Solved construction. Build the adjacency matrix for undirected vertices A,B,C,D and edges AB, AC, CD.

1. Order rows and columns A,B,C,D.
2. Mark AB symmetrically at (A,B),(B,A).
3. Mark AC and CD symmetrically.
4. All other entries, including diagonal, are 0.

	A	B	C	D
A	0	1	1	0
B	1	0	0	0
C	1	0	0	1
D	0	0	1	0

Answer. The displayed symmetric matrix represents exactly the three edges.

Adjacency lists

Definition. An adjacency list stores, for each vertex, the vertices reachable by one edge or outgoing arc. For an undirected graph, each edge normally appears in two lists; for a directed graph it appears in the source list. Space is O(V+E), making lists suitable for sparse graphs.

Example. For A—B and A—C, list A contains B,C while B and C each contain A.

Exam point. Traversal order can depend on the order neighbors are stored.

Solved representation. Write lists for directed arcs A→B, A→C, C→B, B→D.

1. A has outgoing neighbors B and C.
2. B has outgoing neighbor D.
3. C has outgoing neighbor B.
4. D has no outgoing neighbor. Answer. A:[B,C], B:[D], C:[B], D:[].

Representation comparison

Definition. Adjacency matrices use O(V²) space independent of edge count and provide constant-time adjacency tests. Adjacency lists use O(V+E) space and enumerate neighbors in time proportional to degree. Edge lists store only edges and are compact when algorithms mainly scan all edges.

Representation	Space	Test edge (u,v)	Enumerate neighbors of u
Matrix	$O(V^2)$	$O(1)$	$O(V)$
List	$O(V+E)$	$O(deg(u))$ typical	$O(deg(u))$
Edge list	$O(E)$	$O(E)$	$O(E)$ scan

Example. A dense graph may favor a matrix; a sparse graph often favors lists.

Exam point. State whether the graph is sparse or dense when comparing memory.

Breadth-first search

Definition. BFS explores vertices in nondecreasing number of edges from a start vertex, using a queue. Mark a vertex visited when it is enqueued to prevent duplicate insertions. In an unweighted graph, BFS tree distances give shortest path lengths in edges from the source.

Example. Starting at A in A—B, A—C, B—D visits A before B and C, then D.

Exam point. Neighbor ordering can change traversal order but not shortest distances.

Solved trace. Undirected edges are AB, AC, BD, CE, DE. Run BFS from A, examining neighbors alphabetically.

1. Queue [A]; visit A and enqueue B,C.
2. Remove B; enqueue D. Queue [C,D].
3. Remove C; enqueue E. Queue [D,E].
4. Remove D; its neighbors are already discovered. Queue [E].
5. Remove E; all neighbors are discovered. Answer. BFS order A,B,C,D,E; distances are 0,1,1,2,2.

Depth-first search

Definition. DFS explores one path as far as possible before backtracking. It can use recursion or an explicit stack. With adjacency lists, DFS takes O(V+E) time; a recursive implementation uses stack space proportional to traversal depth.

Example. DFS from A may visit A,B,D before returning to explore C.

Exam point. Exact DFS order depends on neighbor order and whether marking occurs at discovery.

Solved trace. Use undirected edges AB, AC, BD, CE, DE; run recursive DFS from A with alphabetical neighbors.

1. Visit A; first neighbor B.
2. From B, skip visited A and visit D.
3. From D, visit E before any later neighbor.
4. From E, visit C.
5. C's neighbors are already visited; backtrack until traversal ends. Answer. DFS preorder A,B,D,E,C.

BFS and DFS complexity

Definition. With adjacency lists, each vertex is discovered at most once and each edge is examined a constant number of times, giving O(V+E) time. With an adjacency matrix, scanning all possible neighbors costs O(V²), even for a sparse graph. Space includes the representation plus visited state and queue or stack.

Example. In a graph with 100 vertices and 150 edges, list traversal is proportional to about 250 stored items.

Exam point. Include the graph representation in the complexity analysis.

Traversal trees and parent arrays

Definition. A BFS or DFS traversal can record a parent for each discovered vertex, forming a spanning tree of the reachable component. The parent array supports path reconstruction by following parents back to the source. Unreachable vertices have no parent in a traversal from one source.