1. Introduction

그래프는 정점과 간선으로 이루어진다.

기본적으로 방향그래프와 무방향 그래프로 나눌 수 있으며, 방향 그래프는 정점에 방향이 존재((v0, v1) != (v1,v0))하고 무방향 그래프는 순서나 방향이 존재하지 않는다.((v0, v1) == (v1,v0))

2. Contents

아래에선 그래프의 몇가지 개념에 대해 알아보려 한다.

• 단순 그래프 : 자기 루프를 허용하지 않는 그래프(두 정점 사이에 최대 하나의 간선)

• 다중 그래프 : 두 정점 사이에 복수 간선이 가능한 그래프

---

• 완전 그래프 : 최대 수의 간선을 가진 그래프, 정점이 n개일 때 간선 수는 다음과 같다. 무방향 : n(n-1)/2, 방향 : n(n-1)

• 단순경로 : 모두 상이한 간선들로 구성된 경로

• 사이클(cycle) : 첫번째 정점과 마지막 정점이 동일한 단순 경로

• DAG(Directed Acyclic Graph) : 사이클이 없는 방향그래프

---

• 진입 차수(indegree) : 방향 그래프에서 정점 v를 머리로 하는 간선의 수

• 진출 차수(outdegree) : 방향 그래프에서 정점 v를 꼬리로 하는 간선의 수

3. 구현

그래프는 다음 방법으로 표현할 수 있다.

인접행렬 : nxn의 2차원 배열로 표현

인접리스트 : n개의 정점에 대한 인접한 정점들을 리스트로 만듬

이 글에선 인접 행렬로 무방향 그래프를 표현해보도록 하겠다.

다음은

그래프의 구조이다.
정점의 개수 n 만큼의 2차원 배열 n x n을 만들고, 초기화해준다.

class Graph { // Matrix

	int n; // Number of vertices
	int e; // Number of edges
	int[][] weight;

	public Graph(int noOfVertices) {
		//
		n = noOfVertices;
		e = 0;
		weight = new int[n][n];
	}
}

다음으로 삽입 연산이다. 삽입 시 i와 j가 연결되었다는 걸 표현하기 위해 weight를 주고 간선의 수를 증가시킨다.

	public void insertEdge(int i, int j) {
		weight[i][j] = 1;
		weight[j][i] = 1;
		e++;
	}
	}

삭제 연산도 마찬가지로 i와 j의 연결을 끊기 위해 weight를 0으로 초기화해준 후 간선의 수를 감소시킨다.

	public void removeEdge(int i, int j) {
		weight[i][j] = 0;
		weight[j][i] = 0;
		e--;
	}

adjacency는 정점 u에 인접한 모든 정점을 배열의 형태로 반환해준다.

	public int[] adjacency(int u) {
		int[] adj;
		int deg = 0;
		for (int i = 0; i < n; i++) { 
        // 먼저 연결된 정점을 세준 후
			if (weight[u][i] == 1) {
				deg++;
			}
		}

		adj = new int[deg]; // 수에 맞게 배열을 생성하고
		int num = 0;

		for (int i = 0; i < n; i++) {
        // 배열에 연결된 간선을 저장
			if (weight[u][i] == 1) { 
				adj[num] = i;
				num++;
			}
		}
		return adj; // 후 반환한다
	}

다음으론 그래프의 순회에 대해 알아보겠다.

4. 순회

이 글에선 편의를 위해 int형으로 정의한 stack, queue를 사용하였다.

public class Stack {
	private int top;
	private int[] data;
	private final static int MAX = 100;
	
	public Stack() {
		data = new int[MAX]; 
		top = -1;
	}
	
	public int size() { 
		return top + 1;
	}
	
	public boolean isEmpty() {
		return (top == -1);
	}
	
	public void push(int x) {
		top = top + 1; 
		data[top] = x;
	}
	
	public int pop() {
		top = top -1;
		return data[top+1];
	}
	
	public int peek() {
		return data[top];
	}
}

그래프엔 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다.
깊이 우선 탐색의 알고리즘은 다음과 같다.

1. 정점 i를 방문한다.

2. 정점 i에 인접한 정점 중 아직 방문하지 않은 정점들을 모두 스택에 저장한다.

3. 스택에서 정점을 삭제하여 새로운 i를 설정, 다시 1단계를 수행한다.

4. 스택이 공백이 되면 연산을 종료한다.

이를 자바 코드로 구현하면 다음과 같다.

	public void dfs(int v) {
		System.out.println("DFS");
		int[] visited = new int[n];
		Stack s = new Stack();
		s.push(v);
		
		while(!s.isEmpty()) {
			int j = s.pop();
			if(visited[j] == 0) {
				System.out.print(j + ", ");
				visited[j] = 1;
               // 인접한 정점들 중방문하지 않은 정점을
				for(int k : adjacency(j)) { 
					if(visited[k] == 0) {
						s.push(k); // 스택에 저장
					}
				}
			}
		}
	}

너비 우선 탐색의 알고리즘은 다음과 같다.

1. 정점 i를 방문한다.

2. 정점 i에 인접한 정점 중 아직 방문하지 않은 정점들을 모두 큐에 저장한다.

3. 큐에서 정점을 삭제하여 새로운 i를 설정, 다시 1단계를 수행한다.

4. 큐가 공백이 되면 연산을 종료한다.

이를 자바 코드로 구현하면 다음과 같다.

	public void bfs(int v) {
		System.out.println("BFS");
		int[] visited = new int[n];
		Queue q = new Queue();
		q.enqueue(v);
		
		while(!q.isEmpty()) {
			int j = q.dequeue();
			if(visited[j] == 0) {
				System.out.print(j + ", ");
				visited[j] = 1;
			}
			for(int k : adjacency(j)) {
				if(visited[k] == 0) {
					q.enqueue(k);
				}
			}
		}
	}

4. Review

그래프의 기본에 대해 알아보았다.
다음엔 가중치 그래프에 대해 정리해보겠다!