Ҷустуҷӯи амиқ-аввал (DFS)

Ҷустуҷӯи амиқ-аввал (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
}

Ҷустуҷӯи амиқ-аввал (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

Ҷустуҷӯи амиқ-аввал (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