Prim(프림) 알고리즘

그래프의 모든 정점을 최소 비용으로 연결하는, 즉, 최소 신장 트리를 구현하는 대표적인 Greedy(탐욕) 알고리즘이다.

Greedy 알고리즘

  • 그 순간에 가장 좋다고 생각되는 해를 선택
    • MST에 포함된 정점들과 그렇지 않은 정점들을 잇는 간선중 가장 가중치가 작은 간선을 선택하여 MST에 추가
  • 그 순간에는 최적의 해일 수 있지만, 전체적으로 봤을때는 그렇지 않을 수 있으므로 반드시 검증을 해야함
    • 정점이 이미 선택되어 MST에 포함되어 있는지 검증
  • Kruskal(크루스칼) 알고리즘의 경우는 간선을 선택하는 Greedy 알고리즘이다.

동작방식

  1. 임의의 정점을 출발 정점으로 선택
  2. 매 단계에서 이전단계에 MST에 포함된 정점들과 포함되지 않은 정점들을 잇는 간선 중 가중치가 가장 작은 간선을 선택하여 MST를 확장한다.
  3. 간선개수가 N1이 될 때까지 반복(N: 정잠개수)

Visualize

임의의 정점 a를 선택한다.

 

 

 

 

 

MST에 포함된 정점들(a)과 그렇지 않은 정점들을 잇는 간선들 중에 가중치가 가장 작은 간선 (a,b)를 MST에 추가 

 

 

 

 

 

MST에 포함된 정점들(a,b)과 그렇지 않은 정점들을 잇는 간선 중 가중치가 가장 작은 간선((a,h))를 MST에 추가

 

 

 

 

 

MST에 포함된 정점들(a,b,h)과 그렇지 않은 정점들을 잇는 간선 중 가중치가 가장 작은 간선((h,g))를 MST에 추가

 

 

 

 

 

MST에 포함된 정점들(a,b,h,g)과 그렇지 않은 정점들을 잇는 간선 중 가중치가 가장 작은 간선((g,f))를 MST에 추가

 

 

 

 

 

 

MST에 포함된 정점들(a,b,h,g,f)과 그렇지 않은 정점들을 잇는 간선 중 가중치가 가장 작은 간선((c,f))를 MST에 추가

 

 

 

 

 

MST에 포함된 정점들(a,b,h,g,f,c)과 그렇지 않은 정점들을 잇는 간선 중 가중치가 가장 작은 간선((c,i))를 MST에 추가

 

 

 

 

 

MST에 포함된 정점들(a,b,h,g,f,c,i)과 그렇지 않은 정점들을 잇는 간선 중 가중치가 가장 작은 간선((d,e))를 MST에 추가

 

 

 

 

 

 

모든 정점들이 MST에 포함되어 있고 간선의 개수가 정점 개수 - 1 이므로 끝

 

 

시간 복잡도

간선의 가중치가 최소인 간선 탐색: O(n)

MST에 포함된 정점과 그렇지 않은 정점들 사이의 거리 갱신: O(n)

이것을 정점의 수 만큼 반복하므로 (O(n)+O(n))(n1)=O(n2)

그러나 우선순위 큐(Priority Queue)를 사용하는 경우에는 O(nlgn)이다.

 

코드

class MSTPrim {
  int[][] graph;
  
  public MSTPrim() {
    this.graph = {
      {0, 4, 0, 0, 0, 0, 0, 8, 0},
      {4, 0, 8, 0, 0, 0, 0, 11, 0},
      {0, 8, 0, 7, 0, 4, 0, 0, 7},
      {0, 0, 7, 0, 9, 14, 0, 0, 0},
      {0, 0, 0, 9, 10, 0, 0, 0, 0},
      {0, 0, 4, 14, 10, 0, 2, 0, 0},
      {0, 0, 0, 0, 0, 2, 0, 1, 7},
      {8, 11, 0, 0, 0, 0, 1, 0, 7},
      {0, 0, 2, 0, 0, 0, 6, 7, 0},
    };
  }
  
  public int prim(startVertex) {
    int vertexCount = graph.length;
    int[] distance = new int[vertexCount];
    boolean[] visit = new boolean[vertexCount];
    Arrays.fill(distance, Integer.MAX_VALUE);
    
    int result = 0;
    distance[startVertex] = 0;
    
    for(int i = 0; i < vertexCount; i++) {
      int minDistanceFromMst = Integer.MAX_VALUE;
      int targetVertex = -1;
      for(int j = 0; j < vertexCount; j++) {
        if(!visit[j] && distance[j] < minDistanceFromMst) {
          minDistanceFromMst = distance[j];
          targetVertex = j;
        }
      }
      
      visit[targetVertex] = true;
      result += minDistanceFromMst;
      
      for(int j = 0; j < vertexCount; j++) {
        if(!visit[j] && graph[targetVertex][j] > 0 && graph[targetVertex][j] < distance[j]) {
          distance[j] = graph[targetVertex][j];
        }
      }
    }
    
    return result; 
  }
  
  public int prim_using_priority_queue(startVertex) {
    int vertexCount = graph.length;
    boolean[] visit = new boolean[vertexCount];
    // int[] -> {destination, weight}
    PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]);
    
    queue.add(new int[]{startVertex, 0})
    int result = 0;
    
    while(!queue.isEmpty()) {
      int[] current = queue.poll();
      int destination = current[0];
      int weight = current[1];
      if(visit[destination]) {
        continue;
      }
      
      visit[destination] = true;
      result += weight;
      
      for(int i = 0; i < vertexCount; i++) {
        if(!visit[i] && graph[destination][i] > 0) {
          queue.add(new int[]{i, graph[destination][i]};
        }
      }
    }
    
    return result; 
  }
}

 

같이 볼 자료

2022.01.16 - [Algorithm] - [Algorithm] MST (Minimum Spanning Tree, 최소 신장 트리)

 

[Algorithm] MST (Minimum Spanning Tree, 최소 신장 트리)

신장 트리 (Spanning Tree) 그래프의 모든 정점을 연결하는 트리 트리: 일반적으로 계층구조의 자료구조를 생각하는데, 그래프 이론에서 사이클이 없는 무방향 그래프를 트리라고 한다. 그래프가 n

jino-dev-diary.tistory.com

2022.01.16 - [Algorithm] - [Algorithm] Krsukal (크루스칼) 알고리즘

 

[Algorithm] Krsukal (크루스칼) 알고리즘

Kruskal (크루스칼) 알고리즘 그래프의 모든 정점을 최소 비용으로 연결하는, 즉, 최소 신장 트리를 구현하는 대표적인 Greedy(탐욕) 알고리즘이다. Greedy 알고리즘 그 순간에 가장 좋다고 생각되는

jino-dev-diary.tistory.com

 

Kruskal (크루스칼) 알고리즘

그래프의 모든 정점을 최소 비용으로 연결하는, 즉, 최소 신장 트리를 구현하는 대표적인 Greedy(탐욕) 알고리즘이다.

Greedy 알고리즘

  • 그 순간에 가장 좋다고 생각되는 해를 선택
    • 정렬 된 간선 중 가중치가 가장 작은 간선부터 차례대로 선택
  • 그 순간에는 최적의 해일 수 있지만, 전체적으로 봤을때는 그렇지 않을 수 있으므로 반드시 검증을 해야함
    • 이미 선택된 간선인지, 사이클을 형성하는지 검증
  • Prim(프림) 알고리즘의 경우는 정점을 선택하는 Greedy 알고리즘이다.

 

동작방식

  1. 그래프의 간선들을 오름차순으로 정렬한다.
  2. 정렬된 간선들을 차례대로 선택한다.
  3. 단, 이미 선택된 간선과 사이클을 형성하는 간선은 패스
  4. 간선의 개수가 N1개가 될 때까지 반복한다 (N: 정점 개수)

 

Visualize

처음은 어떠한 정점들도 선택되지 않은 상태, 간선들을 오름차순 정렬

 

 

 

 

 

정렬된 간선을 차례대로 선택하여 MST에 추가한다. 간선 (g,h)를 추가하고 정점 g,h를 같은 집합으로 합친다.

 

 

 

 

 

간선 (c,i)를 추가하고 정점 c와 i를 같은 집합으로 합친다.

 

 

 

 

 

간선 (g,f)를 추가하고 정점 f와 g를 같은 집합으로 합친다.

 

 

 

 

 

간선 (a,b)를 추가하고 정점 a와 b를 같은 집합으로 합친다.

 

 

 

 

 

간선 (c,f)를 추가하고 정점 c와 f를 같은 집합으로 합친다.

 

 

 

 

 

간선 (g,i)를 추가하려고 하는데.. 정점 g와 i는 이미 같은 집합이다. 만약 간선 (g,i)를 추가하면 사이클이 형성된다. 그러므로 그냥 패스

 

 

 

 

 

간선 (c,d)를 추가하고 정점 c와 d를 같은 집합으로 합친다.

 

 

 

 

 

간선 (h,i)를 추가하려고 하는데.. 정점 h와 i는 이미 같은 집합이다. 만약 간선 (h,i)를 추가하면 사이클이 형성된다. 그러므로 그냥 패스

 

 

 

 

 

간선 (a,h)를 추가하고 a와 h를 같은 집합으로 합친다.

 

 

 

 

 

간선 (b,c)를 추가하려고 하는데... b와 c는 이미 같은 집합이다. 만약 간선 (b,c)를 추가한다면 사이클이 형성된다. 그러므로 그냥 패스

 

 

 

 

 

간선 (d,e)를 추가하고 정점 d와 e를 같은 집합으로 합친다.

 

 

 

 

 

모든 정점들이 같은 집합이고, MST에 추가된 간선이 정점 개수 - 1이므로 끝

 

 

 

 

 

 

 

사이클을 형성하는 지 검증할 때 Union-Find 알고리즘을 사용한다

 

시간복잡도

Union-Find 알고리즘을 사용하면 간선들을 정렬하는 시간에 영향받는다.

즉, 간선 E개를 Quick Sort의 효율로 정렬한다면 O(ElogE)이다.

 

코드

class MSTKruskal {
  int[] parents;
  int[][] graph;
  
  public MSTKruskal() {
    this.graph = {
      {0, 4, 0, 0, 0, 0, 0, 8, 0},
      {4, 0, 8, 0, 0, 0, 0, 11, 0},
      {0, 8, 0, 7, 0, 4, 0, 0, 7},
      {0, 0, 7, 0, 9, 14, 0, 0, 0},
      {0, 0, 0, 9, 10, 0, 0, 0, 0},
      {0, 0, 4, 14, 10, 0, 2, 0, 0},
      {0, 0, 0, 0, 0, 2, 0, 1, 7},
      {8, 11, 0, 0, 0, 0, 1, 0, 7},
      {0, 0, 2, 0, 0, 0, 6, 7, 0},
    }
  }
  
  public int kruskal() {
    int[][] edges = buildEdges();
    makeSet();
    int result = 0;
    
    for(int i = 0; i < edges.lengh; i++) {
      int source = edges[i][0];
      int destination = edges[i][1];
      int weight = edges[i][2];
      
      if(find(source) != find(destination)) {
        union(source, destination);
        result += weight;
      }
    }
    
    return result;
  }
  
  public int[][] buildEdges() {
    int[][] edges = new int[][]{};
    index = 0;
    
    for(int i = 0; i < graph.length; i++) {
      for(int j = 0; j < graph.length; j++) {
        if(graph[i][j] !=0) {
          edges[index++] = {i, j, graph[i][j]};
          edges[index++] = {j, i, graph[j][i]};
        }
      }
    }
    
    return edges;
  }
  
  public void makeSet() {
    this.parents = new int[graph.length];
    
    for(int i = 0; i < graph.lenght; i++) {
      parents[i] = i;
    }
  }
  
  public int find(x) {
    if(parents[x] == x) {
      return x;
    }
    
    return parents[x] = find(parents[x]);
  }
  
  public int union(x, y) {
    x = find(x);
    y = find(y);
    
    if(x == y) {
      return;
    }
    
    if(x > y) {
      parents[y] = x;
    } else {
      parents[x] = y;
    }
    
  }
}

 

같이 볼 자료

2022.01.16 - [Algorithm] - [Algorithm] MST (Minimum Spanning Tree, 최소 신장 트리)

 

[Algorithm] MST (Minimum Spanning Tree, 최소 신장 트리)

신장 트리 (Spanning Tree) 그래프의 모든 정점을 연결하는 트리 트리: 일반적으로 계층구조의 자료구조를 생각하는데, 그래프 이론에서 사이클이 없는 무방향 그래프를 트리라고 한다. 그래프가 n

jino-dev-diary.tistory.com

2022.01.16 - [Algorithm] - [Algorithm] Prim(프림) 알고리즘

 

[Algorithm] Prim(프림) 알고리즘

Prim(프림) 알고리즘 그래프의 모든 정점을 최소 비용으로 연결하는, 즉, 최소 신장 트리를 구현하는 대표적인 Greedy(탐욕) 알고리즘이다. Greedy 알고리즘 그 순간에 가장 좋다고 생각되는 해를 선

jino-dev-diary.tistory.com

 

신장 트리 (Spanning Tree)

  • 그래프의 모든 정점을 연결하는 트리
  • 트리: 일반적으로 계층구조의 자료구조를 생각하는데, 그래프 이론에서 사이클이 없는 무방향 그래프를 트리라고 한다.
  • 그래프가 n개의 정점을 가질 때, 그래프의 최소 간선의 수는 n-1개이다.
  • 하나의 그래프에서 여러개의 신장 트리가 존재할 수 있다.

 

 

 

 

 

최소 신장 트리 (Minimum Spanning Tree)

  • Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
  • Spanning Tree와 마찬가지로 정점이 N개일 때, N-1개의 간선으로 연결된다.
  • Spanning Tree와 마찬가지로 사이클이 없다.
  • Spanning Tree와 마찬가지로 MST의 해가 여러개 일 수 있다.

 

MST을 구현하는 알고리즘으로 Kruskal(크루스칼) 알고리즘과 Prim(프림) 알고리즘이 있다.

2022.01.16 - [Algorithm] - [Algorithm] Krsukal (크루스칼) 알고리즘

 

[Algorithm] Krsukal (크루스칼) 알고리즘

Kruskal (크루스칼) 알고리즘 그래프의 모든 정점을 최소 비용으로 연결하는, 즉, 최소 신장 트리를 구현하는 대표적인 Greedy(탐욕) 알고리즘이다. Greedy 알고리즘 그 순간에 가장 좋다고 생각되는

jino-dev-diary.tistory.com

 

2022.01.16 - [Algorithm] - [Algorithm] Prim(프림) 알고리즘

 

[Algorithm] Prim(프림) 알고리즘

Prim(프림) 알고리즘 그래프의 모든 정점을 최소 비용으로 연결하는, 즉, 최소 신장 트리를 구현하는 대표적인 Greedy(탐욕) 알고리즘이다. Greedy 알고리즘 그 순간에 가장 좋다고 생각되는 해를 선

jino-dev-diary.tistory.com

 

그래프 순회

  • 그래프에서 임의의 한 정점에서 출발하여 모든 정점을 한번씩 방문하는 작업
  • 탐색하는 동안 이미 방문한 정점이 있을 수 있으므로 방문했다는 표시를 하여 중복방문을 피한다.
  • 대표적으로 DFS, BFS가 있다.

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

  • 출발노드에서 인접한 노드(형제노드)를 먼저 탐색하는 방식
  • 가중치가 없는 그래프에서 최단경로를 찾을 때 사용한다.
  • 일반적으로 Queue를 이용하여 구현한다.

동작방식

  1. 시작정점을 방문하여 큐에 삽입한다.
  2. 큐에서 정점을 꺼내 정점에서 인접한 정점중, 방문하지 않은 정점들을 방문하여 큐에 삽입한다.
  3. 모든 정점을 반복할 때까지 반복한다.

Visualize

E노드에서 더이상 간선이 없으므로 그냥 큐에서 꺼내는것으로 끝이다

G노드에서 더이상 간선이 없으므로 그냥 큐에서 꺼내는것으로 끝이다. H노드와 I노드도 마찬가지이다.

 

코드

의사코드

BFS(graph, start_node) {
  Queue q;
  boolean[] visit;
  
  q.add(start_node);
  visit[start_node] = true;
  
  while(!q.isEmpty()) {
    current_node = q.pop();
    for(adjacent_node to current_node) {
      if(!visit[adjacent_node]) {
        visit[adjacent_node] = true;
        q.add(adjacent_node);
      }
    }
  }
}

코드 - Queue (Java)

class BFS_Queue {
  private int[][] graph;
  private boolean[] visit;
  
  public BFS_Queue() {
    this.graph = {
      {0, 1, 1, 1, 0, 0, 0, 0, 0},
      {1, 0, 0, 0, 1, 0, 0, 0, 0},
      {1, 0, 0, 0, 0, 1, 1, 0, 0},
      {1, 0, 0, 0, 0, 0, 0, 1, 0},
      {0, 1, 0, 0, 0, 0, 0, 0, 0},
      {0, 0, 1, 0, 0, 0, 0, 0, 1},
      {0, 0, 1, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 1, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 1, 0, 0, 0},
    };
    this.visit = new boolean[graph.length];
  }
  
  public void bfs(startNode) {
    Queue<Integer> queue = new LinkedList();
    
    queue.add(startNode);
    visit[startNode] = true;
    
    while(!queue.isEmpty()) {
      int currentNode = queue.poll();
      
      for(int i = 0; i < graph[currentNode].length; i++) {
        if(isAdjacentNode(currentNode, i) && !visit[i]) {
          visit[i] = true;
          queue.add(i);
        }
      }
    }
  }
  
  public boolean isAdjacentNode(int currentNode, int targetNode) {
    return graph[currentNode][targetNode] == 1;
  }
}

시간 복잡도

  • 인접 리스트: O(N+E) (N: 정점 개수, E: 간선 개수)
  • 인접 행렬: O(N2)

참고

2021.04.14 - [Algorithm] - [Algorithm] 그래프 (Graph)

 

[Algorithm] 그래프 (Graph)

참고1 : 유튜브 (권오흠 교수, 2015 봄학기 알고리즘) 참고2 : (다양한 예제로 학습하는) 데이터 구조와 알고리즘 for java 1. 그래프 : G = (V, E) 1. 정의 V : 정점(Vertex) 또는 노드(Node)들의 집합 E : 간선,..

jino-dev-diary.tistory.com

2022.01.08 - [Algorithm] - [Algorithm] DFS (Depth-First-Search, 깊이 우선 탐색)

 

[Algorithm] DFS (Depth-First-Search, 깊이 우선 탐색)

그래프 순회 그래프에서 임의의 한 정점에서 출발하여 모든 정점을 한번씩 방문하는 작업 탐색하는 동안 이미 방문한 정점이 있을 수 있으므로 방문했다는 표시를하여 중복방문을 피한다. 대표

jino-dev-diary.tistory.com

 

그래프 순회

  • 그래프에서 임의의 한 정점에서 출발하여 모든 정점을 한번씩 방문하는 작업
  • 탐색하는 동안 이미 방문한 정점이 있을 수 있으므로 방문했다는 표시를하여 중복방문을 피한다.
  • 대표적으로 DFS와 BFS가 있다.

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

  • 출발노드에서 하위노드(자식노드)를 먼저 탐색하는 방식
  • 일반적으로 Stack이나 Recursive를 이용하여 구현한다.

동작방식

  1. 시작노드에서 간선을 따라 다음노드로 방문한다.
  2. 더이상 탐색할 간선이 없다면 역추적(Backtracking)을 통해 이전노드로 이동하여 아직 탐색하지 않은 간선을 참색한다.
  3. 모든 노드를 탐색할 때까지 반복한다.

Visualize

E노드에서 더이상 이동 할 간선이 없으므로 역추적으로 통해 B노드로 이동, B노드에서도 마찬가지로 더이상 이동할 간선이 없으므로 A노드로 이동 후 다음 간선인 (A,C)을 통해 C노드로 이동

F노드에서 더이상 이동할 간선이 없으므로 역추적을 통해 C노드로 이동, C노드에서 다음 간선인 (C,G)을 통해 G노드로 이동

I노드에서 더이상 이동할 간선이 없으므로 역추적을 통해 G노드로 이동, G노드에서도 마찬가지로 C노드로 이동, C노드에서도 마찬가지로 A노드로 이동, A노드에서 다음 간선인 (A,D)를 통해 D노드로 이동

 

코드

의사코드

DFS(graph, current_node, visit) {
  visit[current_node] = true
  
  for( adjacent_node to current_node) {
    if(!visit[adjacent_node]) {
      DFS(graph, adjacent_node, visit)
    }
  }
}

코드 - Recursive (Java)

class DFS_Recursive {

  private int[][] graph;
  
  private boolean[] visit;
  
  public DFS_Recursive() {
    this.graph = {
      {0, 1, 1, 1, 0, 0, 0, 0, 0},
      {1, 0, 0, 0, 1, 0, 0, 0, 0},
      {1, 0, 0, 0, 0, 1, 1, 0, 0},
      {1, 0, 0, 0, 0, 0, 0, 1, 0},
      {0, 1, 0, 0, 0, 0, 0, 0, 0},
      {0, 0, 1, 0, 0, 0, 0, 0, 1},
      {0, 0, 1, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 1, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 1, 0, 0, 0},
    };
    visit = new boolean[graph.length];
  }
  
  public void dfs(currentNode) {
    visit[currentNode] = true;
    
    for(int i = 0; i < graph[currentNode].length; i++) {
      if(isAdjacentNode(currentNode, i) && !visit[i]) {
        dfs(i);
      }
    }
  }
  
  public boolean isAdjacentNode(int currentNode, int targetNode) {
    return graph[currentNode][targetNode] == 1;
  }

}

코드 - Stack

class DFS_Stack {

  private int[][] graph;
  
  private boolean[] visit;
  
  public DFS_Stack() {
    this.graph = {
      {0, 1, 1, 1, 0, 0, 0, 0, 0},
      {1, 0, 0, 0, 1, 0, 0, 0, 0},
      {1, 0, 0, 0, 0, 1, 1, 0, 0},
      {1, 0, 0, 0, 0, 0, 0, 1, 0},
      {0, 1, 0, 0, 0, 0, 0, 0, 0},
      {0, 0, 1, 0, 0, 0, 0, 0, 1},
      {0, 0, 1, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 1, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 1, 0, 0, 0},
    };
    visit = new boolean[graph.length];
  }
  
  public void dfs(startNode) {
    Stack<Integer> stack = new Stack();
    
    stack.push(startNode);
    visit[startNode] = true;
    
    while(!stack.isEmpty()) {
      int currentNode = stack.pop();
      
      for(int i = 0; i < graph[currentNode].length; i++) {
        if(isAdjacentNode(i) && !visit[i]) {
          stack.push(i);
          visit[i] = true;
        }
      }
    }
  }
  
  public boolean isAdjacentNode(int currentNode, int targetNode) {
    return graph[currentNode][targetNode] == 1;
  }

}

시간복잡도

  • 인접 리스트: O(N+E) (N: 정점 개수, E: 간선 개수)
  • 인접 행렬: O(N2)

참고

2021.04.14 - [Algorithm] - [Algorithm] 그래프 (Graph)

 

[Algorithm] 그래프 (Graph)

참고1 : 유튜브 (권오흠 교수, 2015 봄학기 알고리즘) 참고2 : (다양한 예제로 학습하는) 데이터 구조와 알고리즘 for java 1. 그래프 : G = (V, E) 1. 정의 V : 정점(Vertex) 또는 노드(Node)들의 집합 E : 간선,..

jino-dev-diary.tistory.com

2022.01.08 - [Algorithm] - [Algorithm] BFS (Breath-First-Search, 너비 우선 탐색)

 

[Algorithm] BFS (Breath-First-Search, 너비 우선 탐색)

그래프 순회 그래프에서 임의의 한 정점에서 출발하여 모든 정점을 한번씩 방문하는 작업 탐색하는 동안 이미 방문한 정점이 있을 수 있으므로 방문했다는 표시를 하여 중복방문을 피한다. 대

jino-dev-diary.tistory.com

 

참고1 : 유튜브 (권오흠 교수, 2015 봄학기 알고리즘)

참고2 : (다양한 예제로 학습하는) 데이터 구조와 알고리즘 for java


1. 그래프 : G = (V, E)

1. 정의

  • V : 정점(Vertex) 또는 노드(Node)들의 집합
  • E : 간선,에지(Edge) 또는 링크(Link)라고 불리는 정점들의 쌍의 집합
  • G = (V, E)

2. 종류

  • 무방향(undirected) 그래프 vs 방향(directed) 그래프
    • 방향이 없는 그래프 vs 방향이 있는 그래프
    • (u, v) == (v, u) vs (u, v) != (v,u)
    • vs
  • 가중치 그래프(Weight Graph)
  • 방향, 무방향 그래프에 관계없이 각 간선에 가중치(weight) 혹은 비용(cost)이 할당된 그래프

3. 용어

  • 인접 정점 or 인접 노드 : 간선에 의해 연결된 정점
  • 차수(degree) : 정점에 연결된 다른 정점의 개수
    • 진입 차수(in-degree) : 방향 그래프에서 외부 노드에서 들어오는 간선의 수
    • 진출 차수(out-degree) : 방향 그래프에서 외부 노드로 나가는 간선의 수
  • 연결 그래프(connected Graph)
    • 무방향 그래프에서 두 노드 사이를 연결하는 경로(path)가 존재할 때 두 정점은 서로 연결되어 있다고 한다.
    • 그래프 안의 모든 정점이 연결되어 있을때 연결된 그래프라고 한다
    • 연결 요소
    • {a,b,c,d}, {e,f}, {g,h,i}로 3개이다.

2. 그래프의 표현

1. 인접 행렬

  • 인접 행렬 (무방향 그래프)
    • 두 정점 사이에 간선이 있을경우 1, 없을 경우 0으로 표현한다.
      • 가중치 그래프의 경우 0,1 대신 가중치로 표현한다.
    • 무방향 그래프의 경우 자기 자신을 기준으로 대칭이다. (A, B) == (B, A)
      • 방향 그래프의 경우 비대칭이다.
    • 저장공간 : O(n^2)
    • 어떤 노드 v에 인접한 모든 노드를 찾을 때 걸리는 시간 : O(n)
    • 어떤 간선 (u,v)가 존재하는지 검사할때 걸리는 시간 : O(1)
  • 간단한 구현 코드 (무방향 그래프)
public class Graph {
    int[][] adjMatrix;
    int vertexCount;

    public Graph(int count) {
        vertexCount = count;
        adjMatrix = new int[vertexCount][vertexCount];
    }

    public void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1;
    }

    public void removeEdge(int u, int v) {
        adjMatrix[u][v] = 0;
        adjMatrix[v][u] = 0;
    }

    public List<Integer> findAdjVertex(int u) {
        ArrayList<Integer> adjVertexList = new ArrayList<>();
        for(int i = 0; i<adjMatrix.length; i++) {
            if(adjMatrix[u][i] == 1) {
                adjVertexList.add(i);
            }
        }
        return adjVertexList;
    }

    public boolean isEdge(int u, int v) {
        return adjMatrix[u][v] == 1;
    }
}

2. 인접 리스트

  • 인접 리스트 (무방향 그래프)
    • 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 리스트
    • 두 정점 사이에 간선이 있을 경우 리스트에 추가한다 (순서는 상관없다)
    • 저장 공간 : O(n+m)
      • n은 정점개수, m은 간선 개수이다.
      • 무방향 그래프의 경우 2m, 방향 그래프의 경우 m이지만, Big - O 표기법에서는 O(n+m)이다.
    • 어떤 노드 v에 인접한 모든 노드를 찾을 때 걸리는 시간 : O(degree(v))
      • v에 해당하는 리스트의 길이이다.
    • 어떤 간선 (u,v)가 존재하는지 검사할 때 걸리는 시간 : O(degree(u))
      • u에 대한 연결 리스트를 돌면서 v가 있는지 확인한다.
  • 간단한 구현코드 (무방향 그래프)
public class Graph {
	List<Integer>[] adjList;
    int vertexCount;
    
    public Graph(int count) {
    	vertexCount = count;
        adjList = new List[vertexCount];
        for(int i = 0; i<vertexCount; i++) {
        	adjList[i] = new ArrayList<>();
        }
    }
    
    public addEdge(int u, int v) {
    	adjList[u].add(v);
        adjList[v].add(u);
    }
    
    public removeEdge(int u, int v) {
    	adjList[u].remove(adjList[u].indexOf(v));
        adjList[v].remove(adjList[v].indexOf(u));
    }
    
    public List<Integer> findAdjVertex(int u) {
    	return adjList[u];
    }
    
    public boolean isEdge(int u, int v) {
    	for(int i = 0; i < adjList[u].size(); i++) {
        	if(adjList[u].get(i) == v) {
            	return true;
            }
        }
        return false;
    }

}

+ Recent posts