Đồ thị (Graphs) và các thuật toán duyệt

Phần này giới thiệu cấu trúc dữ liệu đồ thị và các thuật toán duyệt của nó.

Đồ thị là cấu trúc dữ liệu phi tuyến tính, bao gồm các nút (nodes) và các cạnh kết nối (edges). Cạnh có thể có hướng hoặc vô hướng. Đồ thị biểu diễn là G(V, E). Ví dụ: G({A,B,C,D,E}, {(A,B), (B,D), (D,E), (B,C), (C,A)})

Đồ thị có hai loại thuật toán duyệt: Breadth First Search (BFS) và Depth First Search (DFS).

Breadth First Search (BFS) - Tìm kiếm theo chiều rộng

BFS là thuật toán dùng để thăm tất cả nút của một đồ thị cho trước. Chọn một nút, sau đó thăm lần lượt tất cả nút kề. Sau khi xong các đỉnh kề, chuyển sang đỉnh khác và thăm các đỉnh kề của nó.

Thuật toán BFS

bfs(vertices, start)
Input: Danh sách đỉnh, đỉnh bắt đầu.
Output: Duyệt tất cả nút nếu đồ thị liên thông.
Begin
    define empty queue que
    đánh dấu tất cả nút là unvisited
    add start vào que
    while que not empty:
        delete item from que -> u
        display u
        for all vertices i adjacent with u:
            if vertices[i] unvisited:
                mark vertices[i] temporarily visited
                add v into queue
        mark u as completely visited
    done
End

Depth First Search (DFS) - Tìm kiếm theo chiều sâu

DFS là thuật toán duyệt đồ thị. Cho một đỉnh bắt đầu, khi tìm thấy đỉnh kề, nó chuyển đến đỉnh kề đó trước và tiếp tục duyệt theo cùng cách đó.

Thuật toán DFS

dfs(vertices, start)
Input: Danh sách tất cả đỉnh, nút bắt đầu.
Output: Duyệt tất cả nút trong đồ thị.
Begin
    initially make state unvisited for all nodes
    push start into stack
    while stack not empty:
        pop element from stack -> u
        display u
        if u not visited:
            mark u as visited
            for all nodes i connected to u:
                if ith vertex unvisited:
                    push ith vertex into stack
                    mark ith vertex as visited
        done
    done
End