그래프는 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']