An edge is a connection between two vertices, or nodes, in a graph. It may be directed, as when one person follows another, or undirected, as with a mutual friendship. The direction matters: an edge from A to B does not by itself establish an edge from B to A. section 1.3
An edge can carry different information depending on the problem:
- A weighted edge has an associated value, such as travel time between cities; an unweighted edge does not distinguish connections by weight. section 1.3
- A dependency edge links tasks in a directed acyclic graph. Incoming edges contribute to a vertex’s in-degree, which topological sort uses to find an execution order. section 1.4.1
- A flow-network edge has a capacity: the most flow it can carry. A path can carry additional flow only when every edge on it has capacity available. section 1.4.2
Finding a route for more flow
Suppose water travels from a reservoir toward homes through pipes with different capacities. A connected route is not necessarily an augmenting path: if one pipe has no capacity left, no additional water can pass along that entire route. The same constraint applies to bandwidth-limited connections in a data network. section 1.4.2
How edges are stored affects the cost of finding one. An adjacency matrix records whether an edge from vertex i to vertex j exists, giving O(1) lookup but using O(v²) space. An adjacency list stores each vertex’s edges, using O(v + e) space but taking O(d) to search a vertex’s list, where d is its degree. Lists avoid much of a matrix’s wasted space in sparse graphs; matrices offer faster edge lookup in dense ones. section 1.3



















