Graph Storage and Traversal

16 Nov 2024

1. What Is a Graph?

A graph consists of vertices and edges. A vertex can represent a place, person, or task, while an edge represents a relationship between two vertices. If an edge has a direction, the graph is directed: 1 → 2 does not mean that we can travel from 2 back to 1. If an edge has no direction, the graph is undirected, so 1 - 2 can be used in both directions.

Before using DFS or BFS on a graph, we first need a way to store the vertices adjacent to each vertex.

2. Two Common Graph Representations

An adjacency matrix uses a two-dimensional array edge. For example, edge[x][y] = 1 means that there is an edge from x to y. It is convenient for checking whether two vertices are directly connected, but it requires O(n²) space, so it is suitable for graphs with few vertices or many edges.

int edge[N][N];
edge[x][y] = 1;

An adjacency list keeps a list for every vertex. graph[x] stores all vertices that can be reached directly from x. It stores only existing edges, so it uses O(n + m) space, where n is the number of vertices and m is the number of edges. This makes it a better choice for most sparse graphs.

vector<int> graph[N];
graph[x].push_back(y);

For an undirected edge, add both directions: graph[x].push_back(y) and graph[y].push_back(x).

3. Example: Luogu P5318: Literature Search

The problem gives a directed graph. Starting from vertex 1, output every reachable vertex in DFS order and then in BFS order. To make the traversal order deterministic, sort the adjacency list of every vertex first.

DFS follows the current edge as deeply as possible. BFS uses a queue and visits vertices closer to the start first. Both traversals need a visited array to mark visited vertices and avoid repeated searches in a graph containing cycles.

#include <bits/stdc++.h>
using namespace std;

const int N = 100000 + 10;
vector<int> graph[N];
bool visited[N];
int n, m;

void dfs(int u) {
    visited[u] = true;
    cout << u << ' ';

    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

void bfs(int start) {
    memset(visited, false, sizeof visited);
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << ' ';

        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
    }

    for (int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    dfs(1);
    cout << '\n';
    bfs(1);
    return 0;
}

For example, with edges 1 → 2, 1 → 3, 2 → 4, and 3 → 4, DFS prints 1 2 4 3, while BFS prints 1 2 3 4.

With an adjacency list, each vertex and edge is processed at most once during one traversal. Therefore, both DFS and BFS run in O(n + m) time. The important part of a graph problem is often not choosing DFS or BFS first, but deciding whether edges are directed, how adjacency is stored, and when to mark a vertex as visited.

Graph Storage and Traversal

Related Posts