[Data Structure] Graph

1. Graph란? 

 

 Graph란 데이터 간의 복잡한 관계도를 표현할 수 있는 Data Structure다. 예를 들어, 내 친구 4명 A, B, C, D가 있다. 나는 친구들을 모두 알지만, 친구들끼리는 서로 모른다고 가정하자. 이러한 관계를 명확하게 표현할 때 이용할 수 있다. 또 다른 예시로는 , 비행기 루트를 들 수 있다. 

 

한국에서 일본을 간다고 가정하자. 이때 갈 수 있는 경로는 매우 많다. 예를들어, 제주도를 경유해서 가도 되고, 파리를 경유해서 가도 된다. (물론 예시일 뿐이니 가볍게 생각해 주기 바란다.) 이럴 때, 관계를 나타내보면 다음과 같이 나타낼 수 있다. "한국 ---> 제주도 ---> 일본 or 한국 ---> 파리 ---> 일본 or 한국 ---> 제주도 ---> 파리 ---> 일본" 

이밖에도 수많은 경우의 수가 있다. 하지만 이러한 경우의 수를 모두 다 데이터로 저장할 것인가? 아니면 필요한 데이터만 사용하여 경우의 수를 만들 것인가? 나는 후자를 택하겠다. 

 

이 Graph 자료구조를 통해 나는 데이터간의 관계를 표현하고 연결할 수 있음을 배웠다. 앞으로 이러한 상황이 생길 때 이용해야겠다.

class Graph:
    def __init__(self,edges):
        self.edges = edges 
        self.graph_dict = {}
        for start,end in self.edges:
            if start in self.graph_dict:
                self.graph_dict[start].append(end)
            else:
                self.graph_dict[start] = [end] 
        print(f"Graph dict:{self.graph_dict}")

    def get_paths(self,start,end,path = []):
        path = path + [start]
        if start == end:
            return [path]
        
        if start not in self.graph_dict:
            return []
        paths = []
        for node in self.graph_dict[start]:
            if node not in path:
                new_paths = self.get_paths(node,end,path)
                for p in new_paths:
                    paths.append(p)
        return paths 
    
    def get_shortest_path(self, start, end, path=[]):
        path = path + [start]

        if start == end:
            return path

        if start not in self.graph_dict:
            return None

        shortest_path = None
        for node in self.graph_dict[start]:
            if node not in path:
                sp = self.get_shortest_path(node, end, path)
                if sp:
                    if shortest_path is None or len(sp) < len(shortest_path):
                        shortest_path = sp

        return shortest_path