สร้างกราฟโดยใช้พจนานุกรมใน Python

กราฟสามารถนำมาใช้โดยใช้พจนานุกรมในภาษาไพทอน ในพจนานุกรม แต่ละคีย์จะเป็นจุดยอด และตามค่า จะมีรายการของจุดยอดที่เชื่อมต่อ ดังนั้นโครงสร้างทั้งหมดจะดูเหมือนรายการ Adjacency ของกราฟ G(V, E)

เราสามารถใช้วัตถุพจนานุกรมพื้นฐานได้ แต่เรากำลังใช้ dict เริ่มต้น มีคุณสมบัติเพิ่มเติมบางอย่าง มีตัวแปรอินสแตนซ์ที่เขียนได้เพิ่มเติมหนึ่งตัว

เรากำลังจัดเตรียมไฟล์ข้อความ ซึ่งประกอบด้วยจำนวนของจุดยอด จำนวนขอบ ชื่อของจุดยอด และรายการของขอบ สำหรับกราฟแบบไม่บอกทิศทาง เราจะให้สองขอบเช่น (u,v) และ (v,u)

เรากำลังใช้กราฟนี้ในตัวอย่างนี้

ไฟล์สำหรับกราฟมีลักษณะดังนี้ -

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

ในตอนแรก เราจะเอาชื่อจุดยอด แล้วอ่านขอบเพื่อแทรกลงในรายการ

โค้ดตัวอย่าง

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]))

ผลลัพธ์

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

ตอนนี้เราจะเห็นการดำเนินการพื้นฐานบางอย่างในกราฟที่กำหนด G(V,E) ขั้นแรกเราจะดูวิธีรับเส้นทางจากจุดยอดต้นทางไปยังจุดยอดปลายทาง รหัสที่กำหนดเป็นส่วนหนึ่งของการดำเนินการนี้ ในการดำเนินการ คุณต้องสร้างกราฟโดยใช้วิธีก่อนหน้า

โค้ดตัวอย่าง

#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))

ผลลัพธ์

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

ตอนนี้เราจะมาดูวิธีรับเส้นทางที่เป็นไปได้ทั้งหมดจาก Source Vertex ไปยัง Destination Vertex รหัสที่กำหนดเป็นส่วนหนึ่งของการดำเนินการนี้ ในการดำเนินการ คุณต้องสร้างกราฟโดยใช้วิธีก่อนหน้า

โค้ดตัวอย่าง

#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)

ผลลัพธ์

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']

สุดท้าย เราจะมาดูวิธีหาเส้นทางที่สั้นที่สุดจากต้นทางไปยังจุดยอดปลายทาง รหัสที่กำหนดเป็นส่วนหนึ่งของการดำเนินการนี้ ในการดำเนินการ คุณต้องสร้างกราฟโดยใช้วิธีก่อนหน้า

โค้ดตัวอย่าง

#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))

ผลลัพธ์

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