Introduction to graphs

This lesson defines a graph as a network of vertices and edges, sketches directed and undirected pictures, and contrasts graphs with linear lists and trees. Later pages cover terminology, representations, traversals, shortest paths, and classic algorithms in C.

1) What is a graph?

A graph G = (V, E) consists of a finite set of vertices (or nodes) V and a set of edges E. Each edge connects two vertices (the same vertex twice is allowed in some definitions as a self-loop). Edges may be undirected (unordered pairs) or directed (ordered pairs, often drawn as arrows).

Unlike a tree, a graph may contain cycles and multiple paths between the same pair of vertices. That flexibility is why graphs model roads, social networks, task dependencies, and state spaces in puzzles.

Schematic: a small undirected graph

Three vertices; edges have no direction (lines, not arrows):

       A ----- B
        \     /
         \   /
          \ /
           C

2) Core ideas

• Neighbor — A vertex adjacent along an edge (out-neighbors / in-neighbors matter for directed graphs).
• Degree — Number of incident edges at a vertex (in directed graphs, split into in-degree and out-degree).
• Path — A sequence of vertices where consecutive pairs are edges; simple path repeats no vertex.
• Cycle — A path that starts and ends at the same vertex (length ≥ 1 depending on definition).
• Connected — In an undirected graph, every pair of vertices is linked by some path.

Precise wording varies by author; Graph terminology fixes vocabulary for the rest of this tutorial.

3) List vs tree vs graph

Graphs are the most general of the three: lists are degenerate paths; trees are connected graphs without cycles plus (often) a root.

Every tree is a graph, but most graphs are not trees. For a focused contrast with hierarchies, see Graph versus tree.

4) Where graphs show up in this tutorial

Upcoming lessons cover adjacency matrix and list representations, BFS and DFS, minimum spanning trees, shortest paths, topological order on DAGs, union–find, SCCs, and more—implemented and reasoned about in C. Nail this introduction first; then Graph types and Graph representation turn the pictures into storage layouts.