자료구조: 그래프Graph의 기본적인 이해 (1)

그래프 graph (1) - 기본 개념 이해

그래프를 설명하는 글의 카테고리를 Concept로 할지 Data Structure로 할지 고민하다가 후자로 하기로 했습니다!
우리가 프로그래밍을 하다보면 어떤 이유에서든 '탐색'이라는 걸 필요로 할 때가 있죠?
'탐색'이란 누구에게나 일상적이고 익숙한 개념이지만, 컴퓨터는 우리와 달리 알려준 것만 알 수 있으니까, 좀 더 구체적이고 명시적으로 알려줄 필요가 있을 거에요.
그래서 컴퓨테이셔널하게 좀 더 풀어서 설명해보자면, 탐색이라는 건 관계를 가지는 어떤 node들을, 정해진 방문 방법을 가지고 순차적으로 방문하며 처리하는걸 말해요. 그리고 이렇게 탐색을 할 수 있도록 정의된 대상을 그래프graph라고 합니다.
이렇게 말하니 좀 낯설죠. 하지만 많이 어려운 개념은 아니에요. 저나 여러분이나 프로그래머가 되려면 위와 같은 그래프 & 탐색 개념을 자주 접해서 익숙해질 필요가 있습니다. 화이팅!

이 글을 읽기에 좋은 주요 대상은 '그래프를 좀 알아보긴 했는데 뭔지 잘 모르겠어' 하는 사람이 될 것 같네요! (딱 제 수준을 말하는 것이죠ㅎㅎ)

그래프의 특성

---

그래프에 대해서 "이건 정점vertex이란 거고 이건 간선edge란 거고 이건 뭐고 저건 뭐고..." 이렇게 설명하면 도입부터 질리기 딱 좋겠죠?
용어를 알긴 알아야 해요. 하지만 우리는 이미 잘 알고 있습니다.
저번 포스팅에서 개념과 활용을 알아본 Tree 구조를 떠올리면 되어요.
Tree는 아주 간단한 규칙을 가지고 작성된 그래프입니다.

• 정점이라는 건 각 node들을 말해요.
• 간선이라는 건 node와 node 사이 연결선을 말해요.

방향성

---

정점과 간선이라는 용어를 알게되었는데요.
그래프의 정점 사이를 연결하는 간선들은 방향성이 존재해요.
그럼 앞에서 비유로 든 Tree 설명과 뭔가 좀 부딪히는 개념이 발견되죠?

Graph의 vertex 사이에는 (대개) 방향성이 존재한다고? Tree의 node와 node 사이에는 방향이 없는걸?

하지만 그건, Tree의 정점들은 무조건 위에서 아래로 향하고 있기 때문에 생략된 것 뿐이에요. 오히려 그런 질문이 떠올랐다면 방향성을 잘 이해하고 있다고 생각할 수 있겠네요!

정점의 방향성은 다음과 같습니다.

• 한 정점에서 한 정점으로 방향이 정해져 있을 때: directed
• 그냥 연결만 되어있을 때: undirected
• 자기 자신을 향할 수 있을 때: self-directed

서클의 유뮤 cyclic / acyclic

---

binary tree는 너무 단순한 구조(위에서 아래로, 최대 두 갈래로 흐르는)를 가지고 있기 때문에 서클 개념이 없어요.
하지만 상상해볼게요.

tree의 leaf node에서 root node로 향하는 간선이 존재하게 된다면?
하나의 node에서 형제 노드로 이어진 간선이 존재하게 된다면?

그렇게 된다면 해당 트리는 계속해서 탐색할 수 있도록, 동그랗게 연결된 부분이 생기는 거겠죠?
이렇게, 정점 사이를 순환할 수 있는 간선의 고리를 circle이라고 하고요.
circle을 통해 순환할 수 있는 형태를 사이클릭cyclic하다고 합니다.
반대로 binary tree같이 순환할 수 없는 형태의 그래프는 에이사이클릭acyclic하다고 해요.

마무리

---

기본적인 그래프 개념을 알아봤으니 이제 코드로 표현을 해봐야겠죠.
다음 포스트에서는 그래프를 코드로 표현해보면서 그래프의 특성과 탐색 방법에 대해 더 알아보도록 하겠습니다.