Tạo đồ thị sử dụng Dictionary trong Python

Đồ thị có thể được triển khai bằng Dictionary trong Python. Trong từ điển, mỗi khóa sẽ là các đỉnh, và làm giá trị, nó giữ một danh sách các đỉnh kết nối. Vì vậy toàn bộ cấu trúc sẽ trông như danh sách kề của đồ thị G(V, E).

Chúng ta có thể sử dụng đối tượng từ điển cơ bản, nhưng chúng ta đang dùng defaultdict. Nó có một số tính năng bổ sung. Nó có một biến thể hiện ghi thêm.

Chúng ta cung cấp một tệp văn bản, chứa số đỉnh, số cạnh, tên các đỉnh và danh sách cạnh. Đối với đồ thị vô hướng, chúng ta cung cấp hai cạnh như (u,v) và (v,u).

Chúng ta đang sử dụng đồ thị này trong ví dụ.

Tệp cho đồ thị như sau:

Graph_Input.txt

6 8
A|B|C|D|E|F
A,B
B,A
A,C
C,A
B,D
D,B
B,E
E,B
C,E
E,C
D,E
E,D
D,F
F,D
E,F
F,E

Vì vậy trước tiên, chúng ta lấy tên các đỉnh, sau đó đọc các cạnh để chèn vào danh sách.

Mã ví dụ

from collections import defaultdict

def create_graph(filename):
    graph = defaultdict(list)  # tạo dict với khóa và danh sách tương ứng
    with open(filename, 'r') as graph_file:
        vertex = int(graph_file.readline())
        edges = int(graph_file.readline())
        vert_Names = graph_file.readline()
        vert_Names = vert_Names.rstrip('\n')  # Xóa ký tự xuống dòng cuối
        nodes = vert_Names.split('|')  # Tách tên đỉnh
        for node in nodes:
            # Với mỗi đỉnh, tạo danh sách rỗng
            graph[node] = []
        # Đọc cạnh từ tệp và điền vào danh sách
        for line in graph_file:
            line = line.rstrip('\n')
            edge = line.split(',')
            graph[edge[0]].append(edge[1])  # edge[0] là nguồn, edge[1] là đích
    return graph

my_graph = create_graph('Graph_Input.txt')
for node in my_graph.keys():
    # In đồ thị
    print(node + ': ' + str(my_graph[node]))

Đầu ra

A: ['B', 'C']
B: ['A', 'D', 'E']
C: ['A', 'E']
D: ['B', 'E', 'F']
E: ['B', 'C', 'D', 'F']
F: ['D', 'E']

Bây giờ chúng ta sẽ xem một số phép toán cơ bản trên đồ thị G(V,E) cho trước. Trước tiên chúng ta sẽ xem cách lấy đường đi từ đỉnh nguồn đến đỉnh đích. Mã cho trước là một phần của phép toán này. Để thực thi nó, bạn phải tạo đồ thị bằng phương pháp trước.

Mã ví dụ

# Hàm tìm đường đi từ nguồn đến đích
def get_path(graph, src, dest, path=[]):
    path = path + [src]
    if src == dest:
        # khi tìm thấy đích, dừng quá trình
        return path
    for vertex in graph[src]:
        if vertex not in path:
            path_new = get_path(graph, vertex, dest, path)
            if path_new:
                return path_new
    return None

my_graph = create_graph('Graph_Input.txt')
path = get_path(my_graph, 'A', 'C')
print('Path From Node A to C: ' + str(path))

Đầu ra

Path From Node A to C: ['A', 'B', 'D', 'E', 'C']

Bây giờ chúng ta sẽ xem cách lấy tất cả các đường đi có thể từ Đỉnh Nguồn đến Đỉnh Đích. Mã cho trước là một phần của phép toán này. Để thực thi nó, bạn phải tạo đồ thị bằng phương pháp trước.

Mã ví dụ

# Hàm tìm tất cả đường đi từ nguồn đến đích
def get_all_path(graph, src, dest, path=[]):
    path = path + [src]
    if src == dest:
        # khi tìm thấy đích, dừng quá trình
        return [path]
    paths = []
    new_path_list = []
    for vertex in graph[src]:
        if vertex not in path:
            new_path_list = get_all_path(graph, vertex, dest, path)
            for new_path in new_path_list:
                paths.append(new_path)
    return paths

my_graph = create_graph('Graph_Input.txt')
paths = get_all_path(my_graph, 'A', 'C')
print('All Paths From Node A to C: ')
for path in paths:
    print(path)

Đầu ra

All Paths From Node A to C:
['A', 'B', 'D', 'E', 'C']
['A', 'B', 'D', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'E', 'C']
['A', 'C']

Cuối cùng, chúng ta sẽ xem cách lấy đường đi ngắn nhất từ nguồn đến đỉnh đích. Mã cho trước là một phần của phép toán này. Để thực thi nó, bạn phải tạo đồ thị bằng phương pháp trước.

Mã ví dụ

# Hàm tìm đường đi ngắn nhất từ nguồn đến đích
def get_shortest_path(graph, src, dest, path=[]):
    path = path + [src]
    if src == dest:
        # khi tìm thấy đích, dừng quá trình
        return path
    short = None
    for vertex in graph[src]:
        if vertex not in path:
            new_path_list = get_shortest_path(graph, vertex, dest, path)
            if new_path_list:
                if not short or len(new_path_list) < len(short):
                    short = new_path_list
    return short

my_graph = create_graph('Graph_Input.txt')
path = get_shortest_path(my_graph, 'A', 'C')
print('Shortest Paths From Node A to C: ' + str(path))

Đầu ra

Shortest Paths From Node A to C: ['A', 'C']