제육's 휘발성 코딩
Published 2022. 2. 23. 00:07
[JAVA] - 그래프 🔷 Java/Basic
반응형

그래프

  • 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:M 관계를 가지는 원소를 표현하는데 용이
  • 정점 (Vertex) : 그래프의 구성요소로 하나의 연결점
  • 간선 (Edge) : 두 정점을 연결하는 선
  • 차수 (Degree) : 정점에 연결된 간서의 수
  • 양방향 그래프 (최대 V * (V-1) / 2 개의 간선)
  • 단반향 그래프 (최대 V * (V-1) 개의 간선)

인접 행렬

image

  • 두 정점을 연결하는 간선의 유무를 행렬로 표현
  • V x V 정방 행렬
  • 행번호와 열 번호는 그래프의 정점에 대응
  • 두 정점이 인접되어 있으면(또는 가중치) 1 그렇지 않으면 0으로 표현
  • 무향 그래프 : i번째 행의 합 = i번째 열의 합 = Vi의 차수
  • 유향 그래프 : 행 i의 합 = Vi의 진출 차수, 열 i의 합 = Vi의 진입 차수

희소 그래프 vs 완전 그래프

  • 희소 그래프는 정점에 비해 간선이 적어 인접행렬을 사용하면 메모리 낭비가 발생할 수 있다.
  • 완전 그래프는 정점에 비해 간선이 많으므로 인접행렬을 사용하면 효율적이다.
import java.util.Arrays;
import java.util.Scanner;

/*
7
8
0 1
0 2
1 3
1 4
2 4
3 5
4 5
5 6
 */
public class AdjMatrixTest {
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 정점 수
        int C = sc.nextInt(); // 간선 수
        int[][] adjMatrix = new int[N][N];
        for (int i = 0; i < C; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            adjMatrix[from][to] = adjMatrix[to][from] = 1;
        }
        for (int[] is : adjMatrix) {
            System.out.println(Arrays.toString(is));
        }
    }
}

인접 리스트

image

  • 각 정점에 대한 인접 정점들을 순차적으로 표현
  • 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결리스트로 저장
  • 비순차적 탐색 처리가 느리다는 단점이 있다.
import java.util.Scanner;

/*
7
8
0 1
0 2
1 3
1 4
2 4
3 5
4 5
5 6
 */
public class AdjListTest {
    static class Node {
        int vertex;
        Node link;

        public Node(int vertex, Node link) {
            this.vertex = vertex;
            this.link = link;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "vertex=" + vertex +
                    ", link=" + link +
                    '}';
        }
    }
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 정점 수
        int C = sc.nextInt(); // 간선 수

        Node[] adjList = new Node[N];
        for (int i = 0; i < C; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            adjList[from] = new Node(to, adjList[from]);
            adjList[to] = new Node(from, adjList[to]);
        }
        for (Node head : adjList) {
            System.out.println(head);
        }
    }
}

간선 리스트

image

  • 두 정점에 대한 간선 그 자체를 객체로 표현하여 리스트로 저장
  • 간선을 표현하는 두 정점의 정보를 나타냄 (시작, 끝 정점)

BFS

  • 트리에서는 부모와 자식간의 관계가 명확하므로 방문관리하지 않지만, 그래프에서는 한 정점에서의 경로가 다양할 수 있으므로 방문관리를 해야된다.
  • 시작 정점을 큐에 삽입하고, 방문하지 않은 곳이라면 큐에 넣고 방문한 것으로 표시

인접 행렬 BFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class AdjMatrixTest {
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 정점 수
        int C = sc.nextInt(); // 간선 수
        int[][] adjMatrix = new int[N][N];
        for (int i = 0; i < C; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            adjMatrix[from][to] = adjMatrix[to][from] = 1;
        }
        bfs(adjMatrix, 0);
    }

    public static void bfs(int[][] adjMatrix, int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N];
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.println(current);

            // current 정점의 인접정점 처리 (단, 방문하지 않은 인접정정만)
            for (int j = 0; j < N; j++) {
                if (!visited[j] && adjMatrix[current][j] != 0) {
                    queue.offer(j);
                    visited[j] = true;
                }
            }
        }
    }
}

인접 리스트 BFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class AdjListTest {
    static class Node {
        int vertex;
        Node link;

        public Node(int vertex, Node link) {
            this.vertex = vertex;
            this.link = link;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "vertex=" + vertex +
                    ", link=" + link +
                    '}';
        }
    }
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 정점 수
        int C = sc.nextInt(); // 간선 수

        Node[] adjList = new Node[N];
        for (int i = 0; i < C; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            adjList[from] = new Node(to, adjList[from]);
            adjList[to] = new Node(from, adjList[to]);
        }
        bfs(adjList, 0);
    }

    public static void bfs(Node[] adjList, int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N];
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.println(current);
            for (Node temp = adjList[current]; temp != null; temp = temp.link) {
                if (!visited[temp.vertex]) {
                    queue.offer(temp.vertex);
                    visited[temp.vertex] = true;
                }
            }
        }
    }
}

DFS

인접 행렬 DFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class AdjMatrixTest {
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 정점 수
        int C = sc.nextInt(); // 간선 수
        int[][] adjMatrix = new int[N][N];
        for (int i = 0; i < C; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            adjMatrix[from][to] = adjMatrix[to][from] = 1;
        }
        dfs(adjMatrix, new boolean[N], 0);
    }

    public static void dfs(int[][] adjMatrix, boolean[] visited, int current) {
        visited[current] = true;
        System.out.println(current);
        for (int j = 0; j < N; j++) {
            if (!visited[j] && adjMatrix[current][j] != 0) {
                dfs(adjMatrix, visited, j);
            }
        }
    }
}

인접 리스트 DFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class AdjListTest {
    static class Node {
        int vertex;
        Node link;

        public Node(int vertex, Node link) {
            this.vertex = vertex;
            this.link = link;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "vertex=" + vertex +
                    ", link=" + link +
                    '}';
        }
    }
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 정점 수
        int C = sc.nextInt(); // 간선 수

        Node[] adjList = new Node[N];
        for (int i = 0; i < C; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            adjList[from] = new Node(to, adjList[from]);
            adjList[to] = new Node(from, adjList[to]);
        }
        dfs(adjList, new boolean[N], 0);
    }

    public static void dfs(Node[] adjList, boolean[] visited, int current) {
        visited[current] = true;
        System.out.println(current);
        for (Node temp = adjList[current]; temp != null; temp = temp.link) {
            if (!visited[temp.vertex]) {
                dfs(adjList, visited, temp.vertex);
            }
        }
    }
}
반응형
저작자표시
profile

제육's 휘발성 코딩

@sasca37

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요! 맞구독은 언제나 환영입니다^^

검색 태그

자료구조
자바스크립트
jpql
javascript
AOP
스프링
JPA
프로그래머스
이펙티브자바
자바

티스토리툴바