Graph

그래프는 객체간의 관계를 보여주는 자료구조다. (라인그래프나 차트같은게 아니다.) 네트워크라고도 한다.

정점은 vertex라고 부르고 간선은 edge라고 부른다. 트리 역시 그래프의 일종이다. 엣지는 값을 가질수 있다.

예를 들어 나와 친구가 몇번을 만났는지를 값으로 저장할수도, 도시간의 거리를 값으로 저장 할 수도 있다.

엣지는 방향성을 가질수 있다.

예를들어 여행계획을 만들때 방향성을 가질수도 있다.(도쿄 -> 한국 -> 베트남) 도시간의 거리나 비행기 가격이 엣지의 값이 될 수 있다. 마찬가지로 반대방향의 방항성도 가질수 있다. 친구간의 관계를 표현할때는 방향성이 필요 없을지도 모른다.

사이클은 그래프 알고리즘에서 굉장히 위험하다. 무한루프를 돌 수 도 있기 때문이다.

connectivity

모든 정점이 연결되어있다면 강하게 연결되어있다고 한다. (이게 connectivity 였구나)

그래프 표현 연습

당신은 인터뷰나 컴터공학등에서 나타나는 여러가지 모양의 그래프에 익숙해져야 한다. 그리고 어떤 형식이든 당신은 표현할줄 알아야한다.

이번 연습에서 너는 그래프클래스에 함수를 더할 필요가있다. 같은 그래프를 가지고 다양한 연출을 하기위해서.

너의 그래프는 두가지 컴포넌트를 갖는다.(노드,엣지)

```

class Node(object):

def \_\_init\_\_\(self, value\):

    self.value = value

    self.edges = \[\]

```

노드는 트리에서의 것들과 같다. 자식으로 엣지의 리스트들을 갖는거 빼곤.

```py

class Edge(object):

def \_\_init\_\_\(self, value, node\_from, node\_to\):

    self.value = value

    self.node\_from = node\_from

    self.node\_to = node\_to

```

Here, we assume that edges have both a value and a direction. An edge points from one node to another—the node it starts at is the node_from and the node it ends at is the node_to. You can envision it as node_from -> node_to.

The base of the Graph class looks something like this:

```py

class Graph(object):

def \_\_init\_\_\(self, nodes=\[\], edges=\[\]\):

    self.nodes = nodes

    self.edges = edges

```

A Graph class contains a list of nodes and edges. You can sometimes get by with just a list of edges, since edges contain references to the nodes they connect to, or vice versa. However, our Graph class is built with both for the following reasons:

If you're storing a disconnected graph, not every node will be tied to an edge, so you should store a list of nodes.

We could probably leave it there, but storing an edge list will make our lives much easier when we're trying to print out different types of graph representations.

Unfortunately, having both makes insertion a bit complicated. We can assume that each value is unique, but we need to be careful about keeping both nodes and edges updated when either is inserted. You'll also be given these insertion functions to help you out:

def insert_node(self, new_node_val):

new_node = Node(new_node_val)

self.nodes.append(new_node)

def insert_edge(self, new_edge_val, node_from_val, node_to_val):
      from_found = None
      to_found = None
      for node in self.nodes:
          if node_from_val == node.value:
              from_found = node
          if node_to_val == node.value:
              to_found = node
      if from_found == None:
          from_found = Node(node_from_val)
          self.nodes.append(from_found)
      if to_found == None:
          to_found = Node(node_to_val)
          self.nodes.append(to_found)
      new_edge = Edge(new_edge_val, from_found, to_found)
      from_found.edges.append(new_edge)
      to_found.edges.append(new_edge)
      self.edges.append(new_edge)

def get_edge_list(self):
    # Should be [(100, 1, 2), (101, 1, 3), (102, 1, 4), (103, 3, 4)]
    result = []
    for e in self.edges:
        result.append((e.value, e.node_from.value, e.node_to.value))
    return result

def get_adjacency_list(self):
    # Should be [None, [(2, 100), (3, 101), (4, 102)], None, [(4, 103)], None]
    max_index = self.find_max_index()
    result = [None]*(max_index+1)
    for e in self.edges:
        newList = []
        if result[e.node_from.value] == None:
            result[e.node_from.value] = [(e.node_to.value, e.value)]
        else:
            result[e.node_from.value].append((e.node_to.value, e.value))
    return result

def get_adjacency_matrix(self):
    # Should be [[0, 0, 0, 0, 0], [0, 0, 100, 101, 102], [0, 0, 0, 0, 0], [0, 0, 0, 0, 103], [0, 0, 0, 0, 0]]
    max_index = self.find_max_index()
    matrix = [[0,0,0,0,0] for i in range(0,max_index+1)]
    for e in self.edges:
        matrix[e.node_from.value][e.node_to.value] = e.value
    return matrix

def find_max_index(self):
    max_index = -1
    if len(self.nodes):
        for node in self.nodes:
            if node.value > max_index:
                max_index = node.value
    return max_index

깊이우선탐색

그래프에는 루트가 없다 따라서 어디서 시작해도 상관 없다.

재귀를 사용한다

  • output, edge_list 배열 두개가 필요하다.

  • 시작 값을 output 배열에 넣고, 방문했다고 True표시해준다.

  • edge_list에는 시작 노드의 엣지들을 루프돌리고 엣지의 node_to값이 start_node와 겹치면 빼준다.(양방향이라 겹치는게 있나보다?)

  • 이제 엣지를 for루프돌리고 엣지가 아직 방문하지 않은 엣지면 node_to를 꺼내서 재귀한다.

  • 이함수의 리턴값은 배열이기 때문에 output과 extend해준다.

시간복잡도는 o(|e|+|v|)다 이다.

https://www.cs.usfca.edu/~galles/visualization/DFS.html

def dfs_helper(self, start_node):
    output = [start_node.value]
    start_node.visited = True
    edge_list = []
    for e in start_node.edges:
        if e.node_to.value != start_node.value:
            edge_list.append(e.node_to)

    for node in edge_list:
        if node.visited == False:
            output.extend(self.dfs_helper(node))
    return output

def dfs_helper(self, start_node):
    # recursive
    ret_list = [start_node.value]
    start_node.visited = True
    for edge in start_node.edges:
        if (edge.node_from.value == start_node.value) and (edge.node_to.visited == False):
            ret_list.extend(self.dfs_helper(edge.node_to))
    # dfs_helper(node)
    return ret_list

너비우선탐색

역시 아무곳에서나 시작해도 상관 없다. 이건 큐를 사용한다.

먼저 방문한 노드는 따로 모아둔다. 방문 예정인 노드들은(이전에 방문한 노드의 이웃) 큐에 넣는다. 이미 방문한 노드라면 큐에 넣을 필요없다. 큐에서 하나씩 빼서(deque) 방문하고 또 이웃을 데려오고 ...그냥 반복문으로 가능.

  • todo(큐), done(array) 두개가 필요하다.
  • 첫번째 노드를 가져와서 todo에 넣고 방문했다는 표시를 한다.(이표시는 큐에 넣을때 하는거다.)
  • 큐를 루프를 돌린다. 루프에서는 매루프마다 큐의 첫번째 값(노드)을 빼온다.
  • 빼온 노드와 연결되어있는 엣지들을 for루프돌리고, 이엣지들의 node_to가 방문한적이 있는지 확인해 미방문된 노드라면 큐에 넣는다. 큐에 넣을땐 visited를 잊지 않는다.
  • for문이 끝나면 앞서 빼온 노드를 done에 넣어준다.

한번에 한레벨씩만 이동한다. 한레벨의 모든 노드를 접근하기 전에는 다음레벨로 넘어가지 않는다.

시간복잡도는 o(|e|+|v|)다 이다.

https://www.cs.usfca.edu/~galles/visualization/BFS.html

# 유다시티
def bfs(self, start_node_num):

    node = self.find_node(start_node_num)
    self._clear_visited()
    ret_list = [] # visited

    # Your code here
    queue = [node] # todo
    node.visited = True #처음값

    def enqueue(n, q=queue):
        n.visited = True
        q.append(n)

    def unvisited_outgoing_edge(n,e):
        # node의 edges를 루프돌려서 나온 엣지들이다.
        # 엣지의 node_from은 당연히 node와 같아야 한다.
        # node_to는 방문한적이 없어야한다.
        return ((e.node_from.value == n.value) and (not e.node_to.visited))

    while queue:
        node = queue.pop(0) # 하나빼고
        for e in node.edges: # 빼낸 노드의 엣지를 돌리고
            if unvisited_outgoing_edge(node,e): # 방문한적 없는 노드라면 큐에 넣는다.
                enqueue(e.node_to)
        ret_list.append(node.value) # 방문했으니 집어넣고

    return ret_list

# 민우코드
def bfs(self, start_node_num):

    node = self.find_node(start_node_num)
    self._clear_visited()
    done = [] # visited

    # Your code here
    todo = [node]
    node.visited = True

    while todo:
        node = todo.pop(0)
        for e in node.edges:
            if (e.node_from.value == node.value) and (e.node_to.visited == False):
                e.node_to.visited = True
                todo.append(e.node_to)
        done.append(node.value)
    return done

그밖에

  • Eulerian Paths
  • Hamitonian Paths

알게된것

  • 그래프는 모델링일 뿐이다. 말그대로 자료를 넣는 구조일뿐이다.
  • 결국 만들때는 그래프로 만들고 꺼낼때 인접리스트인지, 인접매트릭스인지를 결정하는거다.(그저 데이터를 표현하는 방법에 불과하지 않나 싶기도 하다)
  • 단어 사다리도 그래프로 다 만들고 꺼내면서 연결되어있는지 확인하는거다.
  • 꺼낼때 깊이로 꺼낼지 너비로 꺼낼지 이런거도 선택사항이다.
  • 심지어 그래프 클래스를 만들지 이런거도 다선택사항이다.

results matching ""

    No results matching ""