Picture a friendship network: each person is a point, and a connection between two people shows a relationship. In a graph, that point is called a vertex, or node. Vertices represent distinct entities; edges connect pairs of vertices. section 13.2 section 13.3
An edge has two endpoints: a source vertex and a destination vertex. In a directed graph, you can follow the edge only from source to destination; an undirected edge works both ways. This matters when choosing a model: following someone need not be mutual, while a friendship can be represented as a two-way connection. section 13.2 section 13.4
A small friendship graph
Suppose the first two animals in a social network are a campaigner and her friend. Represent each animal as a vertex and their friendship as an edge. Adding animals adds vertices; recording their friendships adds edges. section 13.3
G = ([v1, v2, v3, v4], [(v1,v2),(v1,v3),(v2,v4)])
The listing writes a graph as a collection of vertices paired with a collection of edges. Each edge is shown as a pair of vertex names. section 13.2
“Node” also appears in other data structures, but its links have a different job there. A linked-list node stores a value and a link to the next node. A tree node stores a value and links to children. A graph vertex is an entity in a set of vertices; edges describe its relationships with other vertices. section 6.6 section 11.2 section 13.2
Once vertices and edges are identified, you can ask whether vertices are connected or seek a path between them. Breadth-first search finds paths with the fewest edges from a starting vertex; depth-first search follows paths to their ends and can help check graph properties. section 13.16
