[알고리즘] 그래프와 트리

그래프(Graph)

정점(Vertex)과 간선(Edge)으로 이루어진 자료구조 G = (V, E)

정점 : 데이터 / 간선 (데이터 간의 관계, 방향성)  

 

그래프의 종류

방향그래프 : 간선의 방향 O

무방향 그래프 : 간선의 방향 X

가중치 방향 그래프 : 간선의 가중치

-> 지도상의 위치...

 

그래프 표현

인접행렬

• 2차원 배열을 사용, 그래프의 장점들 간의 연결 관계 표현
• 행렬( i , j ) 위치에 간선의 유무를 나타냄
  • 무방향 - 간선존재 1 / 간선 없음 0
  • 방향그래프 - ( i -> j ) 일 때 간선이 존재하면 1 / 없으면 0
  • 가중치 그래프 - 간선이 존재하면 가중치값 / 없으면 0
• 장점
  • O(1)의 시간복잡도 / 단순한 구조
• 단점
  • O(N^2)의 높은 공간복잡도

=> 정점의 개수가 정해 저 있을 경우 유리함!

class GraphAdjMatrix {
    private int vertices;
    private int[][] adjMatrix;

    public GraphAdjMatrix(int vertices) {
        this.vertices = vertices;
        adjMatrix = new int[vertices][vertices];
    }

    public void addEdge(int src, int dest) {
        adjMatrix[src][dest] = 1;
        adjMatrix[dest][src] = 1;
    }

    public void removeEdge(int src, int dest) {
        adjMatrix[src][dest] = 0;
        adjMatrix[dest][src] = 0;
    }

    public boolean isEdge(int src, int dest) {
        return adjMatrix[src][dest] != 0;
    }
}

 

인접리스트

• 정점에 연결된 다른 정점리스트 표현
• 인접리스트
  • 각 정점에 대해 연결된 정정들의 목록을 저장
  • 각 정점은 리스트를 저장
  • 정점과 연결된 다른 정점들의 참조를 포함
• 장점
  • 공간 효율성이 좋음
  • 인접 정점을 확인하기 좋음
• 단점
  • 두 정점 간의 간선 존재 확인을 위해 O(V)의 시간 복잡도
  • V = 정점의 개수

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class GraphAdjList {
    private int vertices;
    private List<List<Integer>> adjList;

    public GraphAdjList(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new LinkedList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }

    public void removeEdge(int src, int dest) {
        adjList.get(src).remove(Integer.valueOf(dest));
        adjList.get(dest).remove(Integer.valueOf(src));
    }

    public boolean isEdge(int src, int dest) {
        return adjList.get(src).contains(dest);
    }
}

 

그래프의 완전탐색 알고리즘

BFS - 너비우선탐색

(자세히보기)

큐(Queue)를 사용하여 탐색 - 큐에는 좌표가 저장됨

노드 방문 체크 배열이 필요

BFS를 사용해야만 하는 문제

1. 경로가 여려개 일때 최단 경로를 보장

2. 노드간 최단 거리를 구하는 문제

3. 최소 연결 문제

 

 

DFS - 깊이 우선탐색

(자세히보기)

재귀함수 - 스택 오버플로 유의 (스택의 형태를 가지고있음) 

노드 방문 체크 배열이 필요 

검색속도는 BFS에 비해 느림

DFS를 사용 해야만 하는 문제

1. 연결된 구성 요소 찾기/ 미로 탐색 문제 - 현재 노드에서 연결된 모든 애들을 다 보기 위해서 

2. 사이클 검증 : 지나온 길이 다시 최소의 시작점으로 가는지 판단

3. 백트래킹 : 특정 조건 경로 -> 특정 노드 반드시 거칠때

 

 

DFS vs BFS

알고리즘	시간 복잡도 (인접 리스트)	시간 복잡도 (인접 행렬)	공간 복잡도
DFS	O(V+E)	O(V^2)	O(V)
BFS	O(V+E)	O(V^2)	O(V)

 

 

그래프 이용사례

• 네트워크 연결
• 소셜 네트워크 분석
• 경로 찾기 알고리즘

=> 두 가지 중 연결성, 추가, 삭제 등 잘 생각해서 사용해야 한다

 

 

트리(Tree)

그래프의 특별한 형태, 사이클이 없음

루트노드 : 최 상단 노드

리프노드 : 자식노드가 없는 노드

 

트리의 종류

• 이진트리 (Binary Tree) : 최대 자식노드 2개
• 이진 탐색 트리 (Binary Search Tree) : 이진트리값에 순서가 부여된 트리
  • 왼쪽 자식노드 : 부모노드보다 작음
  • 오른쪽 자식노드 : 부모노드보다 큼
  • 
• 균형트리 (Balanced Tree )  : 트리의 리프노드가 같은 레벨이 있도록 구성된 트리
• 힙 (heap) : 특정한 조건을 만족하는 이진트리

 

트리표현

• 인접행렬
• 인접리스트
• 배열
  • 이진트리 표현 가능
  • 루프노드 idx 0번에 저장
  • 노드
    1. 왼쪽 자식 - 배열 (2i+1)
    2. 오른쪽 자식 - 배열(2i +2)

 

트리 이용사례

• 파일 시스템
• 데이터 인덱스
• 컴파일러

 

최소신장트리

신장트리 -> 간선의 가중치 합이 가장 작은 트리

 

크루스칼 알고리즘

모든 정점들을 가장 적은 비용으로 연결하기 위해 사용  간선에 가중치가 포함

모든 정점을 포함하고 사이클이 없는 선을 그렸을 때, 가중치의 합이 최소가 되는 상황

간선을 기준으로

 

프림알고리즘

최소 스패닝 트리 라고 부르는 서브 그래프를 찾는 알고리즘

정점을 중심으로 접근