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