Algorithm - DFS

Course

可以參考我做的課程簡報：

BFS & DFS

Depth-First Search DFS 深度優先搜尋

• 不斷找出尚未遍歷的點當作起點
  • 把起點塞入 stack
  • 重複以下步驟，直到 stack 裡沒有東西為止：
    1. 從 stack 中取出一點
    2. 找出與此點相鄰的點、且尚未遍歷的點，並將這些點依序塞入 stack

Example

DFS - stack

int main(){

    bool visited[12+5];
    bool M[12+5][12+5];

    stack<int> st;
    for(int i = 0; i <= 12; i++){
        visited[i] = false;
    }

    int parent, child;
    while(cin >> parent >> child){
        M[parent][child] = true;
    }

    for(int k = 0; k <= 12; k++){

        if(!visited[k]){
            st.push(k);
            visited[k] = true;
        }

        while(!st.empty()){
            int i = st.top();
            st.pop();

            for(int j = 0; j <= 12; j++){
                if(M[i][j] && !visited[j]){
                    st.push(j);
                    visited[j] = true;
                }
            }
        }
    }
}

DFS - recursive

bool visited[12+5];
bool M[12+5][12+5];

void dfs(int i){
    if(!visited[i]){
        return;
    }
    visited[i] = true;

    for(int j = 0; j <= 12; j++){
        if(M[i][j]){
            dfs(j);
        }
    }
}

int main(){

    for(int i = 0; i <= 12; i++){
        visited[i] = false;
    }

    int parent, child;
    while(cin >> parent >> child){
        M[parent][child] = true;
    }

    for(int k = 0; k <= 12; k++){
        dfs(k);
    }
}

UVA Problem

UVA 00572 - Oil Deposits UVA 10189 - Minesweeper UVA 00441 - Lotto UVA 00167 - The Sultans Successors UVA 00216 - Getting in Line