그래프 표현

그래프

• 아이템(사물 또는 추상적 개념) 들과 이들 사이의 연결 관계 표현
• 정점들의 집합과 이를 연결하는 간선들의 집합
• 선형자료구조나 트리로 표현하기 어려운 M:N의 관계를 표현한 것이다.
• V개의 정점을 가지는 그래프는 최대 V*(V-1)/2 간선이 가능
  

보통의 경우, 간선은 1이라고 생각하지만, 가중치를 가진 계산을 할 수 있다.

그래프의 종류

1. 무향 그래프

2. 유향 그래프

→ 정해주지 않는 경우, 문맥을 통한 파악이 필요하다.
(ex. 일방 통행하는 노선을 계획하는 경우 : 유향 )

3. 가중치 그래프
   가중치가 1이 아니라, 값이 정해져 있는 것.
   항상 유향이 아니라, 무향이면서 가중치 그래프일 수도 있다.

4. 순환 그래프

: 하나의 사이클이 완성되는 경우, 순환 그래프라고 할 수 있다.

5. 비순환 방향 그래프
   : 유향 그래프지만, cycle이 반복되는 것이 아니라 일방향으로 끝이 나는 경우

---

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

---

---

경로

• 간선들을 순서대로 나열한 것
• 단순 경로 : 하나의 정점(노드)를 한 번만 지나는 경로
• cycle : 하나의 정점에서 끝나는 경로

• 경로 표시 방법
  1. 간선 나열 : 0→2, 2→4, 4→6
  2. 정점 나열 : 0-2-4-6 / 0-1-6

그래프 표현 방법

1. 인접행렬

• 두 정점을 연결하는 간선의 유무를 행렬로 표현
• V * V 개의 2차원 배열, 행 번호와 열 번호는 그래프의 정점 번호
  • 정점의 번호가 시작하는 때(0 혹은 1)에 따라, V개를 곱해주거나 V+1 해주면 된다.
• 두 정점이 인접되어 있다면 1, 그렇지 않으면 0으로 표현 (가중치가 있다면 해당 값으로)
• 입력 방법
  • 무향 그래프 : i번째 행의 합 = i번째 열의 합 = V(i) 의 차수
  • 유향 그래프 : i번째 행의 합 = V(i)의 진출 차수 / i번째 열의 합 = V(i)의 진입 차수

자바 코드

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt(); // 정점의 갯수(0 또는 1로 시작) 
		int E = sc.nextInt(); // 간선의 갯수 
		
		int[][] adjArr = new int[V][V]; // 만약 시작점이 1이라면, 각 V+1을 해줘야 한다.
		
		// E개의 간선을 입력 받을 반복문
		for(int i = 0; i < E; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt(); // 두 개의 정점을 갖기 때문에 
			int W = sc.nextInt(); // 가중치가 있다면 값은 3개 
			
			adjArr[A][B] = W; // 가중치가 없다면 1을 저장해주면 된다. 
			adjArr[A][B] = W; // 만약 무향이라면 반대의 경우도 같이 작성해줘야 한다. 
		}
	}

2. 인접 리스트

• 각 정점에 대한 인접 정점들을 순차적으로 표현
• 하나의 정점에 대한 인접 정점들을 각 노드로 하는 연결리스트로 저장

자바 구현

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt(); // 정점의 갯수(0 또는 1로 시작) 
		int E = sc.nextInt(); // 간선의 갯수 
		
		List<Integer>[] adjList = new ArrayList[V];
		
		// 기본적으로 전부 생성을 해주어야 nullpointexception이 안 뜬다. 
		for(int i = 0; i < V; i++) {
			adjList[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < E; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			
			// 가중치를 같이 저장하고 싶다면, 
			// 1. 클래스를 정의하거나 
			// 2. int[] 를 이용해서 넣어야 한다. 
			
			adjList[A].add(B);
			adjList[B].add(A);
		}
	}

---

• 인접행렬 vs 인접 리스트
  1. 정점이 100만개 정도 되는 경우, 인접 행렬은 공간에 여백이 너무 많아 리스트가 더욱 효율적이다.
  2. A와 B의 인접 여부를 물어볼 때, 인접 행렬이 훨씬 수월하다. (값의 존재 여부만 확인하면 되므로)
     인접 리스트는 차례대로 타고 들어가서 확인을 해야 한다.

---

3. 간선 배열

• 정점과 정점의 연결 정보인 간선을 배열에 저장
• 간선을 표현하는 두 정점의 정보를 배열 혹은 객체로 저장할 수 있다.

자바 구현

public class 그래프_03_간선배열 {
	
	static class Edge{
		int A, B, W; // 시작, 끝, 가중치 
		
		Edge(int A, int B, int W){
			this.A = A;
			this.B = B;
			this.W = W;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt(); // 정점의 갯수(0 또는 1로 시작) 
		int E = sc.nextInt(); // 간선의 갯수 
		
		Edge[] edges = new Edge[2]; // 객체 배열 생성 
		
		for(int i = 0; i < E; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int W = sc.nextInt();
			
			edges[i] = new Edge(A, B, W);
		}
		
		
		// 혹은 방법 2 ------------------------
		List<Edge> edges2 = new ArrayList<>();
		
		for(int i = 0; i < E; i++) {
			edges2.add(new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()));
		}
	}
}

클래스를 정의하지 않고 int[][] edges3 = new int[E][3];과 같이 선언하여 배열을 저장할 수도 있다.

// 혹은 방법 2 ------------------------
		List<Edge> edges2 = new ArrayList<>();
		
		for(int i = 0; i < E; i++) {
			edges2.add(new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()));
		}
		
		
		int[][] edges3 = new int[E][3];
		
		for(int i = 0; i < E; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int W = sc.nextInt();
			
			edges3[i][0] = A;
			edges3[i][1] = B;
			edges3[i][2] = W;
		}