[ 인접행렬과 인접리스트 ]
- 인접행렬 : 정점
int[][] a = new int[n + 1][n + 1];
for (int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
a[v1][v2] = 1;
a[v2][v1] = 1;
}
인접행렬은 정점(V)이 n개일때 N*N 이차원 배열로 나타낼수 있고 일반적으로 a라고 이름을 짓는다.
a[1][5] = 1 의 의미는 정점 1과 정점 5의 간선이 연결되어 있다는 뜻이다.(무방향이기에 a[5][1]도 1)
인접행렬의 값이 1이라면, 정점간의 간선이 존재한다는 것이고, 0이라면 존재하지 않는다는 것이다.
(현재는 가중치가 없지만, 가중치를 넣을 때는 1 대신 가중치를 넣으면 됨)
- 인접리스트 : 간선
ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
a[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
a[v1].add(v2);
a[v2].add(v1);
}
1에 연결되어있는 간선(E)들을 A[1] 에 저장하고, A[2]에는 2에 연결되어있는 간선을 저장했다.
같은 목적이지만 배열과 리스트를 통해 다르게 저장함으로써 큰 차이를 볼 수 있다.
인접행렬은 크기가 정점과 간선의 갯수와 사관없이 정점갯수 * 정점갯수 이기 때문에 공간복잡도가 O(v^2) 이다.
하지만 인접리스트는 필요한 공간만 쓰기 때문에 O(V+E) 가 된다.
인접행렬이 익숙하고, 조금 더 쉽게 이해할 수 있어 많이 사용한다.
하지만 보다시피 인접행렬을 쓰는 것보다는 인접리스트가 효율적이다!
[ DFS와 BFS ]
두 탐색 모두 모든 정점을 한번만 방문하기 때문에 탐색의 여부를 확인하기 위한
check배열이 필요하고 DFS는 스택을 사용, BFS는 큐를 사용한다.
*무방향 그래프 기준
- DFS : 깊이 우선 탐색 (Depth-First Search)
변수 a: 인접행렬 / c: 방문여부 / v: 정점
> 재귀형식
public static void dfs(int[][] a, boolean[] c, int v) {
int n = a.length - 1;
c[v] = true;
System.out.print(v + " ");
for (int i = 1; i <= n; i++) {
if (a[v][i] == 1 && !c[i]) {
dfs(a, c, i);
}
}
}
스택을 사용한다고 하지만 많은 분들이 재귀를 통해 구현한다고한다.
> 스택형식
public static void dfs(int[][] a, boolean[] c, int v, boolean flag) {
Stack<Integer> stack = new Stack<>();
int n = a.length - 1;
stack.push(v);
c[v] = true;
System.out.print(v + " ");
while (!stack.isEmpty()) {
int vv = stack.peek();
flag = false;
for (int i = 1; i <= n; i++) {
if (a[vv][i] == 1 && !c[i]) {
stack.push(i);
System.out.print(i + " ");
c[i] = true;
flag = true;
break;
}
}
if (!flag) {
stack.pop();
}
}
}1. 스택의 top에 있는 정점을 기준으로 간선이 연결되어있고 아직 방문하지 않은 정점을 찾는다.
2. 조건에 맞는 정점을 찾는다면 해당 정점을 스택에 넣은 후 break를 건다.
3. 연결된 간선이 없고, 방문하지 않은 정점을 찾지 못한다면 pop.
2번에서 break를 걸어줌으로써, 바로 DFS 탐색이 진행된다.
현재 정점을 기준으로 탐색 중 조건에 맞는 정점을 찾는다면 그 정점을 기준으로 다시 탐색을 한다.
이를 반복함으로써 위 DFS의 그림처럼 깊이 탐색을 할 수 있게 되는 것이다.
3번에서 경우는 DFS와 BFS를 비교하는 그림에서 보듯 1, 2, 3을 탐색한 후 더이상 탐색할 수 없다.
이런 경우를 다시 돌아가기 위해 pop을 하는 것이다.
위와 같이 스택을 통해 구현한 것이 재귀로 바꾼 것 뿐이다.
다른 점은 없다. 단순히 재귀로 바꾼 것 뿐이다.
- BFS : 너비 우선 탐색 (Breadth-First Search)
public static void bfs(int[][] a, boolean[] c, int v) {
Queue<Integer> q = new LinkedList<>();
int n = a.length - 1;
q.add(v);
c[v] = true;
// 인접 행렬
while (!q.isEmpty()) {
v = q.poll();
System.out.print(v + " ");
for (int i = 1; i <= n; i++) {
if (a[v][i] == 1 && !c[i]) {
q.add(i);
c[i] = true;
}
}
}
// 인접리스트
while (!q.isEmpty()) {
v = q.poll();
System.out.print(v + " ");
for (int vv : a[v]) {
if (!c[vv]) {
q.add(vv);
c[vv] = true;
}
}
}
}1. 큐의 front인 정점을 기준으로 연결된 간선이 있고, 방문하지 않은 정점을 찾는다.
2. 조건에 맞는 정점은 모두 큐에 넣는다.
위 과정을 반복한다.
DFS의 경우에는 break문을 걸어줬다.
하지만 BFS는 모두 큐에 넣음으로써 이름처럼 너비를 기준으로 탐색한다.
그렇기에 모든 경우를 탐색할 수 있게 됨으로써, 최단 경로에 이용한다고도 말을 할 수 있는 것이다.
마지막으로 인접 리스트를 조금 더 보겠다.
위에서 공간복잡도를 통해 인접행렬과 비교를 해보았다.
시간복잡도 측면에서도 효율적이다. 이유를 보자.
인접 행렬의 경우 정점을 탐색하는 과정에서 무조건 1에서 n까지 루프를 돌았다.
인접 리스트의 경우에는 리스트 특성상 각 리스트마다 존재하는 정점만큼 존재한다.
그렇기에 i에서 n까지 돌지 않아도 되고, 위와 같이 존재하는 만큼만 탐색하면 된다.
인접 리스트의 경우는 Github을 통해 확인하길 바란다.
단순히 인접행렬과 인접리스트의 차이다.
깊게 생각해서 헷갈리지 말길 바란다.
출처 : mygumi.tistory.com/102#recentEntries