liveBook · Manning

Undirected graph

As explained in Algorithms Every Programmer Should Know

An undirected graph is a graph whose edges represent mutual connections without orientation.

An undirected graph represents mutual connections: if node A connects to node B, B connects back to A. In an adjacency list, each node must list the other as a neighbor. section 1.4.5

A mutual connection

A friendship is a two-way connection: if A and B are friends, both appear in each other’s neighbor lists. Unlike a directed graph, neither node needs to follow an arrow. section 1.4.5

BFS and DFS can travel either way along an undirected edge. In graphs with cycles, traversals use a visited set to avoid revisiting nodes indefinitely. section 1.5

Figure 1.13 Two structural variations of a graph. Left: An Undirected Graph maps mutual, bidirectional connections. Right: A Directed Graph restricts travel paths to be unidirectional, forcing algorithms to explore a path based on direction.

Compare mutual connections in an undirected graph with the one-way paths of a directed graph. section 1.4.5

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines mutual edges and reciprocal adjacency-list entries, then contrasts traversal direction with directed graphs.
Examples
Uses friendship as a mutual-connection example and contrasts it with one-way social-media follows.
What you can do after
Understand how mutual edges are represented and how BFS or DFS can move in either direction along them.
How it connects
Connects graph representation to adjacency lists, adjacency matrices, directed graphs, BFS, and DFS.

Also explained in

Compare how 6 books explain undirected graph →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.