[그래프] 그래프 개념 설명

- 그래프란 무엇일까요?

그래프라고 하면 '정점(노드)'와 '간선(엣지)'로 이루어진 자료 구조를 말하는데요,

그래프는 간선의 방향 유무에 따라서 단방향 그래프, 양방향 그래프로 나뉩니다.

왼쪽 이미지와 같이 간선이 방향을 나타내면 단방향 그래프,

오른쪽 이미지와 같이 간선이 방향을 나타내지 않으면 양방향 그래프 입니다.

(양방향 그래프는 무방향 그래프라고도 합니다.)

- 그래프의 표현 방식

그래프를 표현하는 방식으로는 3가지 방식이 있습니다.

1. 간선 리스트(Edge List)

  (1) 정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해 '간선 정보'를 저장합니다.

    -> ex) 어떤 두 정점 i,j를 연결하는 간선 (i,j)를 간선 리스트 배열 A에 저장했을 경우

             A[k][0] = i, A[k][1] = j로 나타낼 수 있습니다.

 

    

   위의 단방향 그래프의 간선 정보를 오른쪽 행렬과 같이 나타낼 수 있습니다.

    

  (2) 가중치 그래프의 경우 배열의 3번째 열에 간선의 가중치를 저장합니다.

             

  위의 단방향 그래프의 간선 정보를 오른쪽 행렬과 같이 나타낼 수 있습니다.

  (1)번의 그래프에서 A[6][3]에 해당 간선의 가중치를 추가해주시면 됩니다.

2. 인접 행렬

  (1) 정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서 V X V 크기의 이차원 배열에 그래프 정보를 저장합니다.

  ex) 간선의 가중치가 1일 경우 -> 간선 (i, j)가 존재하면 A[i][j] = 1, 존재하지 않으면 A[i][j] = 0

      간선의 가중치가 w일 경우 -> 간선 (i, j)가 존재하면 A[i][j] = w, 존재하지 않으면 A[i][j] = 0

           

 

  

   양방향 그래프의 경우 위와 같이 간선 정보를 인접 행렬로 나타낼 수 있습니다.

 단방향 그래프의 경우 위와 같이 간선 정보를 인접 행렬로 나타낼 수 있습니다.

가중치가 1이 아닌 경우 위와 같이 간선 정보를 인접 행렬로 나타낼 수 있습니다.

3. 인접 리스트

  (1) 정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서 V개의 연결 리스트로 그래프 정보를 저장합니다.

      ->보통 vector를 사용해서 구현합니다.

위의 양방향 그래프를 인접리스트로 나타내면 오른쪽 그림과 같이 나타낼 수 있습니다.

1과 인접한 노드 2,3,4가 연결되어있고

2와 인접한 노드 1,4,5가 연결되어 있고

3과 인접한 노드 1,4가 연결되어 있고

4와 인접한 노드 2,3,4,5가 연결되어 있고

5와 인접한 노드 2,4가 연결되어 있습니다.

단방향 그래프일 경우도 위와 마찬가지로 나타내주면 됩니다.

간선에 가중치가 있는 경우는 아래의 그림과 같이 나타낼 수  있습니다.

정점 1은 4와 인접해있고 8의 가중치를 가지고 있습니다.

정점 2는 1과 인접해있고 5의 가중치를 가지고 있습니다.

정점 2는 5와 인접해있고 6의 가중치를 가지고 있습니다.

정점 3은 1과 인접해있고 7의 가중치를 가지고 있습니다.

정점 3은 4와 인접해있고 9의 가중치를 가지고 있습니다.

정점 4는 2와 인접해있고 1의 가중치를 가지고 있습니다.

정점 5는 4와 인접해있고 5의 가중치를 가지고 있습니다.

위와 같이 vector로 인접한 노드와 가중치에 대한 정보를 한꺼번에 담고 싶을 때 pair를 사용하시면 됩니다.

ex) 

vector<pair<int, int> > v;

v[1].push_back(make_pair(4,8));  //정점 1은 정점 4와 연결되어있고 8의 가중치를 가집니다.

이렇게 보시면 나중에 코드 보실 때 이해하기 쉬우실거라고 생각합니다.

---

BFS, DFS 탐색법을 학습하기 전에 그래프의 기본 개념에 대해서 정리해봤습니다. 

혹시라도 틀린 내용 있으면 댓글로 피드백 남겨주세요! 즉각 반영하도록 하겠습니다!!

다음 게시물로는 BFS, DFS 탐색법에 대해 포스팅 하도록 하겠습니다!