그래프
그래프의 개념
- 그래프 (Graph) : 원소 사이의 연결 관계를 표현할 수 있는 자료구조
- 예 : 지도, 전기 회로의 소자들 등
그래프의 특징
- 현상이나 사물을 정점(vertex)와 간선(edge)으로 표현한 유한 집합이다.
- Gragh G = (V, E)로 표현한다.
- 두 정점이 간선으로 연결되어 있으면 인접(adjacent)라고 한다.
- 네트워크 모델이다.
- 2개 이상의 경로가 가능하다.
- 방향, 무방향 그래프 모두 가능하다.
- 부모-자식 개념이 없다.
오일러 경로 (Eulerian Tour)
- 그래프에 존재하는 모든 간선(edge)을 한 번만 통과하면서 처음 정점(vertex)으로 되돌아오는 경로
- 오일러의 정리 : 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 경우에만 오일러 경로가 존재
그래프의 용어
- 정점 (vertex), 노드 (node) :
- 간선 (edge), 링크 (link) :
- 인접 정점 (adjacent vertex) :
- 단순 경로 (simple path) :
- 차수 (degree) :
- 무방향 그래프에서 하나의 정점에 인접한 정점의 수
- 진출 차수 (in-degree) :
- 진입 차수 (out-degree) :
- 경로의 길이 (path length) :
- 사이클 (cycle) :
- 단순 경로의 시작 정점과 종료 정점이 동일한 경우
그래프의 종류
무방향 그래프 (Undirected Graph)
- 두 정점을 연결하는 간선에 방향이 없는 그래프
- 방향이 없기 때문에 양방향으로 갈 수 있음
- 정점 A와 정점 B를 연결하는 간선을 (A, B)로 표현하며 (A, B)와 (B, A)는 동일한 간선
- 표시방법 예 :
- V(G1) = {0, 1, 2, 3},
- E(G1) = {(0, 1), (0, 3), (1,3), (2, 3)}
방향 그래프 (Directed Graph)
- 두 정점을 연결하는 간선에 방향이 있는 그래프
- 한 방향으로만 갈 수 있음
- 정점 A에서 정점 B를 가는 간선을 <A, B>로 표현하며 <A, B>와 <B, A>는 다른 간선
- 표시방법 예 :
- V(G2) = {0, 1, 2, 3},
- E(G2) = {<0, 1>, <0, 3>, <1,3>, <2, 3>}
부분 그래프 (SubGraph)
- 기존 그래프에서 정점의 일부와 간선의 일부로 이루어진 그래프
- 아래 수식을 만족함 :
연결 그래프 (Conneted Graph)
- 떨어져 있는 정점이 없는 그래프
- 무뱡향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재
비연결 그래프 (Unconneted Graph)
- 떨어져 있는 정점이 있는 그래프
- 무뱡향 그래프 G에 있는 모든 정점쌍에 대하여 경로가 존재하지 않을 수도 있음
완전 그래프 (Complete Graph)
- 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프
- 무방향 완전 그래프 :
- 정점의 수가 n이면 전체 간선의 수는 n * (n - 1) /2
가중 그래프 (Wegiht Graph)
- 정점을 연결하는 간선에 비용이나 가중치를 할당한 그래프
- 네트워크라고도 함
유향 비순환 그래프 (Directed Acyclic Graph)
희소 그래프 (Sparse Graph)
밀접 그래프 (Dense Graph)
그래프 표현 방법
인접 행렬 (Adjacency Matrix)
- NxN 행렬로 표현
- 원소 (i, j) = 1 : 정점 i와 정점 j 사이에 간선이 있음
- 원소 (i, j) = 0 : 정점 i와 정점 j 사이에 간선이 없음
- 구현이 비교적 간편
- 2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 배열의 위치를 확인하면 두 정점에 대한 정보 조회 시간 복잡도는 O(1)
- 모든 정점에 대해 간선 정보를 대입하려면 O(n^2)의 시간복잡도를 가짐
- case1 : 유형 그래프
- 원소 (i, j)는 정점 i로부터 정점 j로 연결되는 간선이 있는지를 나타냄
- case2 : 가중치 그래프
public class MatrixGraph {
int[][] matGraph;
public MatrixGraph(int size) {
this.matGraph = new int[size + 1][size + 1];
}
public int[][] getGraph() {
return this.matGraph;
}
// 무방향
public void putUnDirected(int x, int y) {
matGraph[x][y] = matGraph[y][x] = 1;
}
// 방향
public void putDirected(int x, int y) {
matGraph[x][y] = 1;
}
// 출력
public void printGraph() {
for (int i = 0; i < matGraph.length; i++) {
for (int j = 0; j < matGraph.length; j++) {
System.out.print(" " + matGraph[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
int size = 4;
MatrixGraph graph = new MatrixGraph(size);
graph.putUnDirected(1, 1);
graph.putUnDirected(1, 2);
graph.putUnDirected(1, 3);
graph.putUnDirected(1, 4);
graph.putUnDirected(2, 3);
graph.printGraph();
}
}
인접 리스트 (Adjacency List)
- N개의 연결 리스트로 표현
- 정점의 리스트 배열을 만들어서 관계를 설정
- i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결해 놓음
- 구현이 비교적 어려움
- 시간복잡도 : O(n)
- case: 가중치 있는 그래프
public class ListGraph {
private ArrayList<ArrayList<Integer>> listGraph;
public ListGraph(int size) {
this.listGraph = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < size + 1; i++) {
listGraph.add(new ArrayList<Integer>());
}
}
public ArrayList<ArrayList<Integer>> getGraph(){
return this.listGraph;
}
// 무방향
public void putUnDirected(int x, int y) {
listGraph.get(x).add(y);
listGraph.get(y).add(x);
}
// 방향
public void putDirected(int x, int y) {
listGraph.get(x).add(y);
}
// 출력
public void printGraph() {
for (int i = 0; i < listGraph.size(); i++) {
System.out.print(i + " :");
for(int j = 0; j < listGraph.get(i).size(); j++) {
System.out.print(" -> " + listGraph.get(i).get(j));
}
System.out.println();
}
}
public static void main(String[] args) {
int size = 4;
ListGraph graph = new ListGraph(size);
graph.putUnDirected(1, 2);
graph.putUnDirected(2, 3);
graph.putUnDirected(2, 4);
graph.printGraph();
}
}
그래프의 탐색
깊이 우선 탐색 (Depth-First Search)
- 그래프의 시작 정점에서 시작하여 인접한 정점 중 아직 방문하지 않은 정점을 선택
- 방금 탐색한 정점과 인접한 정점 중 아직 탐색하지 않은 점정을 선택
- 탐색하지 않은 정점이 없다면 탐색 종료
- 방문하지 않은 정점이 있다면 해당 정점부터 다시 탐색 시작
- 자기 자신을 호출하는 순환 알고리즘 형태
- 주로 재귀 호출과 스택 사용하여 구현
public class DFSGraph {
int v;
int[][] dfsGraph;
boolean[] visited;
public DFSGraph(int v){
this.v = v;
this.dfsGraph = new int[v+ 1][v + 1];
this.visited = new boolean[v + 1];
}
public int[][] getGraph() {
return this.dfsGraph;
}
// 무뱡향
public void putUndirected(int x, int y) {
this.dfsGraph[x][y] = this.dfsGraph[y][x] = 1;
}
// 방향
public void putDirected(int x, int y) {
this.dfsGraph[x][y] = 1;
}
// 출력
public void printGraph() {
for(int i = 0; i < this.getGraph().length; i++) {
for(int j = 0; j < this.dfsGraph[i].length; j++) {
System.out.print(this.dfsGraph[i][j] + " ");
}
System.out.println();
}
}
// 탐색 (재귀)
public void dfs(int n) {
this.visited[n] = true;
System.out.print(n + " ");
for(int i = 1; i <= this.v; i++) {
if (dfsGraph[n][i] == 1 && visited[i] == false) {
dfs(i);
}
}
}
public static void main(String[] args) {
int size = 4;
DFSGraph graph = new DFSGraph(size);
// 방문 초기화
for(int i = 0; i < graph.visited.length; i++) {
graph.visited[i] = false;
}
graph.putUndirected(1, 2);
graph.putUndirected(2, 4);
graph.putUndirected(1, 3);
graph.printGraph();
graph.dfs(1);
}
}
public class DFSGraph2 {
int v;
ArrayList<ArrayList<Integer>> dfsGraph;
boolean[] visited;
public DFSGraph2(int v) {
this.v = v;
this.dfsGraph = new ArrayList<ArrayList<Integer>>();
this.visited = new boolean[this.v + 1];
for(int i = 0; i < this.v + 1; i++) {
this.dfsGraph.add(new ArrayList<Integer>());
}
}
public ArrayList<ArrayList<Integer>> getGraph(){
return this.dfsGraph;
}
// 무방향
public void putUndirected(int x, int y) {
this.dfsGraph.get(x).add(y);
this.dfsGraph.get(y).add(x);
}
// 방향
public void putDirected(int x, int y) {
this.dfsGraph.get(x).add(y);
}
// 탐색 (재귀)
public void dfs(int n) {
this.visited[n] = true;
System.out.print(n + " ");
for(int i : this.dfsGraph.get(n)) {
if (this.visited[i] == false) {
dfs(i);
}
}
}
// 출력
public void printGraph() {
for (int i = 0; i < this.dfsGraph.size(); i++) {
System.out.print(i + " :");
for(int j = 0; j < this.dfsGraph.get(i).size(); j++) {
System.out.print(" -> " + this.dfsGraph.get(i).get(j));
}
System.out.println();
}
}
public static void main(String[] args) {
int size = 4;
DFSGraph2 graph = new DFSGraph2(size);
// 방문 초기화
for(int i = 0; i < graph.visited.length; i++) {
graph.visited[i] = false;
}
graph.putUndirected(1, 2);
graph.putUndirected(2, 4);
graph.putUndirected(1, 3);
graph.printGraph();
graph.dfs(1);
}
}
너비 우선 탐색 (Breath-First Search)
- 시작 정점으로부터 가장 가까운 정점부터 방문하고 멀리 떨어져 있는 정점은 나중에 방문
- 넓게 탐색하는 것이 우선
- 두 정점 사이의 최단 경로를 찾고싶을 때 많이 사용
- 주로 큐와 반복문을 사용하여 구현
public class BFSGraph {
int v;
LinkedList<Integer>[] bfsGraph;
boolean[] visited;
public BFSGraph(int v) {
this.v = v;
this.bfsGraph = new LinkedList[v + 1];
this.visited = new boolean[this.v + 1];
for(int i = 0; i <= this.v; i++) {
this.bfsGraph[i] = new LinkedList<Integer>();
}
}
// 무뱡향
public void putUndirected(int x, int y) {
this.bfsGraph[x].add(y);
this.bfsGraph[y].add(x);
}
// 방향
public void putDirected(int x, int y) {
this.bfsGraph[x].add(y);
}
// 탐색
public void bfs(int n) {
Queue<Integer> queue = new LinkedList<Integer>();
visited[n] = true;
queue.add(n);
while(!queue.isEmpty()) {
int firstV = queue.poll();
System.out.print(firstV + " ");
for(int next : this.bfsGraph[firstV]) {
if(this.visited[next] == false) {
this.visited[next] = true;
queue.add(next);
}
}
}
System.out.println();
}
// 출력
public void printGraph() {
for (int i = 1; i <= this.v; i++) {
System.out.print(i + " :");
for (int j = 0; j < this.bfsGraph[i].size(); j++) {
System.out.print(" -> " + this.bfsGraph[i].get(j));
}
System.out.println();
}
}
public static void main(String[] args) {
int size = 4;
BFSGraph graph = new BFSGraph(size);
// 방문 초기화
for(int i = 0; i < graph.visited.length; i++) {
graph.visited[i] = false;
}
graph.putUndirected(1, 2);
graph.putUndirected(2, 3);
graph.putDirected(1, 3);
graph.printGraph();
graph.bfs(1);
}
}