그래프(Graph)

1. 그래프(Graph)란?

📝 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조이다. 객체 사이의 연결 관계를 표현하는데 사용된다.

---

2. 그래프 용어 정리

📋 용어	뜻
정점(Vertex)	그래프의 구성 요소로 하나의 연결 점이며, 노드(Node)라고도 한다.
간선(Edge)	두 정점을 연결하는 선으로, 정점 간의 관계를 나타낸다.
차수(Degree)	정점에 연결된 간선의 수를 나타낸다.
가중치(Weight)	간선에 할당된 값으로, 해당 간선의 비용이나 거리를 나타낸다.
인접(Adjacent)	두 정점 사이에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.
사이클(Cycle)	그래프에서 한 노드에서 시작해서 같은 노드로 돌아오는 경로를 나타낸다.
경로(path)	두 정점 사이를 잇는 간선들을 순서대로 나열한 것이다.

---

3. 그래프의 종류

📁 종류	뜻
무방향 그래프 (Undirected Graph)	간선에 방향이 없는 그래프
방향 그래프 (Directed Graph)	간선에 방향이 있는 그래프
가중치 그래프 (Weighted Graph)	간선에 가중치가 할당된 그래프
완전 그래프(Complete Graph)	모든 정점이 서로 연결되어 있는 그래프
부분 그래프	원래 그래프에서 일부의 정점이나 간선을 제외한 그래프
연결 그래프(Connected Graph)	모든 정점 쌍 사이에 최소 하나 이상의 경로가 존재하는 그래프
비연결 그래프(Disconnected Graph)	특정 정점 쌍 사이에 경로가 존재하지 않는 그래프
트리 (Tree)	트리는 그래프의 특수한 형태이다.

---

4. 그래프 구현 방법

☑️ 인접 행렬(Adjacent matrix)

• 정의
  • $V \times V$ 크기의 2차원 배열을 이용해서 연결 관계를 표현하는 방식이다.
  • 행과 열은 그래프의 각 정점을 나타낸다.
  • 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현한다.
• ⭐️ 장점
  • 임의의 두 정점이 연결되어 있는지 확인할 때 시간 복잡도가 $O(1)$이다.
  • 구현이 간단하다.
• 💥 단점
  • 간선이 적은 희소 그래프일 때 메모리, 시간이 비효율적이다.

☑️ 인접 리스트(Adjacent List)

• 정의
  • 각 정점에서 그 정점과 인접한 정점들을 리스트 형태로 차례대로 저장하는 방식이다.
  • 리스트의 헤더 인덱스는 각 정점을 나타낸다.
• ⭐️ 장점
  • 간선의 개수에 비례하는 메모리만 차지한다.
• 💥 단점
  • 임의의 두 정점이 연결되어 있는지 확인할 때 시간 복잡도가 $O(V)$이다.

☑️ 간선 리스트(Edge List)

• 간선(시작 정점, 끝 정점)의 정보를 객체로 표현하여 리스트에 저장

---

5. 예제 코드

(1) 인접 행렬 구현

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

public class Main {

	static int[][] arr;
	public static void main(String[] args) throws IOException{

		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(in.readLine()," ");
		int V= Integer.parseInt(st.nextToken()); // 정점 수
		int E= Integer.parseInt(st.nextToken()); // 간선 수
		
		arr=new int[V][V]; // 모두 0으로 초기화된 상태
		
		// 입력
		int from,to;
		for(int i=0;i<E;++i) {
			st=new StringTokenizer(in.readLine()," ");
			from=Integer.parseInt(st.nextToken());
			to=Integer.parseInt(st.nextToken());
			// 무향 그래프
			arr[to][from]=arr[from][to]=1;
		}
		
		// 출력
		for(int[] temp: arr) {
			System.out.println(Arrays.toString(temp));
		}
	}
}

(2) 인접 리스트 구현

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(in.readLine()," ");
		int V= Integer.parseInt(st.nextToken()); // 정점 수
		int E= Integer.parseInt(st.nextToken()); // 간선 수
		
		
		ArrayList<ArrayList<Integer>> graph=new ArrayList<>(); // 그래프-인접 리스트
		for(int i=0;i<=V;i++) {
			graph.add(new ArrayList<>());
		}
		// 입력
		for(int i=0;i<E;i++) {
			st=new StringTokenizer(in.readLine()," ");
			int from=Integer.parseInt(st.nextToken());
			int to=Integer.parseInt(st.nextToken());
			graph.get(from).add(to);
			graph.get(to).add(from);
		}
		
		// 출력
		int start=0;
		for(ArrayList list : graph) {
			System.out.print(start+" -> ");
			for(int i=0; i<list.size(); i++) {
				System.out.print(list.get(i)+" -> ");
			}
			System.out.println();
			start++;
		}
	}
	
}