그래프

---

그래프는 비선형 자료구조이고 그래프는 아이템들 사이의 연결관계를 표현하는 자료구조이다.

정점들의 집확과 이들을 연결하는 간선들의 집합으로 구성된다.

선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하는데 용이하다.

---

그래프

 

그래프 용어

정점 : 그래프의 구성요소로 하나의 연결점

간선 : 두 정점을 연결하는 선

차수 : 정점에 연결된 간선의 수

 

그래프 유형

• 무향 그래프
• 유향 그래프
• 가중치 그래프
• 사이클이 없는 방향 그래프
• 완전그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프
• 부분그래프

 

그래프 경로

경로란 어떤 정점 A에서 시작하여 다른 정점 B로 끝나는 순회로 두 정점 사이의 간선들을 순서대로 나열한것

 

그래프 표현

간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정

 

<인접행렬>

• V X V 크기의 2차원 배열을 이용해서 간선의 정보를 저장

<인접 리스트>

• 각 정점마다 다른 정점으로 나가는 간선의 정보를 저장

<간선 리스트>

• 간선의 정보를 객체로 표현하여 리스트에 저장

---

인접행렬

두 정점을 연결하는 간선의 유무를 행렬로 표현 V X V 정방 행렬

두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현

---

[ 무향 그래프 ]

i번째 행의 합 = i번째 열의 합 = Vi의 차수

 

무향 그래프 예시

 

 

무향 그래프 인접행렬

---

[ 유향 그래프 ]

행 i의 합 = Vi의 진출 차수

열 i의 합 = Vi의 진입 차수

유향 그래프 예시

 

유향 그래프 인접행렬

 

 

---

인접 리스트

하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장

---

[ 무향 그래프 ]

무향 그래프의 노드 수 = 간선의 수 * 2

각 정점의 노드 수 = 정점의 차수

무향 그래프 인접 리스트

 

[ 유향 그래프 ]

유향 그래프의 노드 수 = 간선의 수

각 정점의 노드 수 = 정점의 진출 차수

유향 그래프 인접 리스트