자료구조_비선형구조 ②그래프

 

[1] 그래프 개념 

---

(1) 그래프 개념 

객체를 나타내는 정점vertex과 객체를 연결하는 간선 edge로 구성된 집합이다 

G = (V,E)

 

 

 

 

 

[2] 그래프 종류 

---

(1) 무방향 그래프 

두 정점의 쌍에 순서가 없는 그래프

(v0,v1) 와 (v1,v0)이 동일하다 

최대 간선의 수 = n(n-1) / 2 개이다 (n : 정점의 수)

 

(2) 방향 그래프

간선을 표현하는 두 정점의 쌍에 순서가 있는 그래프

(vj,vk) 와 (vk,vj)가 다른 그래프  

최대 간선의 수 = n(n-1) 개이다 (n : 정점의 수)

 

 

(3) 신장트리 spanning tree

n개의 정점으로 이루어진 무방향 그래프 에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리

최소비용 신장트리 알고리즘

kruskal 알고리즘 : 가중치가 높은 간선을 제거한다 

prime 알고리즘 : 간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해 나간다 

 

 

 

 

 

 

[3] 그래프 구현

---

(1) 인접행렬 adjacency matrix

행렬에 대한 2차원 배열을 사용하는 순차자료구조

그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장한다 

 

 

 

 

(2) 인접리스트 adjacency list

각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트

각 정점의 차수만큼 노드를 연결, 인접 리스트의 각 노드, 정점의 헤드 노드 

(3) 인접 다중 리스트 adjacency Mulitilist

여러 리스트가 노드들을 공용하는 리스트

특정 간선에 대한 접근 여부를 표시하는데 편리하다 

간선의 부속된 두 정점 각각에 대한 인접 리스트를 다중 리스트로 유지하여 하나의 간선을 두개의 리스트가 공유하는 리스트

 

[4] 그래프 순회

---

(1) 너비 우선 검색  BFS(bread first search)

시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서, 방문했던 정점 중 첫 노드를 시작으로 다시 인접한 정점들을 차례로 방문하는 방식으로 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회방법 

 

(2) 깊이 우선 검색  DFS(depth first search)

시작 정점의 한 방향으로 갈수 있는 경로가 있는 곳까지 깊이 검색해가다가 더이상 갈곳이 없게 되면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 검색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법