使用Python字典生成圖

---

可以使用Python中的字典來實現圖。在字典中，每個鍵將是頂點，其值將是連線頂點的列表。因此，整個結構將類似於圖G(V, E)的鄰接表。

我們可以使用基本的字典物件，但我們使用的是defaultdict。它有一些附加功能。它有一個額外的可寫例項變數。

我們提供了一個文字檔案，其中包含頂點的數量、邊的數量、頂點的名稱以及邊的列表。對於無向圖，我們提供兩條邊，例如(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']

現在我們將看到如何從源頂點到目標頂點獲取所有可能的路徑。給定的程式碼是此操作的一部分。要執行它，您必須使用先前的方法生成圖。

示例程式碼

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