An undirected graph connects nodes with edges that have no orientation, so each connection can be traversed in either direction. section 5.1.1
A simple Haskell representation captures the essential structure:
- Use a polymorphic node type so the graph can store different kinds of elements. section 5.1.1
- Ignore edge costs when every connection represents one equal step. section 5.1.1
- Store each connection as a pair in an adjacency list, represented by an associative list. section 5.1.1
- Recognize that checking edges, finding neighbors, and inserting edges may require scanning the whole list. section 5.1.1
Word ladders
A word-ladder program builds an undirected graph from a dictionary, with words as nodes and one-letter ladder steps as equal-cost edges, then searches for a shortest path. section 5.1.1
type Graph a = [(a,a)]
Inspect the compact adjacency-list type used to represent an undirected graph as connected node pairs. section 5.1.1
