[Algorithm] 7-1. Graphs and Graph Traversals

이번 시간에는 자료구조 시간에서도 배운 그래프에 대해 알아보도록 하겠다.

그래프가 사용되는 경우와 그래프의 종류에 대해 먼저 알아보도록 하자.

 

 

 

 

 

● 그래프가 사용되는 경우

① Airline Routes (항공 노선)

- 도시들을 vertex(정점)으로 표시, 두 도시를 오가는 항공편이 있으면 edge(간선)으로 표시

 

- SD에서 SAC로 가는 데 비행기를 가장 적게 갈아타는 방법은?

  → Shortest Path 문제

  → SD-SF-SAC 또는 SD-LA-SAC

  → BFS(너비 우선 탐색) 방법을 사용하면 된다.

 

 

- SD에서 SAC로 가는 데 비행기를 가장 많이 갈아타는 방법은?

  → 단, 한 번 들렀던 도시는 다시 방문하지 않는다.

  → Longest Simple Path (여기에서 simple은 재방문하지 않는다는 뜻)

  → SD-OAK-LA-FRES-STK-SF-SAC

  → empty hard 문제

 

 

② FlowCharts (순서도)

- 알고리즘의 서술 방법 중 하나였다.

  → 또다른 방법은 pseudocode가 있었고, 우리가 자주 사용하기로 했었다.

- 이전 예와 달리 간선의 한 쪽 끝에 화살표가 있는 유향그래프임을 볼 수 있다.

 

 

③ Binary Relation

- x는 y의 인수인데, proper factor 즉, 자기 자신을 제외한 인수이다.

 

 

- 예를 들어, 2의 경우는 총 4개의 outgoing edge가 있다. 4,6,8,10으로.

- 1은 자기 자신을 제외한 모든 수의 인수이기 때문에 다른 node에 모두 연결되어 있다.

 

 

④ Computer Networks

- 인터넷이 있는 모든 집에 유선을 깔아서 연결하려고 한다.

- 다른 집들을 거쳐서라도 연결이 되면 된다.

 

- edge마다 비용이 다를 수 있고, 이 때는 Minimum Spanning Tree 문제이다.

 

 

 

● Directed Graph (유향 그래프)

- digraph라고 부르기도 하고 두 개의 쌍으로 G = (V, E)로 표시된다.

- V는 (vertices) 정점들의 집합이다.

- E는 (edges) 간선들의 집합이다.

- vertices는 nodes라고 부르기도 한다.

- E의 원소는 edges, directed edges, arcs라고 부르기도 한다.

- 방향 있는 간선인 (v, w)에서 v는 꼬리(tail), w는 머리(head)라고 불린다.

- (v, w)는 v → w 또는 vw라고 표현되기도 한다. <v, e>라고 표현하는 곳도 있다.

 

 

 

 

 

● UnDirected Graph (무향 그래프)

- G = (V, E)는 정점과 간선의 쌍으로 이루어진 그래프이다.

- V는 정점들의 집합이고, E는 간선들의 집합이다.

- E는 순서가 없는 구별되는 V의 쌍들의 집합이다.

- {v, e}, v-w, vw, wv로 표현된다.

- vw는 "incident upon vertices v and w"라고 표현되는데, 연결을 나타내는 것이다.

- incident는 간선과 정점 사이의 연결 관계를 나타내는 것이고, adjacent는 정점과 정점 사이의 관계를 표현한다는

  점에서 다르다.

 

 

 

 

 

 

● Weighted Graph (가중치 그래프)

- weighted graph는 전의 두 그래프와 달리 세 가지 종류들의 모임을 원소로 가지고 있는 집합이다.

- (V, E, W)

- W는 E에서 R로 가는 함수이다. 간선을 입력하면 그 간선의 가중치를 반환하는 함수인 것이다.

- 보통 가중치는 거리, 요금, 비행시간 등을 나타낸다.

 

 

 

 

 

 

 

 

 

다음 시간에는 구체적으로 그래프를 어떻게 구현하는지 등에 대해 배우도록 하겠다.