4. 그래프 (Graph)

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링

---

*비선형 자료 구조 : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조

 

◆  그래프 (Graph)

- 정점(Vertex)과 간선(Edge)으로 연결 되어 있는 원소들의 관계를 표현한 자료 구조

무방향 그래프

- 예시 : 위와 같은 구조에서 A,B,H,D,G,F,E == 정점(Vertix),  정점들 사이를 잇는 선 == 간선(Edge) 

- G = (V,E)로 정의, V는 정점의 집합, E는 간선들의 집합

- 무방향 그래프 : 간선의 방향이 정해져있지 않은 그래프

- 단방향 그래프 : 간선의 방향이 한 방향으로만 설계되있는 그래프

단방향 그래프

-  양방향 그래프 : 간선의 방향이 양 방향으로 설계 되있는 그래프

양방향 그래프

-  진출 차수 (out-degree) : 어떠한 정점을 기준으로 해당 정점으로부터 나가는 간선의 갯수

                ex) 위 그래프에서 B의 out-degree == 3 (B->A, B->D, B->G)

- 진입 차수 (in-degree) : 어떠한 정점을 기준으로 해당 정점으로 들어오는 간선의 갯수

               ex) 위 그래프에서 A의 in-degree ==  2 (B->A, H->A)

 -  가중치 (Weight) : 어떠한 정점과 정점 사이에 드는 비용 ( 정점 사이의 거리 )

              ex) 위 그래프에서 A-B 가중치 :  3, G-E 가중치 : 2 

- 경로 : 어떠한 한 개의 정점에서 다른 한개의 정점에 이르는 순서

- 단순 경로(Simple Path) : 한 경로상에 있는 모든 정점들이 서로 다른 경로

             ex) 위 그래프에서 A->G 의 단순경로 : A B G, A H G 등

- 사이클 (Cycle) : 처음과 끝의 경로가 같은 단순 경로

            ex) 위 그래프에서 A-B-G-H-A는 사이클이 된다.

- 인접 행렬(adjacency matrix) , 인접 다중 리스트 (adjacency multilist), 역 인접 리스트 (inverse adjacency list) 등으로 표현

- 그래프의 응용 : 최단 경로 찾기, 운영체제의 프로세스 관리, 조합론, 인공지능 등등

---

◆  그래프 표현

- 그래프를 인접행렬, 인접 리스트, 인접 다중 리스트, 역 인접 리스트 등으로 표현

- 인접 행렬 (adjacency matrix) 

           : 그래프의 경로를 2차원 행렬로 표시

           : 임의의 정점 A, B로 이동할 때 간선이 존재하면 1, 간선이 존재하지 않으면 0

             ( 즉, 인접하면 1, 인접하지 않으면 0)

양방향 그래프

           : 위의 그래프를 정점간의 인접관계에 따라 행렬로 표현하면 아래와 같다.

          : 방향 그래프에서 어떠한 정점의 행들의 합 == i의 outdegree )

          : 방향 그래프에서 어떠한 정점의 열들의 합 == i의 indegree )

          : A~H 까지 각각 0~7번까지의 2차원 배열 형태의 행렬로 선언

public class Main {

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        
    	// 왜 C가 없지????ㅋㅋㅋㅋㅋㅋ
    	// 가로와 세로 A,B,D,E,F,G,H
    	int[][] narrGraph = new int[7][7];
    	
    	
    	narrGraph[0][1] = 1;	// A to B
    	narrGraph[0][6] = 1;	// A to H
    	narrGraph[1][0] = 1;	// B to A
    	narrGraph[1][2] = 1;	// B to D
    	narrGraph[1][5] = 1;	// B to G
    	narrGraph[2][1] = 1;	// D to B
    	narrGraph[3][5] = 1;	// E to G
    	narrGraph[4][6] = 1;	// F to H
    	narrGraph[5][1] = 1;	// G to B
    	narrGraph[5][3] = 1;	// G to E
    	narrGraph[5][6] = 1;	// G to H
    	narrGraph[6][0] = 1;	// H to A
    	narrGraph[6][4] = 1;	// H to F
    	narrGraph[6][5] = 1;	// H to G
    	
    	// 그래프 경로를 표현한 인접 행렬 출력
    	for(int i = 0; i < 7; i++) {
    		for(int j = 0; j < 7; j++) {
    			System.out.print(narrGraph[i][j] + " ");
    		}
    		System.out.println();
    	}
        
        /*
        0 1 0 0 0 0 1 
        1 0 1 0 0 1 0 
        0 1 0 0 0 0 0 
        0 0 0 0 0 1 0 
        0 0 0 0 0 0 1 
        0 1 0 1 0 0 1 
        1 0 0 0 1 1 0 
        */
    }
}

---

참고로 책 내용은 이렇게 상세하지 않습니다!! 인접 리스트 또한 가능한 빠른 시일 내에 구현하여 글을 추가로 수정이나 작성해보도록 하겠습니다.

 위의 글과 관련하여 추가적인 내용이나 피드백은 언제나 환영입니다 :)