너비 우선 검색(BFS)

그래프의 너비 우선 검색은 수준별로 정점을 방문합니다. 첫 번째 수준은 시작 정점으로 구성됩니다. 다음 각 레벨은 이전 레벨의 정점에 인접한 정점으로 구성됩니다. 그래프의 너비 우선 순회는 트리 순회에서 설명한 트리의 너비 우선 순회와 같습니다. 트리의 너비 우선 순회를 사용하면 노드가 수준별로 방문됩니다. 먼저 루트를 방문한 다음 루트의 모든 자식, 루트의 손자 등을 방문합니다. 마찬가지로, 그래프의 너비 우선 검색은 먼저 정점을 방문한 다음 모든 인접한 정점, 그런 다음 해당 정점에 인접한 모든 정점 등을 방문합니다. 각 정점이 한 번만 방문되도록 하기 위해 이미 방문한 정점은 건너뜁니다.

너비 우선 검색 알고리즘

그래프의 정점 v부터 시작하는 너비우선탐색 알고리즘은 아래 코드에 설명되어 있습니다.

입력: G = (V, E) 및 시작 정점 v
출력: v
에 뿌리를 둔 BFS 트리 1 트리 bfs(정점 v) {
2 방문할 정점을 저장하기 위한 빈 대기열을 만듭니다.
3 대기열에 v를 추가합니다.
4 마크v 방문;
5
6 while(큐가 비어 있지 않음) {
7 큐에서 정점(예: u)을 큐에서 제거합니다.
8 탐색된 정점 목록에 u를 추가합니다.
당신의 이웃 w당 9
w를 방문하지 않은 경우 10 {
11 대기열에 w를 추가하세요.
12 u를 트리의 w에 대한 부모로 설정합니다.
13시 방문;
14 }
15 }
16 }

아래 그림 (a)의 그래프를 살펴보세요. 정점 0에서 너비 우선 검색을 시작한다고 가정합니다. 아래 그림 (b)에 표시된 대로 먼저 0을 방문한 다음 모든 이웃인 1, 2, 3을 방문합니다. 정점 1에는 0, 2, 4라는 세 개의 이웃이 있습니다. 0과 2는 이미 방문했으므로 아래 그림(c)에 표시된 것처럼 이제 4만 방문합니다. 정점 2에는 0, 1, 3이라는 세 개의 이웃이 있으며 모두 방문되었습니다. 정점 3에는 0, 2, 4라는 세 개의 이웃이 있으며 모두 방문했습니다. 정점 4에는 두 개의 이웃 1과 3이 있으며 모두 방문되었습니다. 이로써 검색이 종료됩니다.

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

를 나타냅니다.

너비 우선 검색 구현

bfs(int v) 메소드는 Graph 인터페이스에 정의되고 AbstractGraph.java 클래스(197~222행)에 구현됩니다. 정점 v가 루트인 Tree 클래스의 인스턴스를 반환합니다. 이 메소드는 검색된 정점을 searchOrder 목록(198행)에 저장하고, parent 배열(199행)에 있는 각 정점의 부모는 대기열(199행)에 연결된 목록을 사용합니다. 203–204), isVisited 배열을 사용하여 정점을 방문했는지 여부를 나타냅니다(라인 207). 검색은 정점 v부터 시작됩니다. v는 206행의 대기열에 추가되고 방문한 것으로 표시됩니다(207행). 이제 메서드는 대기열의 각 정점 u를 검사하고(라인 210) 이를 searchOrder에 추가합니다(라인 211). 이 메서드는 u의 방문하지 않은 각 이웃 e.v를 대기열에 추가하고(라인 214), 해당 부모를 u로 설정하고(라인 215), 방문한 것으로 표시합니다. (216행).

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

public class TestBFS {

    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 bfs = graph.bfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = bfs.getSearchOrder();
        System.out.println(bfs.getNumberOfVerticesFound() + " vertices are searched in this BFS 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(bfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(bfs.getParent(i)));
    }

}

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

BFS의 응용

DFS로 해결한 많은 문제는 BFS를 사용해도 해결할 수 있습니다. 구체적으로 BFS를 사용하면 다음과 같은 문제를 해결할 수 있습니다.

• 그래프 연결 여부를 감지합니다. 그래프의 두 꼭지점 사이에 경로가 있으면 그래프가 연결됩니다.
• 두 정점 사이에 경로가 있는지 감지합니다.
• 두 꼭짓점 사이의 최단 경로 찾기. BFS 트리의 루트와 노드 사이의 경로가 루트와 노드 사이의 최단 경로임을 증명할 수 있습니다.
• 연결된 모든 구성 요소를 찾는 중입니다. 연결 구성 요소는 모든 정점 쌍이 경로로 연결되는 최대 연결 하위 그래프입니다.
• 그래프에 주기가 있는지 감지합니다.
• 그래프에서 순환을 찾아요.
• 그래프가 이분형인지 테스트합니다. (그래프의 정점이 두 개의 서로소 집합으로 분할되어 동일한 집합의 정점 사이에 간선이 존재하지 않는 경우 그래프는 이분형입니다.)

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