Algorithm. 그래프 기본

1. 친구관계

A와 B는 친구를 (A - B)로 표현

 

2. 그래프

• 객체들 사이의 연결 관계 표현
• 정점(vertex)집합과 정점을 연결하는 간선(edge)집합으로 구성
• G = (V, E)
• |V| : 정점 수, |E| : 간선 수
• |V| = n개의 정점은 최대 C(n, 2) = n*(n-1)/2 개의 간선이 가능

3. Directed Graph vs Undirected Graph

Undirected Graph

• 서로 대칭적이지 않은 관계
• 기업간의 공급관계, 작업의 선후 관계 등을 표현

4. 가중치 그래프(Weighted Graph)

• 간선에 비용이 추가된 그래프

 

5. 용어

• 인접(adjacency) : 두 정점 사이에 간선이 존재할 경우 인접하다고 한다.
• 완전 그래프 : 모든 정점이 인접한 그래프
• 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제거한 그래프
• 경로(path) : 간선들을 순서대로 나열한 것
• 단순 경로 : 경로 중 한 정점을 최대 한번만 지나는 경로
• 사이클(cycle) : 시작한 정점에서 끝나는 경로

6. 컴퓨터에서 그래프 표현 

인접 행렬(adjacent matrix) vs 인접 리스트(adjacent list)

인접 행렬

• |V| x |V| 정방 행렬
• 인접하면 1, 그렇지 않으면 0으로 표현
• directed graph
  • 행i의 합 -> Vi의 out degree
  • 열i의 합 -> Vi의 in degree
• undirected graph
  • i행의 합 = i열의 합 = Vi의 차수

 

• 단점 : 정점의 개수가 커지면 메모리 크기가 n^2으로 커진다.
• 정점의 개수가 커질수록 인접 정점을 찾는 시간이 오래걸린다.

인접 리스트

• 각 정점에 대한 인접 정점을 순차적으로 표현
• 하나의 정점에 대한 인접 정점들을 각 노드로 하는 연결리스트로 저장