[URECA] Day 19 | 알고리즘 | 그래프

그래프란?

용어: 
정점(Vertex): 그래프의 노드 또는 점
간선(Edge): 정점 간의 연결. 부모-자식 개념 없음 
가중치(Weight): 간선(엣지)에 할당된 값으로, 주로 두 노드(정점) 간의 관계의 강도, 비용, 거리 등을 나타냄
차수(Degree): 정점에 연결된 간선의 수
진입 차수: 방향 그래프에서 특정 정점으로 들어오는 간선의 수
진출 차수: 방향 그래프에서 특정 정점에서 나가는 간선의 수
경로(Path): 그래프의 두 정점 간에 존재하는 간선의 연속
사이클(Cycle): 시작 정점에서 출발하여 다시 시작 정점으로 돌아오는 경로. 트리와 가장 큰 차이
연결 그래프: 모든 정점이 서로 연결된 그래프
포화그래프: V 개의 정점을 가지는그래프는 최대 V *(V–1)/ 2 간선이 가능
예> 4개정점이있는그래프의최대간선수는 6(=>4*3/2) 개
부분 그래프(Subgraph): 원래 그래프의 일부 정점과 간선으로 구성된 그래프
방향 그래프: 간선에 방향이 있는 그래프. 예를 들어, A → B는 A에서 B로 가는 방향을 의미
무방향 그래프: 간선에 방향이 없는 그래프. A와 B 간의 관계는 양방향으로 해석

예시:
소셜 네트워크: 사람(정점)과 사람 간의 친구 관계(간선)를 나타내는 그래프.
도로망: 도로의 교차점(정점)과 도로(간선)를 표현하는 그래프.
웹 페이지: 웹 페이지(정점)와 링크(간선) 간의 관계를 나타내는 그래프.

 

 

노드와 간선을 입력받아 인접행렬로 저장하는 코드

/*
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
6 5
1 2
2 5
5 1
3 4
4 6
*/

import java.util.Scanner;

public class AdjacencyMatrix {
    public static void main(String[] args) {
        // Scanner 객체 생성하여 입력을 받을 준비
        Scanner scanner = new Scanner(System.in);
        
        // 첫 번째 줄에서 정점의 개수 N과 간선의 개수 M을 입력받음
        int N = scanner.nextInt(); // 정점의 개수
        int M = scanner.nextInt(); // 간선의 개수
        
        // N x N 크기의 인접 행렬 생성 (정점의 개수에 따라)
        int[][] adjacencyMatrix = new int[N + 1][N + 1]; // 1부터 N까지 사용하므로 N+1 크기로 생성
        
        // M개의 간선을 입력받아 인접 행렬에 저장
        for (int i = 0; i < M; i++) {
            int u = scanner.nextInt(); // 간선의 시작 정점
            int v = scanner.nextInt(); // 간선의 끝 정점
            
            // 무방향 그래프의 경우 양쪽 모두에 1을 설정
            adjacencyMatrix[u][v] = 1; // u에서 v로의 간선
            adjacencyMatrix[v][u] = 1; // v에서 u로의 간선
        }
        
        // 인접 행렬 출력 (디버깅 용도)
        System.out.println("인접 행렬:");
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println(); // 각 행을 출력한 후 줄 바꿈
        }
        
        // Scanner 종료
        scanner.close();
    }
}

노드와 간선을 입력받아 인접리스트로 저장하는 코드

/*
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
6 5
1 2
2 5
5 1
3 4
4 6
*/
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class AdjacencyList {
    public static void main(String[] args) {
        // Scanner 객체 생성하여 입력을 받을 준비
        Scanner scanner = new Scanner(System.in);
        
        // 첫 번째 줄에서 정점의 개수 N과 간선의 개수 M을 입력받음
        int N = scanner.nextInt(); // 정점의 개수
        int M = scanner.nextInt(); // 간선의 개수
        
        // 정점의 개수에 맞춰 인접 리스트 생성
        List<List<Integer>> adjacencyList = new ArrayList<>(N + 1);
        
        // 각 정점에 대해 빈 리스트 초기화
        for (int i = 1; i <= N+1; i++) {//정점이 1부터 시작하므로 0번은 버림
            adjacencyList.add(new ArrayList<>()); // 정점 i에 대한 빈 리스트 추가
        }
        
        // M개의 간선을 입력받아 인접 리스트에 저장
        for (int i = 0; i < M; i++) {
            int u = scanner.nextInt(); // 간선의 시작 정점
            int v = scanner.nextInt(); // 간선의 끝 정점
            
            // 무방향 그래프의 경우 양쪽 리스트에 추가
            adjacencyList.get(u).add(v); // u에서 v로 연결
            adjacencyList.get(v).add(u); // v에서 u로 연결
        }
        
        // 인접 리스트 출력 (디버깅 용도)
        System.out.println("인접 리스트:");
        for (int i = 1; i <= N; i++) {
            System.out.print(i + ": "); // 정점 번호 출력
            for (int neighbor : adjacencyList.get(i)) {
                System.out.print(neighbor + " "); // 인접한 정점 출력
            }
            System.out.println(); // 각 정점을 출력한 후 줄 바꿈
        }
        
        // Scanner 종료
        scanner.close();
    }
}