Grahp란? [자료구조 그래프] 개념 및 특징 종류 구조 // 인접 리스트와 인접행렬 선택 방법

 

 

 

Graph 정의

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

단순히 노드와 그 노드를 연결하는 간선을 하라노 모아 놓은 자료구조라고 표현할 수도 있습니다.

 

*  연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조.

   → 활용 : 지도, 지하철노선도, 도로 통행길, 

 

 

 

 

Graph의 종류

무방향 그래프 (Undirected Graph)

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

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

     (A,B) == (B,A)

 

ex) 양방향 통행 도로()

 

 

방향그래프 (Directed Graph)

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

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

   <A,B> != <B,A>    <ㅡ 둘은 다르다

 

ex) 일방 통행도로

 

 

가중치 그래프(Weighted Graph)

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

 * 네트워크라고도 한다. 

 

ex) 도로의 길이, 통신망 사용료, 도시와 도시의 연결 등..

 

 

 

연결 그래프(Connected Graph)  // 비연결 그래프(Disconnected Graph)

연결 그래프 (Connected Graph)

 * 모든 두 꼭짓점 사이에 경로가 존재하는 그래프 

  -> 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우

ex) 트리구조(Tree): 사이클을 가지지않는 특징을 가지고 있는 연결 그래프임.

 

 

 비연결 그래프(Disconnected Graph)

 *무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우 

 

 

사이클 VS 비순환 그래프

사이클 (Cycle)

 * 단순 경로의 시작 정점과 종료 정점이 동일한 경우 (결국 순환한다는 내용)

  단순 경로란? : 경로 중에서 반복되는 정점이 없는 경우

 

비순환 그래프(Acylic Graph)

 * 사이클이 없는 그래프이다. (순환하지 않는 그래프)

 

 

완전 그래프(Complete Graph)

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

 * 무방향 완전 그래프 (한곳으로 향하는데 모두 연결되어 있는 그래프)

    -> 정점의수가 = n 이면 // 간선의수는 n*(n-1) /2 가 된다.

 

 

 

 

 

 

Graph의 표현방식 (그래프를 구현하는 방법 2가지)

 

인접 리스트

인접 리스트 언제 사용할까?

메모리를 효율적으로 사용하고 싶을때 인접 리스트를 사용하게 된다.

* 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지하게 되는데 그래서 인접 리스트를 가장 일반적으로 많이 사용한다.

 

모든 정점(혹은 노드)를 인접 리스트에 저장한다. 즉 각각의 정점에 인접한 정점들을 리스트로 표시한다.

** 배열(혹은 해시테이블)과 배열의 각 인덱스마다 존재하는 또 다른 리스트(Array, ArrayList, LinkedList)를 이용해서 인접 리스트를 표현하게 된다.

 

 

그래프를 이용하여 DFS 구현해보기 ↓

// 그래프를 이용하여 DFS 구현해보기!

Public class Graph{

   private LinkedList<Integer>[] mimi; // 인접 리스트 생성하기.
   private int v; // vertex 정점 생성.
   
  // 그래프의 생성 및 초기화 작업
   Graph(int v){
     this.v = v; // 정점 개수를 초기화해줌
     visit = new boolean[v] // 방문했는지 여부를 true false로 확인하기.
     mimi = new LinkedList[v+1] // v로 하면 0부터 시작되니 보기 간편하게 1부터 시작하게둠.
                                // 0은 공백으로 할 것임.
     //인접리스트 초기화 작업
     for(int i = 0; int < v+1; i++) {
         mimi[i] = new LinkedList();  // mimi인접리스트 각 요소를 초기화함.
     }
   }
   
   //그래프 인자끼리 연결해주기.
   void GraphEdge(int v1, int v2){
   mimi[v1].add(v2);   // 인접리스트의 mimi[v1]에 v2를 추가해 연결해주고.
   mimi[v2].add(v1);   // 인접리스트의 mimi[v2]에 v1d을 추가해 연결해주기.
   }
   
   public static void main(String args[]){
   Graph dfs_graph = new Graph(5); // dfs_graph를 만들어주고 Graph에 5인자값 넣기.
   
     dfs_graph.GraphEdge(1,2); // 그래프의 1과 2를 연결하고
     dfs_graph.GraphEdge(1,3); // 그래프의 1과 3을 연결하고
     dfs_graph.GraphEdge(3,4); // 그래프의 3과 4를 연결하고
     dfs_graph.GraphEdge(3,5); // 그래프의 3과 5를 연결하기.
     
     // 인자값 1 부터 출력하기 1부터인 이유는 우리가 v를 보기좋게 v+1부터 했기 때문임.
     for(int i = 1; i< dfs_graph.length; i++){
        System.out.printLn(i + " : " + dfs_graph.mimi[i]; // 출력할겁니다 i + 스트링" : " 값과 +
        // dfs.graph.mimi[i] dfs.graph에 들어가있는. mimi를 출력하는것임.
        
     }
   }
}


/*
출력 결과:
1: [2,3] // dfs.graph.GraphEdge로 1에 2,3을 연결해줬고.
2: [1]   // dfs_graph.GraphEdge(1,2) 이 메서드로 인해서 1이랑 연결됐고
3: [1,4,5] // dfs_graph.GraphEdge(1,3) 메서드로 1이랑 연결되고,  직접 4와 5를 연결함  dfs_graph.GraphEdge(3,4);  dfs_graph.GraphEdge(3,5);
4: [3] //  dfs_graph.GraphEdge(3,4)의 이유로 3과 연결됐고,
5: [3] //  dfs_graph.GraphEdge(3,4);의 이유로 3과 연결됐다


*/

인접리스트는 작성해본 위의 예제와 같이 확인해볼 수 있다.

 

 

 

 

 

 

인접 행렬 [말 그대로 2차원 배열로 구현한 것. ]

인접 행렬 언제 사용할까? 

한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이하다.

ex) A에서 B로 진출하는 간선이 있나 파악하기 위해서 0번재 줄의 1번째 열에 어떤 값이 저장되어있는지 바로 확인하기.

가장 빠른 경로찾기(Shortest Path)에 주로 활용된다.  (** 코딩 테스트에서 구현할때 주로 많이 사용된다.)

 

인접행렬은 말그대로 너무 쉽게 작성할 수 있는데

int[][] mimi = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{,0,0,0}};

와 같이 적으면 된다.

 

0과 1을 이용해 정수 행렬(Integer Matrix)을 사용할 수도 있다.

// 0과 1을 이용해서 정수 행렬을 사용하기.

if(간선 (i,j)가 그래프에 있다면)
 matrix[i][j] = 1;  
else
 matrix[i][j] = 0;

ex) 정수 행렬을 활용한 예제 ↓

// 간선은 두개가 이어져 있다는 사실만 알려 줄 뿐 그 외의 정보는 포함하지 않는다.
// 이렇게 추가적인 정보를 파악할 수 없는 그래프를 비가중치 그래프라고 한다.

/*
     Ex) 1 서울 / 2 부산 / 3 대전
     0 연결되지 않은 상태, 1은 연결된 상태
     
*/


   [1] = [0,1,1] // 1 서울은 부산과 연결되어 있고, 대전과 연결되어 있음. 
   [2] = [1,0,1] // 2 부산은 서울과 연결되어 있고, 대전과 연결되어 있음.
   [3] = [1,1,0] // 3 대전은 서울과 연결되어 있고, 부산과 연결되어 있음.

 

 

 

** 인접 리스트와 인접 행렬의 선택 방법

인접 리스트

그래프 내의 적은 숫자의 간선만을 가지는 *희소 그래프(아래 주석 참고)인 경우 사용.

 

장점:

* 노드에 인접한 노드들을 쉽게 찾을 수 있다. (연결되어있는 간선의 데이터만 나타내기 때문에 메모리를 적게 차지함.)

* 연결되어 있는 간선의 데이터만 나타내기 때문에 연결되어 있는 모든 노드를 방문하려 할 때 효율적이다.

* 특정 노드의 인접 노드들은 바로 알 수 있다.

 

단점:

* 노드간의 연결 여부를 확인하기 위해서는 모든 노드를 탐색해야해서 비효율적이다.

 

 

 

 

인접 행렬

그래프에 간선이 많이 존재하는 *밀집 그래프(아래 주석 참고) 의 경우 사용.

 

장점:

노드 간의 연결 정보를 바로 알 수 있으며 구현이 쉽다. (두 정점을 연결하는 간선의 존재 여부 M[i][j]를 빠르게 알 수 있다.)

 

단점:

* 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.

 -> (특정 노드 N을 방문하기 위해서 Graph[i][0]부터 Graph[i][N]까지 모두 확인해봐야 하기때문에 비효율적이다.

 

* 모든 노드의 관계를 기록하기 때문에 크기가 커질수록 메모리를 많이 차지한다.

 

 

인접 리스트와 인접 행렬의 선택 방법  결론:

간선이 많고 적음을 근거로 판단하면 된다.

간선이 많을때에는 인접행렬 사용. : 빠르게 연결 여부를 확인 할 수 있기 때문에.

간선이 적을때에는 인접 리스트 사용. : 인접 노드를 빠르게 알 수 있기 때문에.

 

 

 

 

깊이 우선  탐색 DFS(Depth-First Search) 너비 우선  탑색BFS(Breadth-First Search)은 할말도 많고

중요한 내용이기에 다음 포스팅에서 다뤄보도록 하겠다.

 

 

 

 

 

TIL:

그래프의 개념과 특징을 파악했고, 코드로도 직접 작성 해보고 알고리즘 문제도 풀어보았다. ♥

 

 

오늘도 열심히 살았다!! ㅎㅎ

 

 

 

 

 

 

 

 

주석:

희소 그래프(Sparse Graph) : 간선이 얼마 없는 그래프는 희소 그래프.

밀집 그래프(Dense Graph) : 간선의 수가 최대 간선의 수에 가까운 그래프.

 

단어 설명:

정점(Vertex) : 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소이다.

간선(Edge) : 정점 간의 관계를 나타냅니다. (정점을 이어주는 선이다.)

인접(Adjacent): 두 정점 간에 간선이 직접 이어져 있다면 이 두정점은 인접한 정점이다.

인접 정점(Adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻한다.

가중치 그래프(Weighted Graph): 연결의 강도(추가적인 정보가 주어짐)가 얼마나 되는지 적혀있는 그래프

비가중치 그래프(Unweighted Graph): 연결의 강도가 적혀있지 않은 그래프

무(방)향 그래프(Undirected Graph): 서울에서 부산으로 갈 수 있듯이 부산에서도 서울로 갈 수 있다.

   하지만 단방향(Directed) 그래프로 구현된다면 서울에서 부산은 갈 수 있지만 부산에서 서울을 가지는 못한다.

    즉 무방향  ->  양방통행

    단방향  -> 일방통행 으로 이해하면 쉽다.

진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇개인지를 나타낸다.

자기 루프(Self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다.

   다른 정점을 거치지 않는다는것이 특징이다.

사이클(Cycle): 한 정점에서 출발해서 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다라고 표현한다.

   위에 코드블럭에 예시를 적은 네비게이션 그래프는 서울 -> 대전 -> 부산 -> 서울로 이동이 가능하기에 사이클이 존재하      는 그래프 이다.

 

 

 

Tree 구조란?

https://mininkorea.tistory.com/31

Tree 구조 (트리 구조) 자료구조 / 트리 순회 방법 세가지 전위, 중위, 후위 순회 알고리즘 문제

 

 

 

 

 

이미지 출처

https://en.wikipedia.org/wiki/Graph_theory