Hướng dẫn how do you make a graph in python data structure? - làm thế nào để bạn tạo một biểu đồ trong cấu trúc dữ liệu python?

Cảnh báo

Trang này ở đây vì lý do lịch sử và nó có thể chứa thông tin lỗi thời hoặc không chính xác.

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.
All rights reserved.
Licensed under the PSF license.

Có các tài liệu đáng kể trên các thuật toán đồ thị, là một phần quan trọng của toán học riêng biệt. Đồ thị cũng có nhiều sử dụng thực tế trong các thuật toán máy tính. Các ví dụ rõ ràng có thể được tìm thấy trong việc quản lý các mạng, nhưng các ví dụ rất nhiều trong nhiều lĩnh vực khác. Chẳng hạn, các mối quan hệ caller-callee trong một chương trình máy tính có thể được xem như một biểu đồ (trong đó các chu kỳ biểu thị các nút đệ quy và các nút không thể truy cập đại diện cho mã chết).

Rất ít ngôn ngữ lập trình cung cấp hỗ trợ trực tiếp cho các biểu đồ dưới dạng kiểu dữ liệu và Python cũng không ngoại lệ. Tuy nhiên, đồ thị dễ dàng được xây dựng từ danh sách và từ điển. Chẳng hạn, đây là một biểu đồ đơn giản (tôi không thể sử dụng các bản vẽ trong các cột này, vì vậy tôi viết ra các cung của biểu đồ):

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

    graph = {'A': ['B', 'C'],
             'B': ['C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F'],
             'F': ['C']}

Hãy viết một hàm đơn giản để xác định đường dẫn giữa hai nút. Nó lấy một biểu đồ và các nút bắt đầu và kết thúc làm đối số. Nó sẽ trả về một danh sách các nút (bao gồm các nút bắt đầu và kết thúc) bao gồm đường dẫn. Khi không có đường dẫn có thể được tìm thấy, nó không trả lại. Cùng một nút sẽ không xảy ra nhiều hơn một lần trên đường dẫn được trả về (nghĩa là nó sẽ không chứa các chu kỳ). Thuật toán sử dụng một kỹ thuật quan trọng được gọi là quay lại: nó lần lượt thử từng khả năng cho đến khi tìm thấy một giải pháp.

    def find_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if not graph.has_key(start):
            return None
        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath: return newpath
        return None

    >>> find_path(graph, 'A', 'D')
    ['A', 'B', 'C', 'D']
    >>>

Lưu ý rằng trong khi người dùng gọi

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

Thật đơn giản để thay đổi chức năng này để trả về danh sách tất cả các đường dẫn (không có chu kỳ) thay vì đường dẫn đầu tiên mà nó tìm thấy:

    def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if not graph.has_key(start):
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths

    >>> find_all_paths(graph, 'A', 'D')
    [['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]
    >>>

    def find_shortest_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if not graph.has_key(start):
            return None
        shortest = None
        for node in graph[start]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

    >>> find_shortest_path(graph, 'A', 'D')
    ['A', 'C', 'D']
    >>>

CẬP NHẬT: Eryk Kopczyński chỉ ra rằng các chức năng này không tối ưu. Ngược lại, "Chương trình này chạy trong thời gian theo cấp số nhân, trong khi Find_Shortest_Path có thể được thực hiện trong thời gian tuyến tính bằng cách sử dụng BFS [Tìm kiếm đầu tiên trên chiều rộng]. Hơn nữa, BFS tuyến tính đơn giản hơn:" Eryk Kopczyński pointed out that these functions are not optimal. To the contrary, "this program runs in exponential time, while find_shortest_path can be done in linear time using BFS [Breadth First Search]. Furthermore a linear BFS is simpler:"

    # Code by Eryk Kopczyński
    def find_shortest_path(graph, start, end):
        dist = {start: [start]}
        q = deque(start)
        while len(q):
            at = q.popleft()
            for next in graph[at]:
                if next not in dist:
                    dist[next] = [dist[at], next]
                    q.append(next)
        return dist.get(end)

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

    A -> B
    A -> C
    B -> C
    B -> D
    C -> D
    D -> C
    E -> F
    F -> C

Một biến thể khác sẽ là thêm nhiều trừu tượng dữ liệu: tạo một lớp để biểu thị các biểu đồ, có các phương thức thực hiện các thuật toán khác nhau. Mặc dù điều này hấp dẫn mong muốn lập trình có cấu trúc, nhưng nó không làm cho mã hiệu quả hơn (ngược lại). Nó giúp việc thêm các nhãn khác nhau vào các nút hoặc cung dễ dàng hơn và thêm các thuật toán đưa các nhãn đó vào tài khoản (ví dụ: để tìm tuyến đường ngắn nhất giữa hai thành phố trên bản đồ). Điều này cũng vậy, sẽ là chủ đề của một cột khác.