그래프 ( Graph) 자료구조

그래프 ( Graph )

단순히 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료 구조
연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.
( ex. 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로 등 )
그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다.

그래프 vs 트리
트리는 그래프의 한 종류이다. ( DAG Diracted Acyclic Graph, 방향성이 있는 비순환 그래프 )
그래프는 싸이클 ( Cycle )이 가능하지만 트리는 불가능하다.

종류	그래프	트리
정의	노드와 그 노드를 연결하는 간선( edge )을 하나로 모아 놓은 자료 구조	그래프의 한 종류 ( DAG Diracted Acyclic Graph, 방향성이 있는 비순환 그래프 )
방향성	방향, 무방향 그래프 모두 존재	방향 그래프
사이클	사이클 ( Cycle ) 가능, 자체 간선 ( self-loop )가능, 순환/비순환 그래프 ( Cyclic, Acyclic ) 모두 존재	사이클, 자체 간선 불가능, 비순환 그래프
루트 노드	해당 개념 없음	한개의 루트 노드, 모든 자식 노드는 한개의 부모 노드를 가짐
부모 - 자식	해당 개념 없음	부모 자식 관계, top-bottom 또는 bottom-top
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS안의 Pre-. In-, Post-order
간선의 수	그래프에 따라 간선의 수가 다름, 간선이 없을 수도 있음	노드가 N인 트리는 N-1의 간선을 가짐
경로	유일할 수도 많을 수도 있음	임의의 두 노드간의 경로는 유일
예시 및 종류	지도, 지하철 노선도, 전기회로 소자들, 도로 등	이진 트리, 이진 탐색 트리, 균형트리 ( AVL트리, red-black 트리 ), 이진 힙 ( 최대힙, 최소힙 ) 등

참고 

     오일러 경로 ( Euleraion tour ) 

     그래프에 존재하는 모근 간선 ( edge )을 한 번만 통과하면서 처음 정점 ( vertex )으로 되돌아오는 경로.

     그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일려 경로가 존재한다.

 ( 출처 : https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html )

 

 : 그래프와 관련된 용어

     정점( vertex ) : 위치의 개념 ( node 라고도 부름 )

     간선( edge ) : 위치 간의 관계, 노드를 연결하는 선 ( link, branch ) 

     인접 정점 ( advacent vertex ) : 간선에의해 직접 연결된 정점

     정점의 차수 ( dgree ) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수.

                                   무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배

     진입 차수 ( in-dgree ) : 방향 그래프에서 외부에서 오는 간선의 수 ( 내차수 라고도 부름 ) 

     진출 차수 ( out-dgree ) : 방향 그래프에서 외부로 향하는 간선의 수 ( 외차수 라고도 부름 )

     경로 길이 ( path length ) : 경로를 구성하는데 사용된 간선의 수

     단순 경로 ( simple path ) : 경로 중에서 반복되는 정점이 없는 경우

     사이클 ( cycle ) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

 

 : 그래프의 종류

 : 무방향 그래프 vs 방향 그래프

     무방향 그래프 

      : 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.

        정점 A, 정점 B를 연결하는 간선은 (A, B) 와 같이 정점의 쌍으로 표현한다.

        (A, B) 는 (B, A)와 동일

        ex) 양방향 통행 도로

 

     방향 그래프

      : 간선에 방향성이 존재하는 그래프

        A -> B로만 갈 수 있는 간선은 <A,B>로 표시한다.

       <A,B> 와 <B,A>는 다름

        ex) 일방통행

 

 : 가중치 그래프

     간선에 비용이나 가중치가 할당된 그래프

     네트워크 라고도 한다.

     ex) 도시-도시 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등

 

 : 사이클 vs 비순환 그래프

     사이클 ( cycle ) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

                           단순 경로 ( simple path ) : 경로 중에서 반복되는 정점이 없는 경우

     비순환 그래프 : 사이클이 없는 그래프

 

 : 완전 그래프

     그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프

     무방향 완전 그래프

      : 정점 수가 n 이면, 간선 수는 n*(n-1) / 2