그래프 - 비선형 자료구조

👩‍💻  그래프 (Graph)

정점과 간선으로 이루어진 자료구조 (Cyclic)

• 연결된 정점간의 관계를 표현할 수 있는 자료구조
• 트리와 다른점은 트리는 an cyclic 이라면 그래프는 cyclic이다. ***
• 간선끼리 가중치가 있는 경우도 있다. 

 

그래프의 용도 : 

• 지하철 노선도, 통신 네트워크, ...

 

✏️  그래프 구조

• 정점(Vertex) : 각 노드
• 간선(Edge) : 노드와 노드를 연결하는 선 (Link, branch)
• 인접 정접 (Adjacent vertex) : 간선 하나를 두고 바로 연결된 정점
• 정점의 차수 (Degree):
  • 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배
• 진입 차수 (In-degree): 방향 그래프에서 외부에서 오는 간선의 수
• 진출 차수 (Out-degree): 방향 그래프에서 외부로 나가는 간선의 수
• 경로 길이(Path length): 경로를 구성하는데 사용된 간선의 수 
• 단순 경로 (Simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(Cycle): 단순 경로의 시작 정점과 끝 정점이 동일한 경우

 

✏️  그래프의 특징과 트리와의 차이

	그래프	트리
개요	노드와 간선으로 이루어진 자료구조	그래프의 한 종류
방향성	방향 그래프, 무방향 그래프	방향 그래프
사이클	Cyclic	Acyclic
모델	네트워크 모델	계층 모델
루트 노드	루트 노드 X	최상위 노드
부모-자식	부모-자식 관계 X	인접한 상하위 노드
간선 수	그래프에 따라 간선 개수 다름	N개의 노드로 구성된 트리의 간선 수는 N-1개
순회	DFS, BFS	Pre-, In, Post-order / Level-order
경로	2개 이상의 경로 가능	두 노드 간의 경로는 1개

 

 

✏️  그래프의 종류

1) 무방향 그래프

• 간선에 방향이 없는 그래프 (양방향 이동 가능)
• 정점 A - B 간선의 표현 : (A,B) = (B, A)

2) 방향 그래프 

• 간선에 방향이 있는 그래프 (해당 방향으로만 이동 가능)
• 정점 A-> B 간선의 표현 : <A,B> != <B,A>

 

1) 가중치 그래프

• 간선에 값이 있는 그래프 (이동 비용)

2) 완전 그래프

• 모든 정점이 서로 연결되어 있는 그래프
• 정점이 N개일 경우, 간선의 수는 n(n-1)/2개

 

✏️  그래프 탐색 - DFS

✨ 깊이 우선 탐색 (Depth First Search) 

각 노드에 방문했는지 여부를 체크할 배열과 스택 이용하여 구현

 

* 노드의 개수만큼 크기를 가진 배열 선언 후 방문했으면 1을 넣어주며 반복

(우측 그림과 같이 나오게 하기 위해서 진행해보면)

Stack에 A를 넣고, D,C,B를 순서대로 stack에 삽입

-> 더 이상 근처에 방문할게 없으므로 B를 스택에서 꺼낸뒤 B에 인접한 노드들로 반복

-> E를 스택에 넣고 배열에 1 로 방문 처리 후 더 이상 갈 곳이 없으므로 E 꺼냄

-> E에서 인접한 노드 D,G중 D는 방문처리 되어 있으므로 G를 방문 처리 후 넣고, 더 이상 없으므로 G를 꺼냄

-> G에서 인접한 노드 F를 넣고 또 반복

-> F에서는 더 이상 갈 노드가 없으므로 (다 방문처리 된 것 밖에 없음) 스택에서 하나 또 꺼냄 (C)

-> C도 더 이상 갈 노드가 없으므로 나머지 마지막 노드인 D를 꺼냄

 

✏️  그래프의 구현 

✨ 1) 인접 행렬 (Adjacency Matrix)

 

ㄴ 2차원 배열 이용

 

💫 인접 행렬의 장단점

• 간선 정보의 확인과 업데이트가 빠름 O(1)
• 인접 행렬을 위한 메모리 공간 차지

 

✨ 2) 인접 리스트 (Adjacency List) 

ㄴ 연결 리스트 이용

💫 인접 리스트의 장단점

• 메모리 사용량이 상대적으로 적고, 노드의 추가 삭제가 빠름
• 간선 정보 확인이 상대적으로 오래 걸림

 

✨ 인접 행렬 VS 인접 리스트 

인접 행렬 : 노드의 개수가 적고,  간선의 수가 많을 때 유리. 밀집 그래프 (Dense Graph)

인접 리스트 : 노드의 개수가 많고, 간선의 수가 적을 때 유리. 희소 그래프 (Sparse Graph)

	인접 행렬	인접 리스트
특정 간선 검색	O(1)	O(degree(V))
정점의 차수 계산	O(N)	O(degree(V))
전체 노드 탐색	O(N^2)	O(E)
메모리	N * N	N + E

N: 전체 정점 개수 / E : 전체 간선 개수