Graph

A graph is a data structure representing a collection of objects and the relationships between them. Formally, a graph $G$ is a pair $(V, E)$ where:

$V$ is a set of vertices (also called nodes).
$E$ is a collection of edges, each connecting a pair of vertices.

Graphs are the most general non-linear structure — trees, lists, and grids are all special cases of graphs. Used for everything from social networks (people = vertices, friendships = edges) to road maps (intersections, roads), web pages (URLs, hyperlinks), and circuit topology.

Example

Airports as a graph: each vertex stores a 3-letter airport code; each edge represents a flight route, possibly weighted with mileage.

Types

Undirected graphs

Edges have no direction — an edge between vertices $u$ and $v$ is just an unordered pair ${u, v}$ . If the graph has ${1, 2}$ as an edge, you can traverse from 1 to 2 or 2 to 1.

Directed graphs (digraphs)

Edges have direction — represented as ordered pairs $(u, v)$ where the edge goes from $u$ to $v$ . If the graph has $(1, 2)$ as an edge, you can go 1 → 2 but not necessarily 2 → 1.

If both $(3, 4)$ and $(4, 3)$ are edges in a directed graph, you can travel either way.

Weighted graphs

Each edge has a numerical weight (cost, distance, capacity, time). Used for shortest-path problems, network flow, etc. See Dijkstra’s algorithm.

Connectivity

Undirected graph is connected if there’s a path between every pair of vertices.
Directed graph is strongly connected if there’s a directed path from every vertex to every other vertex.
Directed graph is weakly connected if, ignoring edge directions, it’s connected (the underlying undirected graph is connected).

Representation

Two main ways to store a graph in memory:

Adjacency matrix — a $V \times V$ matrix with entries indicating edges. $O (V^{2})$ space, $O (1)$ edge lookup. Best for dense graphs.
Adjacency list — for each vertex, a list of its neighbors. $O (V + E)$ space, $O (de g)$ edge lookup. Best for sparse graphs.

Most real-world graphs are sparse — social networks, road graphs, web graphs all have $E ≪ V^{2}$ . So adjacency lists dominate practical use. The choice of representation affects algorithm complexity: BFS and DFS run in $O (V^{2})$ on a matrix but $O (V + E)$ on a list.

Construction

void create_graph() {
    int n, adj[100][100];
    int count, max_edge, origin, destin;
    
    printf("Enter number of vertices: ");
    scanf("%d", &n);
    
    max_edge = n * (n - 1);
    for (count = 1; count <= max_edge; count++) {
        printf("Enter edge %d (-1 -1 to quit): ", count);
        scanf("%d %d", &origin, &destin);
        if (origin == -1 && destin == -1) break;
        if (origin >= n || destin >= n || origin < 0 || destin < 0) {
            printf("Invalid edge!\n");
            count--;
        } else {
            adj[origin][destin] = 1;
        }
    }
}

This builds an adjacency matrix interactively. The matrix adj[i][j] = 1 indicates an edge from $i$ to $j$ .

Operations

The fundamental graph operations:

Traversal: visit every reachable vertex from a starting point. See Breadth-first search and Depth-first search.
Shortest path: find the cheapest route between two vertices. See Dijkstra’s algorithm.
Spanning tree: extract a tree that connects all vertices with minimum total edge weight. See Prim’s algorithm.
Topological sort, strongly connected components, cycle detection — graph-specific algorithms.

For traversal, see the BFS/DFS notes. For weighted-graph shortest paths, see Dijkstra. For minimum spanning trees, see Prim.

Idriss Rami — Notes

Explorer