그래프란?
그래프는 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다. 정점 집합과 간선 집합으로 표현이 가능하다. 여기서 정점과 간선은 노드(Node) 와 엣지(Edge)라고 부른다.
이런 그래프는 보통 인물 관계도에서 많이 볼 수 있다. 여기서는 정점이 인물이고 간선이 정점간의 관계이다.
실제 소프트웨어에 사용되는 예로는 지하철 노선도나 페이지 랭크 알고리즘이 있다. 지하철 노선도의 경우 각 정점이 지하철역이 되며 지하철역과 역 사이의 간선은 이동 시간 정보를 가지고 있다. 페이지 랭크 알고리즘은 구글이 존재 할 수 있게 한 알고리즘이다. 간단하게 설명하자면, 하나의 페이지가 정점이 되고 페이지에서 파생되는 링크들이 간선이 된다. 페이지 랭크는 이런 방식으로 페이지와 랭크를 수집하여 우선도를 측정하고 검색 결과를 계산한다.
그래프의 특징
위의 예시처럼 그래프는 소프트웨어 개발에서 중요한 자료구조중 하나이다. 그래프의 특징으로 4가지가 있다.
1. 정점은 여러 개의 간선을 가질 수 있다. 선형 자료구조는 앞뒤로 하나의 요소만 가질 수 있었지만 비선형 자료구조인 그래프는 앞뒤로 여러 개의 요소가 배치 될 수 있다.
2. 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
3. 간선은 가중치를 가질 수 있다.
4. 탐색 시 계속 루프가 가능한 사이클이 발생할 수 있다. 그래서 탐색 시엔 무한 루프에 빠지지 않도록 사이클을 찾아야 할 필요가 있다.
그래프의 종류
무방향 그래프
말 그대로 방향이 존재하지 않는 그래프이다. 반대로 말하면 앙뱡향으로 이동 가능한 간선으로 이루어져 있다고 볼 수 있다. 따라서 간선으로 이어진 정점끼리는 양방향으로 이동이 가능한데 표현하기에는 A에서 B로 이동이 가능하고 B에서 A로 이동이 가능하다.
방향 그래프
간선에 방향성이 존재하는 그래프이다. A정점과 B정점을 보면 양방향으로 갈 수는 있지만 간선이 두개가 존재한다. 만약 간선 두개 중 하나가 존재하지 않는다면 양방향으로 이동할 수 없게 된다.
연결 그래프
모든 정점이 서로 이동 가능한 상태인 그래프이다. 특정 정점에서 또 다른 특정정점까지 모든 경우의 수가 이동 가능해야만 한다.
비연결 그래프
특정 정점쌍 사이에 간선이 존재하지 않는 그래프이다. 예를 들어 아래의 그림처럼 이선협 정점이 그 어떤 간선과도 연결되어 있지 않기 때문에 이 그래프는 비연결 그래프라고 부른다.
완전 그래프
연결 그래프를 넘어 모든 정점끼리 연결된 상태인 그래프이다. 따라서 한점의 간선 수는 모든 정점의 수 - 1 이 된다. 그리고 모든 정점의 수에 1을 뺀 값에 모든 정점 수를 곱하면 모든 간선 수를 알 수 있다.
사이클
사이클은 말 그대로 순환되는 영역을 말한다. 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분을 말할 수 있는데 그림에서는 A,B,C 정점이 서로 순환되는 것을 알 수 있다.
이런 그래프를 코드로 나타내려면 두 가지 방법이 존재한다. 인접 행렬과 인접 리스트 두 가지 방식으로 그래프를 표현할 수 있다. 인접 행렬은 2차원 배열을 이용할 수 있고 인접 리스트는 연결 리스트로 표현이 가능하다.
그래프 구현
인접 행렬
인접 행렬은 간단하다. 정점의 크기만큼 2차언 배열을 만들고 연결이 안된 상태로 초기화한다. 그리고 나서 행렬의 열 부분을 시작 정점, 행 부분을 도착 정점으로 두고 true 값을 넣어주면 간선이 연결 된 것으로 할 수 있다. 이런 식으로 쉽게 그래프 표현이 가능하다. 만약 간선에 가중치를 넣고 싶다면 false 와 true 가 아닌 null 과 임의의 가중치 값을 넣으면 된다. 참고로 무방향 그래프를 구현한다면 모든 값을 대칭으로 넣어주면 된다.
인접 리스트
인접 리스트도 구현이 간단하다. 특히 자바스크립트에서 배열은 마치 연결 리스트처럼 무한정 늘어날 수 있기 때문에 정점의 수 만큼 배열을 만든 후 연결할 정점을 배열에 추가하면 된다.
