Python - Thuật toán đồ thị

Đồ thị là cấu trúc dữ liệu rất hữu ích trong việc giải quyết nhiều thách thức toán học quan trọng. Ví dụ cấu trúc liên kết mạng máy tính hoặc phân tích cấu trúc phân tử của các hợp chất hóa học. Chúng cũng được sử dụng trong giao thông thành phố hoặc lập kế hoạch tuyến đường và thậm chí trong ngôn ngữ của con người và ngữ pháp của họ. Tất cả các ứng dụng này đều có một thách thức chung là duyệt qua đồ thị bằng cách sử dụng các cạnh của chúng và đảm bảo rằng tất cả các nút của đồ thị đều được truy cập. Có hai phương pháp phổ biến được thiết lập để thực hiện việc truyền tải này được mô tả bên dưới.

Độ sâu Truyền tải đầu tiên:

Còn được gọi là tìm kiếm đầu tiên theo độ sâu (DFS), thuật toán này duyệt qua một đồ thị theo chuyển động của phường độ sâu và sử dụng một ngăn xếp để nhớ để lấy đỉnh tiếp theo để bắt đầu tìm kiếm, khi một điểm cuối xảy ra trong bất kỳ lần lặp nào. Chúng tôi triển khai DFS cho một biểu đồ trong python bằng cách sử dụng các kiểu dữ liệu đã đặt vì chúng cung cấp các chức năng cần thiết để theo dõi các nút đã truy cập và chưa truy cập.

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }


dfs(gdict, 'a')

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

a b d e c

Breadth First Traversal

Còn được gọi là tìm kiếm đầu tiên theo chiều rộng (BFS), thuật toán này đi qua chuyển động của phường theo chiều rộng của đồ thị và sử dụng một hàng đợi để nhớ lấy đỉnh tiếp theo để bắt đầu tìm kiếm, khi một điểm cuối xảy ra trong bất kỳ lần lặp nào. Vui lòng truy cập liên kết này trong trang web của chúng tôi để hiểu chi tiết về các bước BFS cho biểu đồ.

Chúng tôi triển khai BFS cho một đồ thị trong python bằng cách sử dụng cấu trúc dữ liệu hàng đợi đã thảo luận trước đó. Khi chúng ta tiếp tục truy cập các nút không được truy cập liền kề và tiếp tục thêm nó vào hàng đợi. Sau đó, chúng tôi bắt đầu xếp hàng chỉ nút còn lại không có nút nào chưa được truy cập. Chúng tôi dừng chương trình khi không có nút liền kề tiếp theo được truy cập.

import collections
class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
        seen, queue = set([startnode]), collections.deque([startnode])
        while queue:
            vertex = queue.popleft()
            marked(vertex)
            for node in graph[vertex]:
                if node not in seen:
                    seen.add(node)
                    queue.append(node)

def marked(n):
    print(n)

# The graph dictionary
gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }

bfs(gdict, "a")

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

a c b d e