크래프톤 정글 week02, day11 - 그래프

그래프(Vertex, edge, node, arc)

• 구조
  • 정점(Vertex)
    • 그래프의 기본 단위로, 위치나 상태 등을 표현, 노드(Node)라고 부른다
  • 간선(Edge)
    • 두 개의 정점을 연결하는 선을 말하며 두 정점 사이의 관계나 거리 등을 표현
  • 노드(Node)
    • 간선과 같은 의미이며 특정 상태나 위치를 나타내는 점(dot)
      • 그래프에서 점으로 표현
  • 호(Arc)
    • 방향성이 있는 간선을 의미. 두 정점을 연결하는 선이지만, 한 정점에서 다른 정점으로 방향이 정해져 있다.

​

• 그래프는 정점과 정점들을 연결하는 간선으로 구성
• 그래프는 정점과 간선의 집합으로 이루어진 자료구조이다.
• 특징
  • 방향성
    • 방향성이 있는 그래프를 유향 그래프(Directed Graph)
    • 방향성이 없는 그래프를 무향 그래프(Undirected Graph)
  • 가중치
    • 간선에 가중치가 할당되어 있을 수 있는데, 이를 가중 그래프(Weighted Graph)라고 한다.
  • 루프와 다중 간선
    • 그래프에는 자기 자신으로 돌아오는 루프나 두 정점 사이 여러 간선이 있을 수 있다.
  • 연결성
    • 모든 정점이 어떤 경로든 연결되어 있으면 연결 그래프(Connected Graph)라고 한다.
• 그래프 예시
  • 최단 경로 문제
    • 그래프에 주어진 두 정점 사이의 최단 경로를 찾는 문제
    • ex) 구글 맵에서 한 지점에서 다른 지점까지의 최단 거리나 최소 시간을 계산
    • 해결 알고리즘은 다익스트라(Dijkstra)나 플로이드-와샬(Floyd-Warchall)이 있다.
  • 네트워크 플로우 문제
    • 간선에 할당된 용량을 초과하지 않고, 목적지까지 얼마나 많은 양을 보낼 수 있는지 찾는 문제
    • ex) 파이프라인 네트워크에서 최대 얼마의 물을 보낼 수 있는지 계산
    • 해결 알고리즘은 포드-풀커슨(Ford-Fulkerson)이나 에드몬즈-카프(Edmonds-Karp)가 있다.
  • 그래프 색칠 문제
    • 그래프의 정점들을 색칠하는데 인접한 두 정점이 같은 색이 되지 않도록 색을 분배하는 문제
    • ex) 지도 색칠 문제에서 최소의 색으로 모든 국가를 색칠
    • 해결 알고리즘은 백트래킹(Backtracking)이 있다.

 

---

다익스트라(Dijkstra)

• 그래프에서 주어진 시작점과 나머지 모든 정점들 간의 최단 경로를 찾는 알고리즘
• 음이 아닌 가중치를 가진 그래프에 사용 가능
  • 가중치란, 정점 간에 연결된 간선에 부여된 값이다. 이 가중치는 두 정점을 연결하는 간선의 비용이나 거리 등을 나타낼 수 있다.
  • 음의 가중치는 가중치 값이 음수인 경우이며, 음의 가중치가 있는 그래프는 사이클을 계속 돌며 비용을 무한이 줄일 수 있기 때문에 최단 경로를 찾는 일이 복잡해진다. 이를 해결하기 위해 벨만-포드 알고리즘이 사용됨
• 동작 방식
  • 1. 아직 방문되지 않은 정점 중에 가장 거리가 짧은 정점을 찾는다.
  • 2. 해당 정점을 방문됨으로 표시하고, 인접한 정점들의 거리를 현재 저장된 거리와 새로운 경로를 통한 거리 중 더 짧은 거리로 업데이트하는 것을 의미한다.
  • 모든 정점이 방문됨이 표시될 때까지 과정 반복

​

• 예시
  • 도시의 여러 위치를 연결하는 버스 노선이 주어졌을 때, 한 위치에서 다른 위치로 가는 최단 시간을 찾는데 사용한다.

 

---

플로이드 와샬(Floyd-Warshall)

• 그래프에서 모든 정점 간의 최단 거리를 구하는 알고리즘이며, 다 익스트라와 다르게 시작점의 노드 만이 아닌 모든 노드들의 최단 거리를 구한다.
• 음의 가중치를 가진 간선이 있어도 사용가능하지만, 음의 사이클이 있는 경우엔 사용 불가
  • 중간에 다른 정점을 거쳐가는 경로를 고려해 최단 거리를 찾는데, 3중 반복문을 사용해 모든 정점 쌍에 대해 '중간 정점'을 거치는 모든 경로를 고려한다.
• 동작 과정
  • 1. 모든 정점 간의 거리를 나타내는 2차원 배열 준비. 배열의 초기 값은 주어진 그래프의 가중치로 설정하고, 간선이 없는 경우는 무한대로 설정, 자기 자신 거리는 0으로 설정
  • 2. 3중 반복문을 통해 모든 정점을 한 번씩 거쳐가는 경로를 고려한다. 이때 기존 거리보다 새로운 경로를 통한 거리가 더 짧다면 거리를 갱신

 

---

BFS(Breadth-First Search) 너비 우선 탐색

• 시작 정점에서 가장 가까운 정점을 먼저 방문하고, 인접한 정점들을 차례로 방문하는 방식이며 큐를 사용해 구현할 수 있다.
• 과정
  • 1. 탐색을 시작할 정점을 큐에 삽입
  • 2. 큐에서 정점을 하나 꺼내고, 그 정점이 탐색의 목표면 탐색 종료
  • 3. 그렇지 않으면, 해당 정점에 인접한 정점 중 아직 방문하지 않은 정점을 모두 큐에 삽입하고 방문했다는 사실을 체크
  • 4. 큐가 빌 때까지 2번, 3번 과정 반복

​

• 예시
  • 미로의 입구에서 출구까지 가장 빠른 경로를 찾는 미로찾기 문제
    • 이 문제에서 BFS를 사용할 때, 가장 먼저 찾은 경로가 최단 경로인걸 알 수 있다.

 

---

DFS(Depth-First Search) 깊이 우선 탐색

• 한 방향으로 갈 수 있는 한 계속 가다가 갈 곳이 없으면 이전으로 돌아와 다음 경로를 탐색하는 방식
• 스택으로 구현하거나 재귀함수를 사용해 구현할 수 있다.
• 과정
  • 1. 탐색을 시작할 정점을 스택에 넣는다.
  • 2. 스택의 최상단 정점을 확인. 이 정점이 탐색의 목표라면 탐색종료
  • 3. 그렇지 않다면, 해당 정점에 인접한 정점 중 방문하지 않은 정점을 모두 스택에 추가하고 각 정점에 방문했다는 사실을 체크
  • 4. 스택이 빌 때까지 2번, 3번 과정 반복

​

• 예시
  • 그래프의 모든 정점을 방문하는 문제에서 DFS를 사용할 시, 한 정점에서 시작해 깊이 우선으로 모든 정점을 방문 가능하다.
  • 그래프의 구조를 파악하거나 두 정점이 연결되어 있는지 확인하는 등의 문제에서 사용

​

​

학습시간 : 10 ~ 25시