Graphs and Graph Traversal

A graph is a data structure consisting of a set of vertices, or nodes, connected by a set of edges, and it is the natural way to model relationships between entities that are not strictly hierarchical, from social networks and road maps to web links and computer networks. In a directed graph, or digraph, each edge points from one vertex to another in a single direction, reflecting an asymmetric relationship such as "follows" on a social platform or a one-way street. In an undirected graph, edges have no direction and represent a mutual relationship, such as a friendship or a two-way road. Edges may also be weighted, carrying a numeric cost such as distance, time, or price, or unweighted, indicating only that a connection exists. Key terms used to describe graphs include a vertex's degree, the number of edges attached to it; a path, a sequence of edges connecting a sequence of vertices; a cycle, a path that returns to its starting vertex; and connectivity, whether a route exists between every pair of vertices.