자료구조) Graph (그래프)

Graph (그래프)

Traversal / Search (순회,탐색)

• DFS(Depth First Search) 깊이우선탐색
• BFS(Breadth First Search) 너비우선탐색

Spanning Tree (신장트리)

• DFST(Depth First Spanning Tree) 깊이우선 신장트리
• BFST(Breadth First Spanning Tree) 너비우선 신장트리
• MST,MCST(Minimum_Cost Spanning Tree) 최소_비용 신장트리 : Kruskal, Prim 's Alg

Distance (최단거리 등)

• Dijkstra 's Alg
• Floyd-Warshall 's Alg
• Bellman-Ford 's Alg

Etc

• Network Flow
• Bipartite Matching

---

Graph

• Vertex, Edge
• 종류 : 무방향/방향/완전/부분/가중 그래프 ..
• 정점 V1,V2가 간선 E로 연결되있다면, V1과V2는 adjacent(인접)하고, E는 V1과V2에 incident(부속)한다
• degree, path, cycle

구현

1. Adjacent Matrix

2. Adjacent List

두 정점 u,v가 인접한지 확인하는 경우라면,
인접행렬은 adj_matrix[u][v]의 값을 참조하기만하면 된다. 시간복잡도=O(1)
인접리스트는 adj_list[u]에 연결된 원소들을 순회하며 v의 존재를 확인해야한다. 최악의 경우 시간복잡도=O(|V|)
한편, 정점 u에 연결된 모든 정점을 탐색하는 경우라면,
인접행렬은 모든 adj_matrix[u][i]를 참조해야한다. 시간복잡도=O(|V|)
인접리스트는 adj_list[u]의 개수만큼만 걸린다. (물론 최악의경우엔 O(|V|)지만 탐색을 전체그래프로 확장하면 달라짐, 인접행렬의 공간복잡도는 O(|V|2)이고 인접리스트는 O(|E|)이다)
따라서, 각 정점간의 연결관계 참조가 잦다면 인접행렬 표현이, 순회가 잦거나 |V|가 크다면 인접리스트 표현이 유리하다.

인접행렬로 표현된 그래프를 받아 인접리스트로 변환하는 코드

Input	Output
첫 줄에 정점의 개수 V가 주어집니다. (1 ≤ V ≤ 55) 두번째 줄부터 V줄에 걸쳐 V번 정점과 1 - V번 정점의 연결 관계가 입력됩니다. V번째 줄의 i번째 값이 1이면 V에서 출발해 i번 정점으로 향하는 간선이 존재한다는 의미이며, 0이면 이러한 간선이 존재하지 않는 다는 의미입니다.	1번부터 V번 정점까지 V개 줄에 걸쳐 각 정점의에 연결된 정점의 번호를 아래 예제와 같은 형태로 출력합니다.

import java.util.*;

public class Test {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[][] adj_matrix = new int[n + 1][n + 1];

        ArrayList<Integer>[] adj_list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj_list[i] = new ArrayList<>();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                adj_matrix[i][j] = scanner.nextInt();
                if (adj_matrix[i][j] == 1) {
                    adj_list[i].add(j);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            System.out.print(i + " : ");
            for (int j = 0; j < adj_list[i].size(); j++) {
                System.out.print(adj_list[i].get(j) + " ");
            }
            System.out.println();
        }
    }
}