[자료구조/JAVA] 그래프 (Graph)

그래프(Graph)

 

그래프는 정점들과, 정점들을 연결하는 간선들로 구성된 자료 구조이다. 
최단 경로 찾기, 네트워크 구성, 검색 엔진, 스케줄링 등 다양한 분야의 컴퓨터 과학에서 응용되어 사용되고 있다.

 

---

그래프 이론

 

그래프의 정의

• 정점(Vertex)와 간선(Edge)의 집합
• 표현 : G = (V, E)  (V=정점의 집합, E=간선의 집합)

 

---

그래프의 종류

 

방향그래프 : 간선에 방향이 있는 그래프

• 표현 :  (a, b) = 정점 a와 b를 연결하는 간선

무방향그래프 : 간선에 방향이 없는 그래프

• 표현 : <a, b> = 정점 a와 b를 연결하는 간선

https://en.wikipedia.org/wiki/Graph_theory

 

 

 

가중치 그래프 : 간선에 가중치가 부여된 경우

https://ko.wikipedia.org/wiki/%EA%B0%80%EC%A4%91_%EA%B7%B8%EB%9E%98%ED%94%84

 

 

---

그래프 용어

차수(Degree) : 정점에 인접한 간선의 수

• 방향그래프 : 진입차수와 진출차수로 구분

경로(Path) : 시작 정점 u부터 도착점 v까지의 정점들을 나열하여 표현

• 표현 : [a, c, b, e] = a부터 e까지의 경로 중 하나를 표현한 것
• 단순경로 : 경로 상의 정점들이 중복되지 않음
  
  • [a, c, b, c, b, e]는 단순경로가 아니다.
• 싸이클(Cycle) : 시작정점과 도착정점이 동일한 경로
  • [a, c, b, a]는 싸이클이다.

 

 

 

---

특수한 형태의 그래프

트리(Tree) : 싸이클이 없는 그래프. 따라서 트리는 특수한 형태의 그래프이다.

https://en.wikipedia.org/wiki/Binary_tree

 

 

신장트리(Spanning tree) : 주어진 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 싸이클 없이 연결하는 부분 그래프

• 연결성분 : 그래프에서 정점들이 서로 연결되어 구성되어 있는 부분

https://en.wikipedia.org/wiki/Spanning_tree

 

 

 

---

그래프 : 자료 구조 표현

프로그래밍할 때 사용되는 그래프를 자료 구조로 표현하는 방법은 크게 두 가지가 있다.

1. 인접행렬(Adjacency Matrix)
2. 인접리스트(Adjacency List)

과학기술정보통신부와 정보통신기획평가원 : 『소프트웨어중심대학』 Youtube

 

 

---

그래프 구조 구현 : 인접 행렬

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

        System.out.print("정점의 개수 입력:");
        int n = scanner.nextInt();

        int[][] adjMat = new int[n][n];

        System.out.print("간선의 수 입력:");
        int e = scanner.nextInt();

        System.out.print("간선 N줄 입력(u->v) (예시 : 1 2):");
        for (int i = 0; i < e; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            adjMat[u][v] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(adjMat[i][j] + " ");
            }
            System.out.println();
        }
    }
}

• 2차원 배열 adj_mat을 인접 행렬로 사용한다.
• adj_mat[i][j] = 1은 시작 정점 i로부터 정점 j까지 연결하는 간선을 의미한다. 
  
  • 만약 가중치가 존재하는 그래프라면 가중치를 넣어준다.

 

정점의 개수 입력:4
간선의 수 입력:10
간선 N줄 입력(u->v) (예시 : 1 2):
0 1
0 2
1 0
1 2
1 3
2 0
2 1
3 1
2 3
3 2
인접 행렬 출력
0 1 1 0 
1 0 1 1 
1 1 0 1 
0 1 1 0

 

 

---

그래프 구조 구현 : 인접 리스트

public class GraphAdjList {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.print("정점의 개수 입력:");
        int n = scanner.nextInt();

        List<Integer>[] adjList = new List[n];
        for(int i = 0; i < n; i++){
            adjList[i] = new LinkedList<>();
        }

        System.out.print("간선의 수 입력:");
        int e = scanner.nextInt();

        System.out.println("간선 입력(u->v) (예시 : 1 2):");
        for (int i = 0; i < e; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            adjList[u].add(v);
        }
        System.out.println("인접 리스트 출력");
        for (int i = 0; i < n; i++) {
            System.out.print(i + ": ");
            for (int j : adjList[i]) {
                System.out.print(j + " ");
            }
            System.out.println();
        }
    }
}

• adjList : 각 정점에 대해서 Linked List를 생성한다.
• 인접 리스트에는 각 정점에 연결된 다른 정점들의 리스트를 체이닝하여 저장한다.
  

정점의 개수 입력:4
간선의 수 입력:10
간선 입력(u->v) (예시 : 1 2):
0 1
0 2
1 0
1 2
1 3
2 0
2 1
3 1
2 3
3 2
인접 리스트 출력
0: 1 2 
1: 0 2 3 
2: 0 1 3 
3: 1 2

 

 

---

<함께 보기> 그래프 탐색 : BFS와 DFS

https://sjh9708.tistory.com/222

[알고리즘/JAVA] 그래프 탐색 : DFS / BFS (깊이우선 탐색 / 너비우선 탐색)