[기본개념] Graph 구조

| 기본구조

 class Graph:
    def __init__(self):
        self.adj_list = {}

그래프는 matrix, list 두가지로 나타낼 수 있는데, 

time complexity 가 더 효율적인 list로 그려내도록 한다

빈 딕셔너리를 만들고 여기에 각 꼭지점을 key로, 연결된 Edges를 values로 나타내도록 한다

 

| Add Vertex  : O(1)

def add_vertex(self, vertex):
        if vertex not in self.adj_list.keys():
            self.adj_list[vertex] = []
            return True
        return False

 

단순 리스트를 append한다

이미 있는게 아니라면, 새로운 빈 리스트를 만들고

그게 아니라 이미 있다면 false를 반환한다

 

 

| Add Edge   : O(1)

def add_edge(self, v1, v2):
        if v1 in self.adj_list.keys() and v2 in self.adj_list.keys():
            self.adj_list[v1].append(v2)
            self.adj_list[v2].append(v1)
            return True
        return False

v1, v2를 연결하는 edge를 만들거다

이 두 꼭짓점이 정상적으로 존재한다면, 안심하고 각 리스트의 value에 해당 꼭지점을 추가해주고

없다면 에러니까 false를 리턴해준다

   

| Remove Edge   : O( |E| )

 def remove_edge(self, v1, v2):
        if v1 in self.adj_list.keys() and v2 in self.adj_list.keys(): 
            try:
                self.adj_list[v1].remove(v2)
                self.adj_list[v2].remove(v1)
            except ValueError:
                pass
            return True
        return False

 

해당 꼭지점이 갖고 있는 엣지의 갯수만큼 루프를 돌아서, 찾아서 제거해야 된다

두 꼭지점이 존재하는지 먼저 확인하고,

있으면 제거, 하나라도 없으면 그냥 pass 하면되니까 try except문을 사용한다

  

| Remove Vertex   : O( |V| + |E| )

  def remove_vertex(self, v):
        if v in self.adj_list:
            for other_vertex in self.adj_list[v]:
                self.adj_list[other_vertex].remove(v)
            del self.adj_list[v]
            return True
        return False

한 꼭지점을 제거할때도 마찬가지.

일단 실제로 존재하는지 먼저 확인하고,

존재한다면 그 안의 연결된 꼭지점들에 대해서 루프를 돌면서

그 꼭지점에 연결된 v를 remove해준다

다 하고 나서, v 자체를 del 로 없애준다.

 

 

 

공통적으로, 이 꼭지점이 존재하는지를 가장 먼저 확인한다는 점을 볼 수 있다.