그래프 기본

그래프

• 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계 표현
• 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조
• 선형자료구조(1:1)나 트리자료구조(1:N)로 표현하기 어려운 M:N관계를 표현

가중치 그래프(Weighted Graph) : 간선에 값이 있는 그래프

순환 그래프(Cycle graph): 사이클이 있는 그래프

완전 그래프

정점에 대해 가능한 모든 간선들을 가진 그래프

간선 의 수 : N(N-1)/2개

부분 그래프

원래 그래프에서 일부의 정점이나 간선을 제외한 그래프

인접

• 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.
• 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다.

경로

간선들을 순서대로 나열한 것

간선 : (0,2),(2,4),(4,6)

정점 : 0-2-4-6

단순경로 : 경로 중 한 정점을 최대한 한번만 지나는 경로

0-2-4-6, 0-1-6

사이클 : 시작한 정점에서 끝나는 경로

1-3-5-1

그래프 표현 방법

간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정

인접 행렬

• V*V(정점의 수) 크기의 2차원 배열을 이용하여 간선 정보를 저장
• 배열의 배열
• 두 정점을 연결하는 간선의 유무를 행렬로 표현
  • 행 번호와 열 번호는 그래프의 정점에 대응
  • 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현
• 무향 그래프
  i번째 행의 합=i번째 열의 합=Vi의 차수

• 유향 그래프
  • 행 i의 합=Vi의 진출 차수
  • 열 i의 합=Vi의 진입 차수

import java.util.Scanner;

public class 그래프_01_인접행렬 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int V = sc.nextInt(); // 정점의 개수를 입력을 받는다. (6 이다. 시작정점이 0번인지 / 1번인지)
		int E = sc.nextInt(); // 간선의 수가 입력 된다.

		int[][] adjArr = new int[V + 1][V + 1];

		// 간선을 입력을 받자.
		for (int i = 0; i < E; i++) {
			int st = sc.nextInt();
			int ed = sc.nextInt();

			//유향 그래프라면 20번라인은 필요없다.
			adjArr[st][ed] = 1;
			//무향그래프일때 아래도 같이 작성을 해준다.
			adjArr[ed][st] = 1;
			
			adjArr[st][ed] = adjArr[ed][st] = 1; //한줄적기 가넝
		}
	}
}

인접 행렬의 장점

• 연결 여부 확인 빠름 : 인접 행렬에서 두 정점 간의 연결 여부를 확인하는데 상수 시간(O(1))이 소요됩니다. 배열 인덱스를 통해 바로 확인할 수 있기 때문입니다.
• 구현이 간단하고 직관적 : 인접 행렬은 2차원 배열로 구현되어 있어 코드가 간결하고 이해하기 쉽습니다.

인접 행렬의 단점

• 메모리 낭비 : 간선이 적은 희소 그래프의 경우 인접 행렬은 메모리 낭비가 클 수 있습니다. 이는 정점 수의 제곱에 해당하는 공간이 필요하기 때문입니다.
• 간선 추가/삭제 비효율적 : 인접 행렬에서 간선을 추가하거나 삭제하는 작업은 느리고 복잡할 수 있습니다.

인접 리스트

• 각 정점마다 해당 정점으로 나가는 간선의 정보를 저장
• 각 정점에 대한 인접 정점들을 순차적으로 표현

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.ConcurrentHashMap;

public class 그래프_02_인접리스트 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int V = sc.nextInt(); // 정점의 개수를 입력을 받는다. (6 이다. 시작정점이 0번인지 / 1번인지)
		int E = sc.nextInt(); // 간선의 수가 입력 된다.

		List<Integer>[] adjList = new ArrayList[V+1];
		
		for(int i = 0 ; i<V+1; i++) {
			adjList[i] = new ArrayList<>();
		}
		
		
		// 간선을 입력을 받자.
		for (int i = 0; i < E; i++) {
			int st = sc.nextInt();
			int ed = sc.nextInt();

			//유향 그래프라면 20번라인은 필요없다.
			adjList[st].add(ed);
			//무향그래프일때 아래도 같이 작성을 해준다.
			adjList[ed].add(st);
		}
		
		for(int i = 0 ; i<V+1; i++) {
			Collections.sort(adjList[i]);
		}
	}
}

인접 리스트의 장점

• 메모리 효율적 : 간선이 적은 희소 그래프(sparse graph)의 경우 인접 리스트는 메모리 사용량이 적습니다. 인접 리스트는 실제 연결된 간선만 저장하기 때문입니다.
• 간선 추가/삭제 용이 : 인접 리스트에서는 간선을 추가하거나 삭제하기 쉽습니다. 새로운 간선을 리스트에 추가하거나 삭제하기만 하면 됩니다.

인접 리스트의 단점

두 정점 간의 연결 확인 느림 : 인접 리스트에서 두 정점 간에 간선이 존재하는지 확인하려면 연결된 정점 목록을 탐색해야 합니다. 이 과정은 O(n)의 시간이 소요됩니다.

인접 행렬/인접 리스트

인접 행렬이 더 효율적인 경우 : 밀집 그래프(dense graph), 두 정점 간의 연결 여부를 자주 확인해야 하는 경우

인접 리스트가 더 효율적인 경우 : 간선이 적은 희소 그래프(sparse graph)

간선의 배열

• 간선(시작 정점, 끝 정점)을 배열에 연속적으로 저장
• 간선을 표현하는 두 정점의 정보를 배열 혹은 객체로 저장할 수 있음

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 그래프_03_간선배열 {
	static class Edge {
		int st, ed;

		public Edge(int st, int ed) {
			this.st = st;
			this.ed = ed;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt(); // 정점의 개수를 입력을 받는다. (6 이다. 시작정점이 0번인지 / 1번인지)
		int E = sc.nextInt(); // 간선의 수가 입력 된다.

		// 2가지
		Edge[] edges = new Edge[E];
		List<Edge> edges2 = new ArrayList<>();
		
		int[][] edges3 = new int[E][2];   //[i][0] : 시작정점, [i][1] : 끝정점

		for (int i = 0; i < E; i++) {
			int st = sc.nextInt();
			int ed = sc.nextInt();

			edges[i] = new Edge(st, ed);

		}
	}
}