그래프의 개념과 특징

그래프(Graph)의 개념과 구조

그래프(Graph)의 정의

그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조입니다.

컴퓨터 공학에서 말하는 자료 구조 그래프는 일반 적으로 생각하는 그래프와 다른 모양입니다.

자료 구조의 그래프는 위의 그림 처럼 여러 개의 점들이 선으로 연결되어 있는, 거미줄 처럼 복잡한 네트워크와 유사한 모습을 보입니다.

그래프의 구조

그래프는 정점과 간선으로 구성되어 있습니다.

그래프에서 하나의 점은 정점(vertex) 이라고 표현합니다.

하나의 선은 간선(edge) 이라고 표현합니다.

예로 알아보는 그래프

A, B, C 세 친구는 각기 다른 지역에 거주합니다. 셋이 C가 사는 부산에 놀러가기로 했는데, 서울에 사는 A는 하루전에 B의 집에서 자고, 다음날 C가 광주에 있는 A,B를 데리고 부산으로 가기로 했습니다.

여기서 3개의 정점은 서울, 광주, 부산입니다.

이 정점들은 각각의 관계를 표현하는 간선으로 연결되어 있습니다.

• 정점 : 서울, 광주, 부산
• 간선: 서울-광주, 광주-부산, 부산 -서울

그렇다면 1이 연결된 상태, 0이 연결되지 않은 상태를 타나낼때

1 == 서울, 2 == 부산, 3 == 광주
[1] = [0, 1, 1] // 서울-부산, 서울- 광주
[2] = [1, 0, 1] // 부산-서울, 부산 -광주
[3] = [1, 1, 0] // 광주-서울, 광주-부산

---

그래프 용어 정리

• 정점(vertex):노드(node)라고도 합니다. 데이터가 저장되는 그래프의 기본 원소입니다.
• 간선(edge): 두 정점을 연결하며, 이들의 관계를 나타냅니다.
• 입점 정점(adjacent vertex): 간선에 의해 직접 연결된 정점을 의미합니다.
• 가중치 그래프(weighted Graph): 연결의 강도(추가적인 정보, 위의 예시에서는 서울-부산으로가는 거리)를 나타내는 그래프를 의미합니다.
• 비가중치 그래프(unweighted Graph): 연결의 강도를 표현하지 않는 그래프를 의미합니다. 이 경우 한 정점에서 다른 정점으로 이동하는 것과 반대로 부산에서 서울로 가는 것도 가능합니다. 앞선 예시에서 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능합니다. 하지만 단방향(directed)그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능 합니다. 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
• 진입차수(in-degree) /진출차수(out-degree): 한 정점으로 들어오는 간선과 나가는 간서의 수를 의미합니다.
• 인점(adjacency): 두 정점이 직접 연결되어 있는 경우, 이들을 인접하다고 표현합니다.
• 자기 루프(self loop): 한 정점에서 시작해서 바로 그 정점으로 돌아오는 경로를 의미합니다.
• 사이클(cycle): 한 정점에서 시작해서 다시 그 정점으로 돌아오는 경로가 존재한다면 이를 사이클이 있다고 표현합니다.