깊이 우선 검색(DFS)

그래프의 깊이 우선 탐색은 그래프의 정점부터 시작하여 그래프의 모든 정점을 최대한 방문하여 역추적합니다.
그래프의 깊이 우선 탐색은 Tree Traversal, Tree Traversal에서 설명한 트리의 깊이 우선 탐색과 같습니다. 트리의 경우 루트부터 검색이 시작됩니다. 그래프에서는 모든 정점에서 검색을 시작할 수 있습니다.

트리에 대한 깊이 우선 검색은 먼저 루트를 방문한 다음 루트의 하위 트리를 재귀적으로 방문합니다. 마찬가지로, 그래프의 깊이 우선 검색은 먼저 정점을 방문한 다음 해당 정점에 인접한 모든 정점을 재귀적으로 방문합니다. 차이점은 그래프에 순환이 포함될 수 있으며 이로 인해 무한 재귀가 발생할 수 있다는 것입니다. 이 문제를 방지하려면 이미 방문한 정점을 추적해야 합니다.

그래프에서 최대한 '더 깊게' 검색하기 때문에 검색을 깊이 우선이라고 합니다. 검색은 일부 정점 v에서 시작됩니다. v를 방문한 후 v의 방문하지 않은 이웃을 방문합니다. v에 방문하지 않은 이웃이 없으면 검색은 v에 도달한 정점으로 역추적합니다. 그래프가 연결되어 있고 검색이 시작된다고 가정합니다. 모든 정점에서 모든 정점에 도달할 수 있습니다.

깊이 우선 검색 알고리즘

깊이 우선 탐색 알고리즘은 아래 코드에 설명되어 있습니다.

입력: G = (V, E) 및 시작 정점 v
출력: v
에 뿌리를 둔 DFS 트리 1 트리 dfs(정점 v) {
2 방문 v;
v의 각 이웃 w에 대해 3
4 if (w가 방문되지 않은 경우) {
5 트리에서 v를 w의 부모로 설정합니다.
6dfs(w);
7 }
8 }

isVisited라는 배열을 사용하여 정점을 방문했는지 여부를 나타낼 수 있습니다. 처음에는 각 정점 i에 대해 isVisited[i]가 false입니다. v라는 정점을 방문하면 isVisited[v]가 true로 설정됩니다.

아래 그림 (a)의 그래프를 살펴보세요. 정점 0에서 깊이 우선 탐색을 시작한다고 가정합니다. 먼저 0을 방문하고 그 다음 이웃인 1을 방문합니다. 이제 아래 그림(b)에 표시된 대로 1을 방문합니다. 정점 1에는 3개의 이웃(0, 2, 4)이 있습니다. 0은 이미 방문했으므로 2 또는 4를 방문하게 됩니다. 2를 선택하겠습니다. 이제 아래 그림(c)에 표시된 대로 2를 방문합니다. 정점 2에는 0, 1, 3이라는 세 개의 이웃이 있습니다. 0과 1은 이미 방문했으므로 3을 선택합니다. 아래 그림 (d)와 같이 이제 3을 방문합니다. 이 시점에서 정점은 다음 순서로 방문되었습니다.

0, 1, 2, 3

3의 이웃을 모두 방문했으므로 2로 백트랙합니다. 2의 모든 정점을 방문했으므로 1로 백트랙합니다. 4는 1과 인접하지만 4는 방문하지 않았습니다. 따라서 아래 그림 (e)와 같이 4번을 방문하세요. 4개의 이웃을 모두 방문했으므로 1로 되돌아갑니다.
1의 이웃을 모두 방문했으므로 0으로 되돌아갑니다. 0의 이웃을 모두 방문했으므로 검색이 종료됩니다.

각 모서리와 정점은 한 번만 방문하므로 dfs 방법의 시간 복잡도는 O(|E| + |V|)입니다. 여기서 | E|는 모서리 수를 나타내고 |V|는 정점 수

를 나타냅니다.

깊이 우선 검색 구현

위 코드의 DFS 알고리즘은 재귀를 사용합니다. 이를 구현하기 위해 재귀를 사용하는 것은 당연합니다. 또는 스택을 사용할 수도 있습니다.

dfs(int v) 메소드는 AbstractGraph.java의 164~193행에서 구현됩니다. 정점 v을 루트로 하는 Tree 클래스의 인스턴스를 반환합니다. 이 메소드는 searchOrder 목록(165행)에 검색된 정점을 저장하고 parent 배열(166행)에 있는 각 정점의 상위를 저장하며 isVisited 꼭지점을 방문했는지 여부를 나타내는 배열입니다(라인 171). 도우미 메서드 dfs(v, parent, searchOrder, isVisited)를 호출하여 깊이 우선 검색(174행)을 수행합니다.

재귀 도우미 방법에서는 정점 u부터 검색이 시작됩니다. u는 184행의 searchOrder에 추가되고 방문한 것으로 표시됩니다(185행). u의 방문하지 않은 각 이웃에 대해 메서드가 재귀적으로 호출되어 깊이 우선 검색을 수행합니다. 정점 e.v를 방문하면 e.v의 부모가 parent[e.v]에 저장됩니다(189행). 연결된 그래프 또는 연결된 구성 요소의 모든 정점을 방문하면 메서드가 반환됩니다.

아래 코드는 시카고에서 시작하여 위 그림의 그래프에 대한 DFS를 표시하는 테스트 프로그램을 제공합니다. 시카고에서 시작하는 DFS의 그래픽 그림은 아래 그림에 나와 있습니다.

public class TestDFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<String> graph = new UnweightedGraph<>(vertices, edges);
        AbstractGraph<String>.Tree dfs = graph.dfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = dfs.getSearchOrder();
        System.out.println(dfs.getNumberOfVerticesFound() + " vertices are searched in this DFS order:");
        for(int i = 0; i < searchOrders.size(); i++)
            System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
        System.out.println();

        for(int i = 0; i < searchOrders.size(); i++)
            if(dfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(dfs.getParent(i)));
    }

}

이 DFS 순서에서 12개의 정점이 검색됩니다.
시카고 시애틀 샌프란시스코 로스앤젤레스 덴버
캔자스시티 뉴욕 보스턴 애틀랜타 마이애미 휴스턴 달라스
시애틀의 부모는 시카고입니다
샌프란시스코의 부모는 시애틀입니다
로스앤젤레스의 부모는 샌프란시스코입니다
덴버의 부모는 로스앤젤레스입니다
캔자스 시티의 부모는 덴버입니다
보스턴의 부모는 뉴욕입니다
뉴욕의 부모는 캔자스시티입니다
애틀랜타의 부모는 뉴욕입니다
마이애미의 부모는 애틀랜타입니다
달라스의 부모는 휴스턴입니다
휴스턴의 부모는 마이애미입니다

DFS의 응용

깊이 우선 탐색은 다음과 같은 많은 문제를 해결하는 데 사용될 수 있습니다.

• 그래프 연결 여부를 감지합니다. 모든 정점에서 시작하여 그래프를 검색합니다. 검색된 꼭지점 개수와 그래프의 꼭지점 개수가 같으면 그래프가 연결됩니다. 그렇지 않으면 그래프가 연결되지 않습니다.
• 두 정점 사이에 경로가 있는지 감지합니다.
• 두 꼭짓점 사이의 경로 찾기
• 연결된 모든 구성 요소를 찾는 중입니다. 연결 구성 요소는 모든 정점 쌍이 경로로 연결되는 최대 연결 하위 그래프입니다.
• 그래프에 주기가 있는지 감지합니다.
• 그래프에서 순환을 찾아요.
• 해밀턴 경로/주기 찾기. 그래프의 해밀턴 경로는 그래프의 각 꼭지점을 정확히 한 번씩 방문하는 경로입니다. 해밀턴 순환은 그래프의 각 꼭지점을 정확히 한 번씩 방문하고 시작 꼭지점으로 돌아옵니다.

처음 6개 문제는 AbstractGraph.java의 dfs 메서드를 사용하여 쉽게 해결할 수 있습니다. 해밀턴 경로/주기를 찾으려면 가능한 모든 DFS를 탐색하여 가장 긴 경로로 이어지는 DFS를 찾아야 합니다. 해밀턴 경로/사이클은 잘 알려진 Knight's Tour 문제 해결을 포함하여 많은 응용 분야를 가지고 있습니다.

위 내용은 깊이 우선 검색(DFS)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!