Depth-First Search (DFS)

Depth-First Search (DFS) - Resources

bool used[N];       // true if the vertex was visited
vector<int> v[N];   // adjacency list

void dfs(int x) {
    used[x] = true; // mark the current vertex as visited
    for (int y : v[x]) {
        if (used[y]) {
            continue; // this vertex was already visited
        }
        dfs(y);
    }
}

int timer = 0;      // global timer
int tin[N];         // entry time of vertex x
int tout[N];        // exit time of vertex x
bool used[N];       // true if vertex x was visited
vector<int> v[N];   // adjacency list

void dfs(int x) {
    used[x] = true;
    tin[x] = ++timer; // time when we enter x

    for (int y : v[x]) {
        if (used[y]) { // already visited vertex
            if (tout[y] == 0) { 
                // back edge: y is still active in recursion
            } else if (tin[x] < tin[y]) {
                // forward edge
            } else {
                // cross edge
            }
            continue;
        }

        // (x, y) is a tree edge
        dfs(y);
    }

    tout[x] = ++timer; // time when we exit x
}

Depth-First Search (DFS)

Introduction

Classification of Graph Edges

1. If vertex $y$ has not been visited yet

External Problems

2. If vertex $y$ has already been visited

Implementation

Depth-First Search (DFS)

Introduction

Classification of Graph Edges

1. If vertex yyy has not been visited yet

External Problems

2. If vertex yyy has already been visited

Implementation

1. If vertex $y$ has not been visited yet

2. If vertex $y$ has already been visited