Duyệt theo chiều sâu (DFS) cho Đồ thị

Giới thiệu

Depth-First Search (DFS) là thuật toán duyệt đồ thị. Từ đỉnh bắt đầu, đi sâu vào đỉnh kề trước, duyệt hết nhánh đó rồi backtrack.

Cài đặt lặp dùng stack; đệ quy dùng stack nội bộ.

Đầu vào và Đầu ra

Đầu vào: Ma trận kề:
  A B C D E F
A 0 1 1 1 0 0
B 1 0 0 1 1 0
C 1 0 0 1 0 1
D 1 1 1 0 1 1
E 0 1 0 1 0 1
F 0 0 1 1 1 0
Đầu ra: DFS Traversal: C F E B D A

Thuật toán

dfs(vertices, start)

Đầu vào: Danh sách đỉnh, đỉnh bắt đầu.

Đầu ra: Duyệt tất cả nút trong đồ thị.

Begin
  đánh dấu tất cả nút chưa thăm
  push start vào stack
  trong khi stack không rỗng làm:
    pop phần tử thành u
    hiển thị u
    nếu u chưa thăm thì
      đánh dấu u đã thăm
      với mọi nút i kề u làm:
        nếu i chưa thăm thì push i vào stack, đánh dấu i đã thăm
      done
  done
End

Ví dụ (C++)

#include <iostream>
#include <stack>
using namespace std;
#define NODE 6

typedef struct node { int val; int state; } node;

int graph[NODE][NODE] = {
  {0, 1, 1, 1, 0, 0},
  {1, 0, 0, 1, 1, 0},
  {1, 0, 0, 1, 0, 1},
  {1, 1, 1, 0, 1, 1},
  {0, 1, 0, 1, 0, 1},
  {0, 0, 1, 1, 1, 0}
};

void dfs(node *vertex, node start) {
  node u;
  stack<node> myStack;
  for(int i = 0; i < NODE; i++) vertex[i].state = 0;
  myStack.push(start);
  while(!myStack.empty()) {
    u = myStack.top(); myStack.pop();
    cout << char(u.val + 'A') << " ";
    if(u.state != 1) {
      u.state = 1; vertex[u.val].state = 1;
      for(int i = 0; i < NODE; i++) {
        if(graph[i][u.val]) {
          if(vertex[i].state == 0) {
            myStack.push(vertex[i]);
            vertex[i].state = 1;
          }
        }
      }
    }
  }
}

int main() {
  node vertices[NODE], start;
  char s = 'C';
  for(int i = 0; i < NODE; i++) vertices[i].val = i;
  start.val = s - 'A';
  cout << "DFS Traversal: ";
  dfs(vertices, start);
  cout << endl;
}

Kết quả đầu ra

DFS Traversal: C F E B D A