그래프는 Python의 사전을 사용하여 구현할 수 있습니다. 사전에서 각 키는 정점이 되며 값으로 연결된 정점 목록을 보유합니다. 따라서 전체 구조는 그래프 G(V, E)의 인접 목록처럼 보일 것입니다.
기본 사전 객체를 사용할 수 있지만 기본 사전을 사용하고 있습니다. 몇 가지 추가 기능이 있습니다. 쓰기 가능한 인스턴스 변수가 하나 더 있습니다.
정점 수, 모서리 수, 정점 이름 및 모서리 목록이 포함된 텍스트 파일을 제공하고 있습니다. 무방향 그래프의 경우 (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']