English edition note: The graph-set notation in the C-labelled block is illustrative mathematics, not compilable C. The original graph illustration and its source path are retained.

#Graphs

#What is a graph?

A data structure that represents relationships between connected objects.

#Definition of a graph

A data structure consisting of vertices and edges. Graph G = (V, E)

• V : The set of vertices (a finite set)
• E : The set of edges (represented as pairs of vertices)

#Types of graphs

1. Undirected Graph
   • A graph whose connections between vertices have no direction.
2. Directed Graph
   • A graph whose connections between vertices have a direction.
3. Weighted Graph & Network
   • A graph with weights (such as costs) assigned to its edges.
   • Example: vertex = city, edge = road, weight = distance

#Example graph representations

//Represent undirected edges with ()
V(G1) = {0, 1, 2, 3}, E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
V(G2) = {0, 1, 2, 3}, E(G2) = {(0, 1), (0, 2)}
//Represent directed edges with <>
V(G3) = {0, 1, 2}, E(G3) = {<0, 1>, <1, 0>, <1, 2>} 

Examples

• Road networks
• Networks
• Subway maps