(비선형 데이터 구조) 그래프

  • by

그래프(Graph)

  • 그래프는 트리의 상위 개념의 데이터 구조로, 정점과 간선으로 구성된다.

  • 연결 정점 간의 관계를 표현할 수 있는 자료 구조이다.

  • 그래프의 용도는 지하철 노선도나 통신 네트워크와 같은 곳에서 사용된다.

그래프에 사용되는 용어


Undirected Graph(왼쪽), Directed Graph(오른쪽)

  • 정점(Vertex): 그래프 구조의 데이터 값을 포함하는 단위(노드)
  • 간선(Edge): 노드 간 연결선(link, branch)
  • 인접 정점(Adjacent vertex) : 간선을 하나 놓고 직결된 정점
  • 정점의 차수: 무방향 그래프의 한 꼭지점에 인접한 꼭지점 수
    • 무방향 그래프 모든 정점 차수의 합계 = 그래프 간선의 수의 2배
  • 진입 차수(In-degree): 방향 그래프에서 외부에서 오는 간선의 수
  • 진출 차수(Out-degree): 방향 그래프에서 밖으로 나오는 간선의 수
  • 경로 길이: 경로를 설정하는 데 사용되는 간선 수
  • 단순 경로(Simple Path): 경로에 반복 정점이 없는 경우
  • 사이클: 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프의 특징과 트리의 차이

그래프 나무
개요 노드와 간선으로 구성된 데이터 구조 그래프의 일종
방향성 방향 그래프와 무방향 그래프 모두 존재 방향 그래프만 존재
사이클 사이클 가능, 자기 간선(Self-Loop) 가능,
순환(Cyclic), 비순환(Acyclic) 그래프 모두 존재		 사이클 불가능, 자기 간선 불가능,
비순환 그래프만 존재
모델 네트워크 모델 계층 모델
루트 노드 루트 노드 X 최상위 노드
부모 – 아이 부모-자식 관계 X 인접한 상하 노드
간선 수 그래프에 따라 간선 수의 차이 N개의 노드로 구성된 트리의 간선수는 N-1개
순회 DFS, BFS DFS(Pre-, In-, Post-Order)/BFS(Level-Order)
경로 둘 이상의 패스 가능 두 노드 사이의 경로는 하나(유일)
예와 유형 노선도, 지도 바이너리 트리, 바이너리 네비게이션 트리, 밸런스 트리(AVL, RB),
이진 힙 (최대 엉덩이, 최소 엉덩이)

그래프 종류


  • 무방향 그래프(Undirected Graph) : 양 정점을 연결하는 간선에 맞지 않는 그래프. (양방향 이동 가능)
  • 방향 그래프(Directed Graph) : 2개의 정점을 연결하는 간선에 방향이 있는 그래프. (방향만 이동 가능)
  • 가중치 그래프(Weighted Graph) : 두 정점을 모두 이동할 때 가중치만큼 비용이 많이 드는 그래프.
  • 완전 그래프(Complete Graph) : 모든 정점이 간선으로 연결되어 있는 그래프.
    • 정점이 N개인 경우, 간선수는 N(N-1)/2이다.


  • 부분 그래프(Subgraph) : 기존 그래프에서 일부 정점이나 간선을 제외하고 생성된 그래프.
  • 유향 비순환 그래프(DAG, Directed Acyclic Graph): 방향 그래프에서 사이클없이 그래프


  • 연결 그래프(Connected Graph) : 떨어진 정점이 없는 그래프
  • 비연결 그래프(Disconnected Graph): 떨어진 정점을 가진 그래프

그래프 탐색

깊이 우선 탐색(Depth First Search = DFS)


DFS 예

인기글

  • 딥 파고드는 형태로 탐색하는 방법이다.

  • 다음 브랜치를 보기 전에 브랜치를 끝까지 탐색해 보세요.
  • visited 배열과 스택으로 구현한다.

  • 모든 노드를 방문하려면 이 방법을 선택합니다.

깊이 우선 탐색은 폭 우선 탐색보다 약간 간단합니다.

너비 우선 탐색(Breath First Search = BFS)


BFS 예

  • 널리(wide) 탐색하는 방법이다.

    (가까운 노드에서 순회)
  • 루트 노드 (시작 노드)에서 인접 노드를 먼저 검색하는 방법입니다.

  • visited 배열과 큐로 구현한다.

  • 두 노드 사이의 최단 경로 또는 임의 경로를 찾으려면 이 방법을 선택하십시오.

그래프 구현

1. 인접 행렬(Adjacency Matrix)


인접 행렬의 예

2차원 배열을 사용하여 만듭니다.

matrix (i) (j)가 0이 아니면 i -> j에 대한 간선이 존재한다는 의미입니다.

가중 그래프가 아닌 경우는 간선이 있으면 1, 없는 경우는 0, 가중 그래프인 경우는 간선이 있으면 해당 간선의 가중치, 없는 경우는 0으로 한다.

무방향 그래프의 경우는 대칭 행렬입니다.

인접 행렬의 장점

  • 간선 정보의 확인과 업데이트가 빠르다.

    (O(1)의 시간 복잡도로 해당 간선 정보를 확인 또는 갱신할 수 있다.

    )
  • 정점의 차수는 O(N)내에서 알 수 있다.

  • 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우에 유용합니다.

인접 행렬의 단점

  • 인접 행렬을 위한 메모리 공간이 더 필요하다.

    간선 수에 관계없이 N^2의 메모리 공간이 필요합니다.

  • 어느 노드에 인접한 노드를 찾으려면 모든 노드를 순회해야 합니다.

  • 그래프에 존재하는 간선의 수는, O(N^2) 내에 알 수 있다.

    (이웃 행렬 전체를 조사한다)

2. 인접 목록(Adjacency List)


인접 목록의 예

연결 목록 (인접 목록)을 사용하여 구현하는 방법입니다.

각 정점에 인접한 정점을 리스트로 둘러쌌다.

무방향 그래프는 각 간선에서 두 번 저장됩니다.

(A -> B, B -> A)

인접 목록의 장점

  • 이점은 메모리 사용량이 비교적 적고,, 노드 추가 삭제도 빠릅니다.

  • 어느 노드의 인접 노드를 빠르게 찾을 수 있습니다.

  • 그래프에 존재하는 모든 간선의 수는 O(N+E) 내에서 알 수 있다.

    (N은 정점(노드)의 수, E는 간선의 수)
  • 그래프에 간선이 적게 존재하는 희소 그래프(Sparse Graph)의 경우에 유용하다.

인접 목록의 단점

  • 간선 정보의 확인은 인접 행렬에 비해 비교적 길다.

    (정점 차수(degree, 인접 노드수)분의 시간이 필요)

인접 행렬, 인접 목록의 복잡도 비교

인접 행렬 인접 목록
특정 간선 검색 O(1) O(degree(V))
정점 차수 계산 O(N) O(degree(V))
모든 노드 네비게이션 O(N^2) O(E)
메모리 N×N N+E

N : 총 정점 수, E : 전체 간선 수, degree : 차수

인접 행렬에 의한 그래프의 구현 (java)

class MyGraphMatrix {
    char() vertices; // 정점(노드) 이름(1차원 배열)
    int()() adjMat; // 인접 행렬(2차원 배열)
    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 dfs(int id){ // id는 시작 정점
        boolean() visited=new boolean(this.elemCnt);
        Stack<Integer> stack=new Stack<>();

        stack.push(id);
        visited(id)=true;
        
        while(!
stack.isEmpty()){
            int curId=stack.pop();
            System.out.println(this.vertices(curId)+ " ");

            for (int i = 0; i < this.elemCnt ; i++) {
                if(this.adjMat(curId)(i)==1 && visited(i)==false){
                    stack.push(i);
                    visited(i)=true;
                }
            }
        }
        System.out.println();
    }

    public void bfs(int id){ // id는 시작 정점
        boolean() visited=new boolean(this.elemCnt);
        Queue<Integer> queue=new LinkedList<>();

        queue.offer(id);
        visited(id)=true;

        while(!
queue.isEmpty()){
            int curId=queue.poll();
            System.out.println(this.vertices(curId)+ " ");

            for (int i = 0; i < this.elemCnt ; i++) {
                if(this.adjMat(curId)(i)==1 && visited(i)==false){
                    queue.offer(i);
                    visited(i)=true;
                }
            }
        }
        System.out.println();
    }
}

인접 리스트에 의한 그래프의 구현 (java)

class Node{
    int id;
    Node next;

    public Node(int id, Node next){
        this.id=id;
        this.next=next;
    }
}

class MyGraphList {
    char vertices();
    Node() adjList;
    int elemCnt;

    public MyGraphList(){}
    public MyGraphList(int size){
        this.vertices=new char(size);
        this.adjList=new Node(size);
        this.elemCnt=0;
    }

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

    public 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.adjList(x)=new Node(y, this.adjList(x));
        this.adjList(y)=new Node(x, this.adjList(y));
    }

    public void addDirectedEdge(int x, int y){
        this.adjList(x)=new Node(y, this.adjList(x));
    }

    public void deleteEdge(int x, int y){
        Node cur=this.adjList(x);
        Node prev=this.adjList(x);
        while(cur.id!
=y){
            prev=cur;
            cur=cur.next;
        }
        prev.next=cur.next;
        cur.next=null;

        cur=this.adjList(y);
        prev=this.adjList(y);
        while(cur.id!
=x){
            prev=cur;
            cur=cur.next;
        }
        prev.next=cur.next;
        cur.next=null;
    }

    public void deleteDirectedEdge(int x, int y){
        Node cur=this.adjList(x);
        Node prev=this.adjList(x);
        while(cur.id!
=y){
            prev=cur;
            cur=cur.next;
        }
        prev.next=cur.next;
        cur.next=null;
    }
    
    public void dfs(int id){
        boolean() visited=new boolean(this.elemCnt);
        Stack<Integer> stack=new Stack();
        
        stack.push(id);
        visited(id)=true;
        
        while(!
stack.isEmpty()){
            int curId=stack.pop();
            System.out.println(this.vertices(curId) + " ");
            
            Node cur=this.adjList(curId);
            while(cur!
=null){
                if(visited(cur.id)==false){
                    stack.push(cur.id);
                    visited(cur.id)=true;
                }
                cur=cur.next;
            }
        }
        System.out.println();
    }
    
    public void bfs(int id){
        boolean() visited=new boolean(this.elemCnt);
        Queue<Integer> queue=new LinkedList<>();

        queue.offer(id);
        visited(id)=true;

        while(!
queue.isEmpty()){
            int curId=queue.poll();
            System.out.println(this.vertices(curId) + " ");

            Node cur=this.adjList(curId);
            while(cur!
=null){
                if(visited(cur.id)==false){
                    queue.offer(cur.id);
                    visited(cur.id)=true;
                }
                cur=cur.next;
            }
        }
        System.out.println();
    }
}