범위가 조금 넓어서 이번주 스터디에선 그래프의 표현 , 유니온 파인드 , 위상 정렬에 대해서 스터디를 해봤습니다!

---

그래프의 개념

• 정의: 정점(Vertex, Node)과 간선(Edge)을 모아 객체 간의 관계를 표현하는 자료구조.
• 예시: 지도/지하철 최단경로, 전기 회로, 도로망(교차점-일방통행), 선수 과목 관계 등
• 특징적 구조: 여러 개의 고립된 부분 그래프(isolated subgraphs)로 구성될 수 있음.
• 트리와 차이: 트리는 루트·부모-자식 관계·비순환 구조가 필수지만, 그래프는 그 제한이 없음.

💡

1. 그래프는 여러 개로 떨어져 있을 수 있다

그래프는 전체가 하나로 이어져 있을 필요가 없다. 즉, 완전히 연결되지 않은 여러 덩어리로 나뉘어 있을 수 있다.

예를 들어,

친구 그룹 A(서로 다 알고 있음)

친구 그룹 B(서로 다 알고 있음)

A와 B는 서로 모름 → 연결 X

이런 식으로 연결된 덩어리가 여러 개 존재할 수 있는데, 이것을 고립된 부분 그래프라고 한다.

1. 그래프는 트리보다 규칙이 훨씬 적다

트리는 꼭 지켜야 할 규칙이 있지만, 그래프는 그런 제한이 없다.

트리는 반드시: 루트가 존재해야 하고, 부모–자식 관계가 있어야 하고, 사이클(순환)이 없어야 한다

반면 그래프는: 루트가 없어도 되고, 부모/자식 같은 위계가 없어도 되고, 사이클이 있든 없든 상관없다

즉, 트리는 규칙이 많은 특수한 그래프이고, 그래프는 훨씬 자유로운 형태의 연결 구조라고 이해하면 된다.

---

핵심 용어

• 정점(vertex): 위치/개체
• 간선(edge): 정점 간 연결(= link, branch)
• 인접 정점(adjacent): 간선 하나로 직접 연결된 정점
• 차수(degree, 무방향): 정점에 인접한 간선 수
  • 무방향 그래프에서 모든 정점 차수 합 = 2E
• 진입 차수(in-degree), 진출 차수(out-degree, 유향)
  • 유향 그래프에서 모든 정점의 진입 차수 합 = 모든 정점의 진출 차수 합 = E
• 경로 길이(path length): 경로에 포함된 간선 수
• 단순 경로(simple path): 정점 중복 없음
• 사이클(cycle): 단순 경로의 시작·종료 정점이 동일

오일러 경로(Eulerian path)

• 오일러 경로(Eulerian path): 모든 간선을 정확히 한 번씩 지나는 경로(시작점으로 돌아올 필요 없음).
• 오일러 회로/투어(Eulerian circuit/tour): 모든 간선을 한 번씩 지나 시작 정점으로 돌아오는 경로.
• 존재 조건(무방향, 연결 가정)
  • 오일러 회로: 모든 정점의 차수가 짝수.
  • 오일러 경로: 차수가 홀수인 정점이 정확히 0개(=회로) 또는 2개. (질문 본문에는 “오일러 경로가 시작점으로 되돌아온다/모든 차수 짝수”라고 되어 있으나, 이는 오일러 회로의 조건입니다 — 위와 같이 정정합니다.)
    

---

그래프의 일반적 특징

• 네트워크 모델: 정점-간선으로 관계망을 표현
• 경로 다중성: 두 정점 사이에 2개 이상 경로가 있을 수 있음
• 루트/부모-자식 개념 없음(트리와 차별)
• 순회 방식: DFS, BFS
• 순환/비순환: 사이클이 있을 수도(사이클릭) 없을 수도(비사이클릭)
• 방향성: 방향/무방향 그래프로 구분
• 셀프 루프/사이클 가능 여부는 그래프 정의에 따름

---

그래프의 종류

(1) 방향성 기준

• 무방향 그래프: 간선을 (A, B)로 표기, (A, B) = (B, A)
  • 예: 양방향 통행 도로
• 방향 그래프: 간선을 <A, B>로 표기, <A, B> ≠ <B, A>
  • 예: 일방통행, 의존성

(2) 가중치 기준

• 가중치 그래프(네트워크): 간선에 비용/거리/용량/요금 등 가중치 부여
  • 예: 도시 간 거리, 통신요금, 회로 용량

(3) 연결성 기준(무방향)

• 연결 그래프: 모든 정점쌍 사이에 경로 존재
  • 트리(Tree): 사이클 없는 연결 그래프
• 비연결 그래프: 경로가 없는 정점쌍 존재

(4) 사이클 유무

• 사이클 그래프: 사이클 존재
• 비순환 그래프(Acyclic): 사이클 없음
  • 예: DAG(Directed Acyclic Graph, 유향 비순환)

(5) 완전성

• 완전 그래프(Kₙ): 모든 정점쌍이 간선으로 연결
  • 무방향의 간선 수: n(n−1)/2

---

그래프 표현 방법

• 그래프 알고리즘을 배우기 전에 반드시 알아야함
• 그래프 관련 문제를 해결하기 위해서는 주어진 그래프를 표현해야 하고, 그 데이터를 바탕으로 그래프 알고리즘을 적용시켜 해결해야 함

---

그래프를 표현하는 3가지 방법

              [그래프1 - 방향이 없는 그래프]

              [그래프2 - 방향이 있는 그래프]

1. 인접 행렬(Adjacency matrix)

정의 : 정점 수가 V일 때 V × V 크기의 행렬 M으로 간선을 표시.

• 무가중치: M[i][j] ∈ {0,1}
• 가중치: M[i][j] = 가중치(없으면 0 또는 ∞)
• 유향 그래프: M[i][j]만 채움
• 무향 그래프: M[i][j] = M[j][i] 대칭

메모리: Θ(V^2)

주요 연산

• 두 정점 간 간선 존재 확인: O(1)
• 정점 u의 모든 이웃 탐색: O(V)
• 간선 추가/삭제: O(1) (값 대입)

장점

• 매우 빠른 간선 존재 질의(O(1)).
• 구현이 단순, 행렬 기반 알고리즘(플로이드–워셜 등)에 유리.

단점

• 희소 그래프(간선이 적은 그래프)에서 메모리 낭비가 큼.
• 한 정점의 이웃을 나열하는 데 O(V)가 필요.

언제 쓰나

• 밀집 그래프(E ≈ V²), 간선 존재 여부를 자주 물을 때,
• 모든 정점 쌍을 다루는 전쌍 최단경로 같은 행렬 기반 알고리즘.

💡

이해를 돕는 비유(확실함)

친구 목록표라고 생각하면 된다.

• 가로줄 = “내가”
• 세로줄 = “상대”
• 칸 = “친구면 1, 아니면 0”

즉, 모든 사람을 상대로 ‘친구 여부’를 0/1로 체크한 친구표가 바로 인접행렬.

---

3. 장점(이론적으로 확실함)

• 연결 여부 확인이 초고속 → 두 노드 A, B가 연결됐는지 보려면 표에서 하나만 보면 끝 → O(1)
  
• 표 형태라 구현이 직관적

---

4. 단점(이론적으로 확실함)

• 노드가 많아지면 표가 엄청 커짐 → 공간 낭비
• 연결이 거의 없으면 대부분 0만 있음 → 비효율적

예: 10,000개의 노드 → 10,000×10,000 = 1억 칸 필요

---

5. 한 문장 요약

인접행렬은 그래프의 모든 노드 쌍을 표로 만들어, 연결 여부를 0/1로 저장하는 방식이다.

---

2. 인접 리스트(Adjacency list)

정의 : 각 정점 u에 대해, u와 연결된 (목적지, 가중치) 쌍의 리스트를 저장.

• 유향: u → v는 u의 리스트에만 저장
• 무향: u ↔ v는 u와 v 양쪽 리스트에 저장

메모리: Θ(V + E)

주요 연산

• 두 정점 간 간선 존재 확인: O(deg(u)) (u의 차수만큼 탐색)
• 정점 u의 모든 이웃 탐색: O(deg(u))
• 간선 추가: 평균 O(1)(리스트 push)
• 간선 삭제: O(deg(u))(리스트에서 찾아 제거)

장점

• 희소 그래프에서 메모리 효율 최고(V+E만큼 저장).
• 이웃 순회가 간선 수에 비례하므로 BFS/DFS에 매우 적합.

단점

• 간선 존재 여부를 즉시(O(1)) 확인할 수 없음(리스트 검색 필요).

언제 쓰나

• 희소 그래프, 순회/탐색(BFS/DFS), 단일/단소수 소스 최단경로(Dijkstra의 힙 버전 등).

💡

인접리스트 (Adjacency List)

“친구 이름만 메모하는 방식”

• 각 노드가 연결된 친구만 리스트에 적는다.
• 존재하는 간선만 기록 → 메모리 절약.

예

A-B, B-C 연결이면:

A: B
B: A, C
C: B

장점: 공간 효율 높음

단점: A-B 연결됐나 확인하려면 리스트를 뒤져야 함 → O(연결된 친구 수)

3. 간선 리스트(Edge list)

정의 : 모든 간선을 배열/리스트 하나에 (u, v[, w]) 형태로 나열.

• 무향: (u, v)와 (v, u) 중 하나만 저장하는 것이 일반적(표현 방식에 따라 다름)
• 가중치가 있으면 w 포함

메모리: Θ(E) (+정점 메타데이터)

주요 연산

• 두 정점 간 간선 존재 확인: O(E)(전체를 훑어야 함)
• 특정 정점의 이웃 탐색: O(E)(필터 필요)
• 간선 추가: O(1)(push)
• 간선 삭제: O(E)(검색 후 제거)

장점

• 구현이 가장 단순, 입력/출력 포맷으로 가장 흔함.
• 간선을 정렬하기 쉬워 크루스칼(MST) 같은 간선 정렬 기반 알고리즘에 최적.

단점

• 인접 정점 탐색이 비효율적(O(E)).
• 간선 존재 여부 질의가 느림.

언제 쓰나

• MST(크루스칼)처럼 간선 정렬·필터링이 핵심인 알고리즘,
• 데이터 교환/저장 포맷, 그래프를 한 번 훑는 전처리 단계.

💡

간선리스트 (Edge List)

“연결된 쌍만 모아둔 명단”

• 간선 하나하나를 “(출발, 도착, 가중치)” 형태로 저장

예

A-B, B-C 연결이면:

(A, B)
(B, C)

가중치가 있다면:

(A, B, 3)
(B, C, 5)

장점: 가장 단순, 간선만 모아두면 됨

단점: 두 노드 연결 여부 확인이 느림 → 하나하나 검사해야 함

---

선택 가이드

• 정점 수가 크고 간선이 적다(희소) → 인접 리스트가 기본값.
• 간선 존재 여부를 빈번히 O(1)로 확인해야 하거나 매우 밀집 → 인접 행렬.
• 간선을 정렬/스캔하는 작업이 핵심(예: 크루스칼) → 간선 리스트.

참고:

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

https://godgod732.tistory.com/15

---

https://www.acmicpc.net/problem/2606

BFS 사용

import java.io.*;
import java.util.*;

public class Main {
    static int count, num, connections;
    static boolean[] visited;
    static List[] computers;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        num = Integer.parseInt(br.readLine());
        connections = Integer.parseInt(br.readLine());
        visited = new boolean[num+1];
        computers = new List[num+1];
        count = 0;
        for(int i=1; i<num+1; i++) {
            computers[i] = new ArrayList<Integer>();
        }

        StringTokenizer st;
        for(int i=0; i<connections; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            computers[a].add(b);
            computers[b].add(a);
        }

        bfs(1);

        System.out.println(count-1); // 시작 지점 카운트 빼주기
        br.close();
    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(start);

        while(!queue.isEmpty()) {
            int now = queue.poll();
            if(!visited[now]) {
                count++;
                visited[now] = true;
                for(int i=0; i<computers[now].size(); i++) {
                    queue.add((int)computers[now].get(i));
                }
            }
        }
    }
}

DFS 사용

import java.io.*;
import java.util.*;

public class Main {
    static int count, num, connections;
    static boolean[] visited;
    static List[] computers;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        num = Integer.parseInt(br.readLine());
        connections = Integer.parseInt(br.readLine());
        visited = new boolean[num+1];
        computers = new List[num+1];
        count = 0;
        for(int i=1; i<num+1; i++) {
            computers[i] = new ArrayList<Integer>();
        }

        StringTokenizer st;
        for(int i=0; i<connections; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            computers[a].add(b);
            computers[b].add(a);
        }

        dfs(1);

        System.out.println(count-1); // 시작 지점 카운트 빼주기
        br.close();
    }

    private static void dfs(int start) {
        if(!visited[start]) {
            visited[start] = true;
            count++;
            for(int i=0; i<computers[start].size(); i++) {
                dfs((int)computers[start].get(i));
            }
        }
    }
}
}