그래프 구현

그래프 자세히 알아보기

그래프 구현 방식

---

1. 인접 행렬 (adjacency matrix)
2. 인접 리스트 (adjacency list)

차이점

	인접 행렬	인접 리스트
정점 간의 간선 여부	graph[x][y] 의 값으로 한번에 확인	graph<x> 의 원소에서 y가 나올때까지 탐색
공간 복잡도	V개의 노드 표현 위해V^2 만큼의 공간 필요 인접 노드를 찾기 위해 모든 노드를 순회 공간복잡도 : O(V^2)	V개의 리스트에 간선(E) 만큼 원소가 들어있음 인접 노드를 쉽게 찾을 수 있음 공간복잡도 : O(V+E)
주사용	간선이 많이 있는 밀집 그래프 간선의 연결 여부 확인에 유리	간선이 적게 있는 희소 그래프 인접 노드 확인에 유리

 

인접 행렬

---

• 그래프를 2차원 배열에 저장하는 방법으로 노드 수보다 간선 수가 많은 dense graph 이거나 빠르게 부속된 간선을 찾을 때 주로 사용
  • 부속된 간선을 찾는 것은 빠르지만 |V| x |V| 만큼의 공간이 필요하여 저장 측면에서 비효율적(|V| : 정점 수)

 

1. 방향 그래프 (Directed Graph)

2번 정점에서 4번 정점으로의 간선이 존재할 경우

• graph[2][4] = 1

2. 무방향 그래프 (Undirected Graph)

2번 정점에서 4번 정점으로의 간선이 존재할 경우

• graph[2][4] = graph[4][2] = 1

3. 가중치 그래프(Weighted Graph)

 

 

구현 코드

• 무방향 그래프

public class Main {
 
    public static void print(int[][] graph) {
        for (int i = 1; i < graph.length; i++) {
            for (int j = 1; j < graph.length; j++)
                System.out.print(graph[i][j]+ " ");
            System.out.println();
        }
    }
 
    public static void putEdge(int[][] graph, int x, int y) {
        graph[x][y] = 1;
        graph[y][x] = 1;
    }
 
    public static void main(String[] args) {
        int n = 5; //그래프 정점의 개수
        int[][] graph = new int[n+1][n+1]; //index를 1부터 맞추기 위해 n+1
 
        putEdge(graph, 1, 2);
        putEdge(graph, 1, 3);
        putEdge(graph, 1, 4);
        putEdge(graph, 2, 3);
        putEdge(graph, 2, 5);
        putEdge(graph, 3, 4);
        putEdge(graph, 4, 5);
 
        print(graph);
    }
}
/*출력
01110
10101
11010
10101
01010
*/

 

시간 복잡도

• 어느 두 정점(i, j)에 부속된 간선이 있는지 체크하는 연산
  • O(1)
  • graph[x][y]가 1인지 0인지만 확인
• 임의의 한 정점(i)에 인접한 정점을 찾는 연산
  • O(V)
  • 인접행렬에서 i행 전체에 대해 조사

 

인접 리스트

---

• 인접한 정점을 연결 리스트로 저장하는 방법으로 연결된 간선에 대한 값만 저장하기 때문에 저장 측면에서 효율적이고 간선 수보다 노드 수가 많은 spare graph에 주로 사용
  • 정점은 배열로 저장하고 각 정점에 인접한 정점들은 연결 리스트로 관리

 

1. 방향 그래프 (Directed Graph)

인접 목록 길이의 합 = 그래프에 있는 간선의 수

• list.size()=간선의 수

2. 무방향 그래프 (Undirected Graph)

인접 목록 길이의 합 = 그래프에 있는 간선의 수*2

• list.size()=간선의 수*2

3. 가중치 그래프(Weighted Graph)

가중치를 저장하기 위한 추가 필드 필요

 

구현 코드

public class Main {
 
    public static void print(ArrayList<ArrayList<Integer>> graph) {
        for (int i = 1; i < graph.size(); i++) {
            ArrayList<Integer> node = graph.get(i);
            System.out.print("node"+"["+i+"] : ");
            for (int j = 0; j < node.size(); j++)
                System.out.print(node.get(j)+ "->");
            System.out.println();
        }
    }
 
    public static void putEdge(ArrayList<ArrayList<Integer>> graph, int x, int y) {
        graph.get(x).add(y);
        graph.get(y).add(x);
    }
 
    public static void main(String[] args) {
        int n = 5; //그래프 정점의 개수
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
 
        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>()); //각 노드 별 리스트를 만들어준다.
        putEdge(graph, 1, 2);
        putEdge(graph, 1, 3);
        putEdge(graph, 1, 4);
        putEdge(graph, 2, 3);
        putEdge(graph, 2, 5);
        putEdge(graph, 3, 4);
        putEdge(graph, 4, 5);
 
        print(graph);
    }
}
/* 출력
node[1] : 2->3->4->
node[2] : 1->3->5->
node[3] : 1->2->4->
node[4] : 1->3->5->
node[5] : 2->4->
*/

 

시간 복잡도

• 어느 두 정점(i, j)에 부속된 간선이 있는지 체크하는 연산
  • O(d)(d=degree(i))
• 임의의 한 정점(i)에 인접한 정점을 찾는 연산
  • O(d)(d=degree(i))