[1128] 자바 - Graph (그래프)

#그래프

- 그래프의 정의

  ▪ 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조

  ▪ 컴퓨터에서 표현하는 그래프는 XY축을 기준으로 한 그래프와 달리 복잡한 네트워크망과 같은 모습이다.

 

- 그래프의 구조

• 직접 관계에 있는 두 점은 사이에 이어진 선이 있다.
• 간접 관계이 있는 두 점은 다른 점과 선을 거쳐 이어진다.
• 하나의 점을 정점(vertex), 하나의 선은 간선(edge)라고 한다.

3개의 정점과 3개의 간선이 있는 그래프

 

- 그래프의 표현 방식

1. 인접 행렬
   직접 관계에 있는 두 정점을 인접한다고 말하는데, 인접행렬은 서로 다른 정점들이 인접한 상태를 2차원 배열의 형태에 표시한다. 

         위 그래프를 인접행렬로 표현한다면 다음과 같다.

int[][] arr = new int[][] {
    {0, 1, 0},
    {0, 0, 1},
    {1, 1, 0}
    };

     

    2. 인접 리스트
        인접 리스트는 각 정점이 어떤 정잠과 인접하는지를 리스트의 형태로 표현한다. 
        각 정점마다 하나의 리스트를 가지며, 이 리스트는 자신과 인접한 다른 정점을 담는다.
        인접 리스트는 인접 행렬보다 메모리를 효율적으로 사용한다. (인접 행렬은 연결 가능한 모든 경우의 수를 저장)

그래프를 인접 리스트로 표현

        위의 그래프를 인접 리스트로 표시하면, 다음과 같다.

// A, B, C를 각각의 인덱스로 표시. A = 0, B = 1, C = 2

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    graph.add(new ArrayList<>(Arrays.asList(1, null)));
    graph.add(new ArrayList<>(Arrays.asList(2, null)));
    graph.add(new ArrayList<>(Arrays.asList(0, 1, null)));
    
graph.get(0) == [1, null] == 0 -> 1 -> null
graph.get(1) == [2, null] == 1 -> 2 -> null
graph.get(2) == [0, 1, null] == 2 -> 1 -> 0 -> null

 

 

- 그래프의 용어

• 정점 (vertex): 데이터가 저장되는 그래프의 기본 원소. 노드(node)라고도 함.
• 간선 (edge): 정점 간의 관계를 나타냄
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점. (직접 관계에 있는 두 정점)
• 가중치 그래프 (weighted Graph): 연결의 강도(두 정점 사이의 추가적인 정보)가 얼마나 되는지 적혀 있는 그래프
• 비가중치 그래프 (inweighted Graph): 연결의 강도가 적혀 있지 않은 그래프
• 무향(부방향) 그래프 (undirected graph): 정점간의 관계에서 연결 가능한 방향이 적혀 있지 않은 무향 그래프. 무향 그래프에서는 간선이 있는 두 정점은 서로 왕복이 가능하다. 반대로 단뱡향 그래프는 간선이 있더라도 A정점에서 B정점으로 갈 수 있더라도 B정점에서 A정점으로는 이동 불가능한 상황을 단방향인 간선으로 표현한다.
• 진입차수 (in-degreee) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)과 진출(나가는 간선)의 개수를 나타냄
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있을 때 두 정점은 인접한 정점이다.
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에 진입하는 경우에 자기 루프를 가졌다고 말함. 다른 정점을 거치지 않는다.
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있을 때, 사이클이 있다고 표현함.

 

- 그래프를 코드로 구현하기

1. 인접 행렬로 구현하기
   

   import java.util.*;
   
   public class GraphInArray {
       private int[][] graph;
       
       public void setGraph(int size) {
       graph = new int[size][size];
       
       for (int i = 0; i < size; i++) {
           for (int j = 0; j < size; j++) {
                graph[i][j] = 0;
           }
       }
   }
       public int[][] getGraph() {
            return graph;
       }
       
       public void addEdge(int from, int to) {
           if (from >= graph.length || to >= graph.lenth) return; // 그래프 범위를 넘어가는 인수 전달 시 작동 X
           graph[from][to] = 1;
       }
       
       public boolean hasEdge(int from, to) {
           if (from >= graph.length || to >= graph.lenth) return false;
           else if (graph[from][to] == 1) return true;
           else return false;
       }
       
       public void removeEdge(int form, int to) {
           from >= graph.length || to >= graph.lenth) return; 
           graph[from][to] = 0;
       }
   }​​

2. 인접 그래프로 구현하기
   

   import java.util.*;
   
   public class GraphInArrayList { 
   	private ArrayList<ArrayList<Integer>> graph;
   
       public Solution() {
           graph = new ArrayList<>();
       }
       
       public void setGraph(int size){
           for (int i = 0; i < size; i++) {
           graph.add(new ArrayList<Integer>());
           }
       }
   
       public ArrayList<ArrayList<Integer>> getGraph() {
           return graph;
       }
   
       public void addEdge(int from, Integer to) {
   		// from, to가 그래프의 크기보다 크거나, 음수일 경우 아무것도 추가 X
           if (from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return;
               graph.get(from).add(to); // from의 인접 리스트에 to를 추가
               graph.get(to).add(from); // to의 인접 리스트에 from를 추가
       } 
   
       public boolean hasEdge(int from, int to) {
           if (from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return false;
   		
           else return graph.get(from).contains(to); // ArrayList 메서드 contains 사용.
       }
   
       public void removeEdge(int from, int to) {
           if (from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return;
   		
           if (graph.get(from).contains(to)) { // from의 인접리스트가 to를 contain하는 경우 간선이 존재
               graph.get(from).remove((Integer) to); // 간선 삭제
           }
   
           if (graph.get(to).contains(from)) { // to의 인접리스트가 from을 contain하는 경우 간선이 존재
               graph.get(to).remove((Integer) from); // 간선 삭제
           }
       }
   }​​