Java 자료구조(Data Structure) - 그래프 (Graph) & 그래프 서치 (Graph Search)

그래프(Graph)란?

자료구조에서 그래프는 여러 개의 점들이 서로 복잡하게 연결 되어있는 관계를 표현한 자료 구조 이다.

그래프의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.
• 하나의 점을 그래프에서는 정점(vertex)이라고 표현하며, 하나의 선은 간선(edge)라고 한다.

인접 행렬

그래프 표현 방식 중 하나로 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1, 이어져 있지 않다면 0 으로 표시한 일종의 표이다.위의 그래프를 인접 행렬로 표시하면 다음과 같은 2차원 배열로 나타낼 수 있다.

int[][] matrix = new int[][]{
	{0, 0, 1}, // A정점에서 이동 가능한 정점을 나타내는 행
	{1, 0, 1}, // B정점에서 이동 가능한 정점을 나타내는 행
	{1, 0, 0}. // C정점에서 이동 가능한 정점을 나타내는 행
};

• A의 진출차수는 1개입니다: A → C
  • [0][2] == 1
• B의 진출차수는 2개입니다: B → A, B → C
  • [1][0] == 1
  • [1][2] == 1
• C의 진출차수는 1개입니다: C → A
  • [2][0] == 1

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며 이 리스트는 자신과 인접한 다른 정점을 담고 있다. 위 그래프를 인접 리스트로 표현하면 다음 그림과 같다.

// A, B, C는 각각의 인덱스로 표기한다. 0 == A, 1 == B, 2 == C
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    graph.add(new ArrayList<>(Arrays.asList(2, null)));
    graph.add(new ArrayList<>(Arrays.asList(0, 2, null)));
    graph.add(new ArrayList<>(Arrays.asList(0, null)));

graph.get(0) == [2, null] == 0 -> 2 -> null
graph.get(1) == [0, 2, null] == 1 -> 0 -> 2 -> null
graph.get(2) == [0, null] == 2 -> 0 -> null

 

인접 리스트는 메모리를 효율적으로 사용하고 싶을 때 사용한다. 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.

반응형

너비 우선 탐색 BFS(Breadth-First Search)

너비 우선 탐색(Breadth First Search, BFS)은 한 정점을 기준으로 해당 기준에서 인접한 정점을 모두 방문한 후에 방문한 정점을 기준으로 변경하고, 변경된 기준에서 인접한 정점을 차례대로 방문한다. 너비 우선탐색의 특징은 다음과 같다.

1. 하나의 정점을 기준으로 해당 정점과 인접한 정점을 모두 방문한다.
2. 기준점을 방문했던 정점으로 변경하여 해당 정점에서 인접한 정점을 방문한다.
3. 이 과정을 통해 최상위 정점을 기준으로 이어진 정점을 차례대로 방문한다.
4. 최단 경로 탐색에 유리하다.
   BFS는 루트 정점에서부터 거리가 가까운 정점을 먼저 방문하므로, 최단 경로를 찾는 문제에서 유용하다. 그래프에서 두 정점 사이의 최단 경로를 찾을 때도 BFS를 사용한다. 이는 DFS와 달리 같은 거리에 있는 정점들을 먼저 방문하기 때문이다.
5. 방문한 정점들을 저장해야 하는 경우 메모리 사용이 크다.
   BFS는 큐 자료구조를 사용하기 때문에 방문한 정점들을 큐에 저장하고 있어야 한다. 이때 그래프의 크기가 크면 큐에 저장되는 정점들의 수가 많아지기 때문에 많은 메모리를 사용해야 한다는 큰 단점이 있다.
6. 그래프의 크기와 밀도에 따라 성능이 달라진다.
   그래프의 밀도가 높거나(간선의 개수가 많거나) 그래프의 크기가 크면(정점의 개수가 많으면) BFS 성능이 저하될 수 있다.
7. 시작 정점에서 도달할 수 없는 정점은 탐색하지 않는다.
   따라서 시작 정점에서 도달할 수 있는 정점들만 탐색할 때 사용한다.
8. visited 배열과 같은 방문 여부를 체크하는 자료 구조를 사용해야 한다.
   방문 여부를 체크하는 자료 구조를 사용하지 않는다면 무한 루프에 빠질 수 있다.

구현 방법

BFS는 큐 자료구조를 활용하여 구현된다. 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 방식으로 동작한다. 따라서 BFS에서는 시작 노드를 큐에 삽입한 후 인접한 노드를 큐에 순차적으로 삽입하며 탐색한다. BFS에서는 visited 배열과 같은 방문 여부를 체크하는 자료 구조를 사용해야 한다. 그렇지 않으면 무한 루프에 빠질 수 있다.

1. BFS는 큐(Queue)자료 구조를 활용하여 구현된다.
2. 시작 노드를 큐에 삽입한 후 큐가 빌 때까지 반복을 시작한다.
3. 큐에서 현재 정점을 가져온다.(queue.poll() 활용)
4. 현재 정점은 이미 이동했다고 방문 여부를 체크한다. ex) visitied[index] = true;
5. poll() 을 활용해 가져온 정점을 기준으로, 인접한 장점을 모두 큐에 삽입한다. (queue.offer() 활용)
6. 다시 반복으로 돌아와서, 큐가 빌 때까지 인접한 정점을 모두 큐에 삽입하여 그래프를 끝까지 순회한다.

    /**
     * BFS 인접행렬 : 너비 우선 탐색을 구현한 템플릿 예제
     *
     * @param array : 각 정점을 행/열로 하고, 연결된 정점은 1로, 연결되지 않은 정점은 0으로 표기하는 2차원 배열
     * @param visited : 방문여부 확인을 위한 배열
     * @param src : 방문할 정점
     * @param result : 방문했던 정점 리스트를 저장한 List
     *
     **/
    public ArrayList<Integer> bfs_array(int[][] array, boolean[] visited, int src, ArrayList<Integer> result) {
			//bfs의 경우 큐를 사용
	    Queue<Integer> queue = new LinkedList<>();
			//시작 지점을 큐에 넣어주고, 해당 버택스의 방문 여부를 변경
	    queue.offer(src);
	    visited[src] = true;
			//큐에 더이상 방문할 요소가 없을 경우까지 반복
	    while (!queue.isEmpty()) {
				//현재 위치를 큐에서 꺼낸 후
	      int cur = queue.poll();
				// 현재 방문한 정점을 result에 삽입
				result.add(cur);
				//전체 배열에서 현재 버택스의 행만 확인
	      for (int i = 0; i < array[cur].length; i++) {
					//길이 존재하고, 아직 방문하지 않았을 경우
	        if(array[cur][i] == 1 && !visited[i]) {
						//큐에 해당 버택스의 위치를 넣어준 이후
	          queue.offer(i);
						//방문 여부를 체크
	          visited[i] = true;
	        }
	      }
	    }
			//이어진 모든 길을 순회한 후 방문 여부가 담긴 ArrayList를 반환
	    return result;
  }

깊이 우선 탐색 DFS(Depth-First Search)

깊이 우선 탐색(Depth First Search, DFS)은 시작 정점에서부터 최대한 깊숙히 탐색을 진행하고 더 이상 탐색이 불가할 때 이전 단계로 돌아와 다음 분기로 탐색을  진행하는 알고리즘이다. 깊이 우선 탐색은 아래와 같은 특징이 있다.

1. 한 분기를 탐색 후 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.
2. 더 이상 탐색이 불가능한 상태가 되면 이전 분기로 돌아와 다음 분기를 탐색한다.
   하나의 노선을 끝까지 확인하기에 운이 좋다면 단 몇 번 만에 경로를 찾을 수 있다. BFS 보다 시간은 걸려도 모든 정점을 완전히 탐색할 수 있다. 그리고 현 경로상의 정점듦나을 기억하면 되므로 저장공간 수요가 비교적 적고 목표한 정점이 깊은 단계에 있으면 해를 빨리 구할 수 있다.
3. 깊이 우선 탐색은 그래프 내의 순환구조(Cycle)를 고려하여 방문한 정점을 확인하여 이미 방문한 정점을 다시 방문하지 않도록 해야 한다.
   도달할 정점이 없다면 무한 루프에 빠질 수 있다. 그리고 찾아낸 길이 최단 경로가 되지는 않는다.

구현 방법

1. 스택(Stack) 자료 구조나 재귀를 통해 구현할 수 있으며 일반적으로 재귀를 통해 구현한다.
2. 방문했던 정점인지 확인한다. 방문했다면 재귀 호출을 종료한다. 
   단순 출력이 아닌 방문 여부를 저장할 데이터가 필요하다면 해당 데이터에 방문 여부를 저장한 후 저장 데이터를 반환한다.
3. 방문하지 않았다면 방문 여부를 체크한다.
4. 해당 정점에 연결된 모든 정점을 재귀호출로 순회한다.

    /**
     * DFS 인접행렬 : 깊이 우선 탐색을 구현한 템플릿 예제
     *
     * @param array : 각 정점을 행/열로 하고, 연결된 정점은 1로, 연결되지 않은 정점은 0으로 표기하는 2차원 배열
     * @param visited : 방문 여부 확인을 위한 배열
     * @param src : 방문할 정점
     * @param result : 방문했던 정점 리스트를 저장한 List
     *
     **/
    public ArrayList<Integer> dfs(int[][] array, boolean[] visited, int src, ArrayList<Integer> result) {
				// 이미 방문했다면
        if (visited[src] == true) {
					result.add(src);    // 방문한 정점을 저장
					return result;      // 저장한 데이터를 반환하며, 재귀호출을 종료
				}

				// 아직 방문하지 않았다면
        visited[src] = true;           // 방문한 정점을 표기

				// 현재 정점에서 이동할 수 있는 정점을 순회하며 재귀 호출
        for (int index = 0; index < array.length; index++) {
            if (array[src][index] == 1) {
								// 재귀 호출을 통해, 방문 여부를 담은 데이터를 반환과 동시에 할당
                result = dfs(array, visited, index, result);
            }
        }
				return result;
    }