Tạo biểu đồ bằng Từ điển trong Python

Tệp cho biểu đồ như dưới đây -

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, lúc đầu, chúng tôi lấy tên của các đỉnh, sau đó đọc các cạnh để chèn vào danh sách.

Mã mẫu

from collections import defaultdict
defcreate_graph(filename):
   graph = defaultdict(list) #create dict with keys and corresponding lists
   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') #Remove the trailing new line character
   nodes = vert_Names.split('|') #Cut the vertex names
   for node in nodes: #For each vertex, create empty list
      graph[node] = []
   #Read edges from file and fill the lists
   for line in graph_file:
      line = line.rstrip('\n') #Remove the trailing new line character
      edge = line.split(',')
      graph[edge[0]].append(edge[1]) #The edge[0] is source and edge[1] is dest
   return graph
my_graph = create_graph('Graph_Input.txt')
for node in my_graph.keys(): #Print the graph
   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. Đầu tiên chúng ta sẽ xem cách lấy một đường dẫn từ đỉnh nguồn đến đỉnh đích. Mã đã cho là một phần của hoạt động này. Để thực thi nó, bạn phải tạo đồ thị bằng phương pháp trước đó.

Mã mẫu

#Function to find path from source to destination
defget_path(graph, src, dest, path = []):
   path = path + [src]
   if src == dest: #when destination is found, stop the process
      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 có thể từ Đỉnh nguồn đến Đỉnh đích. Mã đã cho là một phần của hoạt động này. Để thực thi nó, bạn phải tạo đồ thị bằng phương pháp trước đó.

Mã mẫu

#Function to find all paths from source to destination
defget_all_path(graph, src, dest, path = []):
   path = path + [src]
   if src == dest: #when destination is found, stop the process
      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 làm thế nào để có được đường đi ngắn nhất từ ​​đỉnh nguồn đến đỉnh đích. Mã đã cho là một phần của hoạt động này. Để thực thi nó, bạn phải tạo đồ thị bằng phương pháp trước đó.

Mã mẫu

#Function to find shortest path from source to destination
def get_shortest_path(graph, src, dest, path = []):
   path = path + [src]
   if src == dest: #when destination is found, stop the process
      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']