[알고리즘] 그래프

그래프

• 버스 정류장과 여러 노선이 함께 포함된 형태 또는, 링크드인(Linked in)과 같은 사회 관계망 서비스의 연결 등의 형태
• 현상이나 사물을 정점과 간선으로 표현하는 것
• G = (V, E)
•  
• V : 정점의 집합
  • 정점 Vertex
    • 노드 Node
    • 독립형 객체/Circle로 표현
    •  
• E : 간선의 집합
  • 간선 Edge
    • 링크 Link
    • 두개의 정점을 결하는 객체
    • 화살표 또는 실선으로 표현
    •  
• 두 정점이 간선으로 연결되어 있으면 인접하다(Adjacent)고 한다

방향 그래프

• 방향성에 따른 분류
• 방향 있는 간선(Directed Edges)을 지닌 그래프
• 각 간선은 하나의 정점을 떠나서, 하나의 정점으로 들어감
• Self-loop(Self-edge) 가능
• 두 정점 사이에 최대 2개의 간선 존재 가능

무방향 그래프

• 방향 없는 간선(Underected Edges)을 지닌 그래프
• Self-loop(Self-dege) 불가능
• (u, v) = (v, u)

그래프의 예

• 무방향 그래프
• 가중치를 가진 무방향 그래프
• 방향 그래프
• 가중치를 가진 방향 그래프

.

그래프의 표현 1 : 인접 행렬

• n x n 행렬로 표현 [n(=|V|): 정점의 총 수]
  • 원소 (i, j) = 1 : 정점 i와 정점 j 사이에 간선이 있음
  • 원소 (i, j) = 0 : 정점 i와 정점 j 사이에 간선이 없음
• 방향 그래프의 경우
  • 원소 (i, j)는 정점 i로부터 정점 j로 연결되는 간선이 있는지를 나타냄
• 가중치 있는 그래프의 경우
  • 원소 (i, j)는 1 대신에 가중치를 가짐

그래프의 표현 2: 인접 리스트

• n개의 연결 리스트로 표현
• i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결해 놓음
• 노드 개수: 2x|E|

그래프의 표현 3: 인접집합

• 보다 직관적으로 그래프를 표현
  -인접 리스트 --> 인접 집합
  -딕셔너리 추가 사용

그래프 순회

• 그래프의 모든 노드를 방문하는 작업
• 너비우선순회(BFS)
  • 먼저 루트의 자식을 차례로 방문
    --> 루트 자식의 자식 ( 루트에서 두 개의 간선을 거쳐서 도달할 수 있는 정점 방문)

    BFS(G,s)
    {
    for each u ∈ V-{s}
      visied[v] <-- NO;    #정점을 방문하지 않았다
    visied[s] <-- YES;       #정점을 방문하였다, s: 시작 정점
    enqueue(Q,s);            #Q : 큐
    while (Q != ∅) {
      u <-- dequeue(Q)
      for each v ∈ L(u)    #L(u) : 정점 u의 인접 정점 집합
          if(visieted[v] = NO) then{
              visted[v] <-- YES;
              enqueue(Q,v);
          }    
    }
    }

너비 우선 탐색 // 옆으로 쭉 연결

import queue
def bfs(graph, start):
    visited = { start }
    que = queue.Queue()
    que.put(start)
    while not que.empty():
        v = que.get()
        print(v, end='')

• 깊이우선순회(DFS)
  • 루트의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳까지 내려감
  • 다음 순서로 노드들을 방문한다
    1) 출발점 s에서 시작
    2) 형재 노드를 visited로 mark하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다.
    3) 2번을 계속 반복한다
    4) unvisited인 이웃 노드가 존재하지 않는 동안 계속해서 직접 노드로 되돌아간다.
    5) 다시 2번을 반복한다
    6) 시작 노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다.

DFS(G)
{
    for each v ∈ V
        visited[v] <-- NO;
    for each v ∈ V
        if(visited[v] = NO)then aDFS(v);
}
aDFS(v)
{
    visited[v] <-- YES;
    for each x ∈ L(v)       #L(v) : 정점 v의 인접 노드의 집합
        if(visied[x] = NO)then aDFS(x);
}

깊이 우선 탐색

def dfs(graph, start, visited):
    if start not in visited:
        visited.add(start)
        print(start, end=' ')
        nbr= graph[start] - visited
        for v in nbr:
            dfs(graph, v, visited)