[Data Structure 기초] 그래프

그래프 (Graph)

- 정점과 간선으로 이루어진 자료구조 (Cyclic)

- 연결된 정점간의 관계를 표현할 수 있는 자료구조

- 그래프의 용도 : 지하철 노선도, 통신 네트워크 등

 

그래프 구조 용어
정점 (Vertex)	각 노드
간선 (Edge)	노드와 노드를 연결하는 선 ( link, branch )
인접 정점 (Adjacent vertex)	간선 하나를 두고 바로 연결된 정점
정점의 차수 (Degree)	- 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배
진입 차수 (In-degree)	방향 그래프에서 외부에서 오는 간선의 수
진출 차수 (Out-degree)	방향 그래프에서 외부로 나가는 간선의 수
경로 길이 (Path length)	경로를 구성하는데 사용된 간선의 수
단순 경로 (Simple path)	경로 중에서 반복되는 정점이 없는 경우
사이클 (Cycle)	단순 경로의 시작 정점과 끝 정점이 동일한 경우

 

 

 

그래프의 종류 

- 무방향 그래프 (Undirected Graph)

간선에 방향이 없는 그래프 (양방향 이동 가능), 정점 A - B 간선의 표현 : (A, B) = (B, A)

 

- 방향 그래프 (Directed Graph)

간선에 방향이 있는 그래프 (해당 방향으로만 이동 가능), 정점 A -> B 간선 : <A, B> ≠ <B, A>  

 

- 가중치 그래프 (Weighted graph)

간선에 값이 있는 그래프 (이동 비용)

 

- 완전 그래프 (Complete graph)

모든 정점이 서료 연결되어 있는 그래프, 정점이 N개일 경우, 간선의 수는 n(n-1)/2개

Complete&nbsp;graph

 

그래프 탐색 

1. 깊이 우선 탐색 (Depth First Search) , DFS

- 각 노드에 방문했는지 여부를 체크할 배열과 스택(Stack) 또는 재귀함수를 이용하여 구현

- 탐색 과정 현재 정점에서 갈 수 있는 끝까지 방문하며 탐색
- 각 경로마다 특징을 저장해야할 때 유리

 

2. 너비 우선 탐색 (Breadth First Search) , BFS

- 각 노드에 방문했는지 여부를 체크할 배열과 큐(Queue)를 이용하여 구현

- 현재 정점에 연결된 가까운 점들부터 탐색
- 최단 거리를 구할 때 유리

 

BFS와 DFS 비교

그래프 구현

인접 행렬 (Adjacency Matrix)

- 2차원 배열 이용

- 간선 정보의 확인과 업데이트가 빠름 , O(1)

- 인접 행렬을 위한 메모리 공간 차지

- 노드의 개수가 적고 간선의 수가 많을 때 유리. 밀집 그래프 (Dense Graph)

 

인접 리스트 (Adjacency List)

- Linked List 이용

- 메모리 사용량이 상대적으로 적고, 노드의 추가 삭제 빠름

- 간선 정보 확인이 상대적으로 오래 걸림

- 노드의 개수가 많고 간선의 수가 적을 때 유리. 희소 그래프 (Sparse Graph)

 

인접행렬와 인접리스트 비교

 

 

// 비선형 자료구조 - 그래프
// 인접 정렬을 이용한 그래프 구현

class MyGraphMatrix{
    char[] vertices;
    int[][] adjMat;
    int elemCnt;
    public MyGraphMatrix(){}
    public MyGraphMatrix(int size){
        this.vertices = new char[size];
        this.adjMat = new int[size][size];
        this.elemCnt = 0;
    }

    public boolean isFull(){
        return this.elemCnt == this.vertices.length;
    }

    public void addVertex(char data){
        if(isFull()){
            System.out.println("Graph is full!");
            return;
        }

        this.vertices[this.elemCnt++] = data;
    }

    public void addEdge(int x, int y){
        this.adjMat[x][y] = 1;
        this.adjMat[y][x] = 1;
    }

    public void addDirectedEdge(int x, int y){
        this.adjMat[x][y] = 1;
    }

    public void deleteEdge(int x, int y){
        this.adjMat[x][y] = 0;
        this.adjMat[y][x] = 0;
    }

    public void deleteDirectedEdge(int x, int y){
        this.adjMat[x][y] = 0;
    }

    public void printAdjacentMatrix(){
        System.out.print("  ");
        for (char item : this.vertices){
            System.out.print(item + " ");
        }
        System.out.println();

        for (int i = 0; i < this.elemCnt; i++) {
            System.out.print(this.vertices[i] + " ");
            for (int j = 0; j < this.elemCnt; j++) {
                System.out.print(this.adjMat[i][j] + " ");
            }
            System.out.println();
        }
    }
}

public class graph {
    public static void main(String[] args) {
        MyGraphMatrix graph = new MyGraphMatrix(4);

        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);

        graph.printAdjacentMatrix();

    }
}

 

 

 

참고link

https://cm-me0410.tistory.com/78

그래프(Graph)의 종류

https://iq.opengenus.org/dfs-vs-bfs/

DFS vs BFS (in detail)