A graph is a data structure for modeling relationships rather than sequences. It contains vertices, also called nodes, connected by edges, also called links. Graphs support practical models of social networks, maps, computer networks, and biological relationships. section 1.0 section 1.3
Classify a graph by the properties that determine which operations and algorithms apply:
- Directed edges point from one vertex to another; undirected edges represent two-way relationships. section 1.3
- Cyclic graphs contain a route that returns to its starting vertex; acyclic graphs contain no cycles. section 1.3
- Weighted edges carry values such as travel time; unweighted edges treat every connection equally. section 1.3
- Connected graphs provide a path between every vertex pair; disconnected graphs contain unreachable portions. section 1.3
Represent a graph with an adjacency matrix or adjacency list. A matrix stores whether each vertex pair has an edge, giving O(1) edge lookup but O(v²) space. A list stores each vertex’s neighboring edges, using O(v + e) space and O(d) edge lookup, where d is the vertex degree. section 1.3
Inspect the visual graph example alongside its in-memory representation. section 1.3
Algorithms that exploit graph properties
Use breadth-first search to find shortest paths in unweighted graphs, Floyd–Warshall to find shortest paths between all pairs in weighted graphs, and topological sort to order vertices in a directed acyclic graph. These algorithms depend on graph characteristics rather than treating them as incidental labels. section 1.4
























