[알고리즘] 그래프

1. 그래프 관련 용어 정리

- 그래프(Graph) : 실제 세계의 현상이나 사물을 정점(노드)와 간선으로 표현

- 노드(Node) : 위치를 말하며 정점(Vertex)와 같은 말

- 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선을 의미, link나 branch라고도 함

- 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 노드

 

2. 그래프 종류

1) 무방향 그래프(Undirected Graph)

- 방향이 없는 그래프 → 노드는 양방향으로 갈 수 있음

- 노드 A,B : (A,B)나 (B,A)로 표현

무방향그래프

 

2) 방향 그래프(Directed Graph)

- 방향이 있는 그래프

- 노드 A,B (A→B) : <A,B>로 표현

방향그래프

 

3) 가중치 그래프(Weighted Graph) 또는 네트워크(Network)

- 간선에 가중치가 할당된 그래프

가중치그래프

 

4) 연결 그래프(Connected Graph)

- 무방향 그래프에 있는 모든 노드에 대해 항상 경로가 존재하는 경우

 

5) 비연결 그래프(Disconnected Graph)

- 무방향 그래프에서 특정 노드에 대해 경로가 존재하지 않는 경우

 

6) 사이클(Cycle)

- 단순 경로의 시작 노드와 종료 노드가 동일한 경우

 

7) 비순환 그래프(Acyclic Graph)

- 사이클이 없는 그래프

 

8) 완전 그래프(Complete Graph)
- 그래프의 모든 노드가 서로 연결되어 있는 그래프

 

---

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online