DFS DFS
Tìm kiếm theo chiều sâu ( DFS) là một trong những thuật toán chính trên biểu đồ. Thuật toán chạy trong O(N + M).
Thuật toán
Để bắt đầu, chúng tôi bắt đầu từ trên cùng, xem xét các phần tử con của phần trên cùng này và nếu chúng tôi chưa bao giờ nhập chúng, thì chúng tôi bắt đầu DFS từ chúng.
|
DFS DFS
Tìm kiếm theo chiều sâu ( DFS) là một trong những thuật toán chính trên biểu đồ. Thuật toán chạy trong O(N + M).
Thuật toán
Để bắt đầu, chúng tôi bắt đầu từ trên cùng, xem xét các phần tử con của phần trên cùng này và nếu chúng tôi chưa bao giờ nhập chúng, thì chúng tôi bắt đầu DFS từ chúng.
|
Biểu đồ hai phía
Biểu đồ hai phía - một biểu đồ có các đỉnh có thể được chia thành hai tập hợp sao cho mỗi cạnh kết nối các các đỉnh từ các tập hợp khác nhau.
Thông thường, trong ngữ cảnh của đồ thị hai phía, khái niệm màu sắc đỉnh được sử dụng. Việc chia một biểu đồ thành hai phần được gọi là tô màu các đỉnh của nó bằng hai màu khác nhau. Mỗi cạnh phải nối các đỉnh có màu khác nhau.
DFS.
Thuật toán
Chúng ta bắt đầu vẽ từ một đỉnh tùy ý và tô màu tùy ý.
Khi đi dọc theo mỗi cạnh, hãy sơn đỉnh tiếp theo bằng màu đối diện.
Nếu trong khi duyệt qua các đỉnh lân cận, chúng ta tìm thấy một đỉnh đã được sơn cùng màu với đỉnh hiện tại, thì đó là một chu trình lẻ trong đồ thị, nghĩa là nó không phải là hai cạnh.
|
Thuật toán có thể được mô tả như sau:
Cho đồ thị có hướng có n đỉnh và m cạnh. Cần phải đánh số lại các đỉnh của nó sao cho mỗi cạnh dẫn từ đỉnh có số thấp hơn đến đỉnh có số cao hơn.
Nói cách khác, cần phải tìm một hoán vị của các đỉnh (thứ tự tô pô) tương ứng với thứ tự đã cho của tất cả các cạnh của đồ thị.
Chúng tôi sẽ sử dụng tìm kiếm theo chiều sâu (dfs(v))
Nếu chúng ta thêm đỉnh của mình vào đầu danh sách tại thời điểm thoát khỏi \(dfs(v)\) , thì cuối cùng trong danh sách này, bạn sẽ có được một kiểu sắp xếp tô pô.
Do đó, sắp xếp tô pô mong muốn — điều này được sắp xếp theo thứ tự thời gian thoát giảm dần.
|