본 글에서는 Java 기반의 그래프용 너비우선 탐색 알고리즘의 구현 방법을 예시 형태로 설명한다.
인접 행렬을 사용하여 그래프 방법 저장:
1. 그래프의 꼭지점과 모서리 수를 결정합니다.
2. 입력된 정점 정보는 1차원 배열 정점에 저장됩니다.
3. 인접 행렬을 초기화합니다.
4. 각 모서리를 차례로 입력하고 인접 행렬 호에 저장합니다.
가장자리에 연결된 두 정점의 일련 번호 i와 j를 입력합니다.
인접 행렬의 i번째 행과 j번째 열의 요소 값을 1로 설정합니다.
인접 행렬의 j번째 행과 i번째 열의 요소 값을 1로 설정합니다.
너비 우선 순회 구현:
1. 큐 Q 초기화
2. 정점 v를 방문합니다. 방문[v]=1이 대기열 Q에 추가됩니다.
3.while(큐 Q가 비어 있지 않음)
v=큐 Q의 선두 요소가 큐에서 제거됩니다.
w = 꼭지점 v의 첫 번째 인접 점
동안(w가 존재함)
w를 방문하지 않은 경우 정점 w를 방문합니다. 방문[w]=1은 대기열 Q에 넣습니다.
w=꼭지점 v의 다음 인접점
구현 코드는 다음과 같습니다.
패키지 com.teradata.lsw.sort;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;public class BFS {//스토리지 노드 정보 private Object[] vertices;//저장 가장자리 정보 배열 private int[][] arcs;//가장자리 수 private int vexnum;// i번째 노드 방문 여부 기록 private boolean[] Visit;//이동한 노드를 저장하기 위한 임시 연결 리스트 생성 private List<Object> temp = new ArrayList<Object>();/*** @param args* * @author TD_LSW*/public static void main(String[] args) {// TODO 자동 생성 메서드 stubBFS g = new BFS(8);Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };g.addVertex(정점);g.addEdge(0, 1);g .addEdge(0, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(3, 5);g.addEdge(4, 5);g.addEdge(2, 6);g.addEdge(2, 7);System.out.println("그래프의 너비 우선 순회:");g.bfs();}//너비- 첫 번째 순회 구현 private void bfs() {// TODO 자동 생성 메서드 stubfor (int i = 0; i < vexnum; i++) {visited[i] = false;}Queue<Integer> q = new LinkedList<Integer>();for (int i = 0; i < vexnum; i++) {if (!visited[i]) {visited[i] = true;visit(i );q.add(i);while (!q.isEmpty()) {int j = (정수) q.remove().intValue();//모든 순회가 완료되면 루프를 반복할 필요가 없다고 판단합니다. if (temp.size() == vexnum) {q.removeAll(q);return;}for ( int k = this .firstAdjVex(j); k >= 0; k = this.nextAdjVex(j, k)) {if (!visited[k]) {q.add(k);visited[k] = true;visit(k);}}}}}}// 다음 노드 찾기 public int firstAdjVex(int i) {for (int j = 0; j < vexnum ; j++) {if (arcs[i][j] > 0)return j;}return -1;}public int nextAdjVex(int i, int k) {for (int j = k + 1; j < vexnum; j++) {if (arcs[i][j] > 0)return j;}return -1;}//그래프 가장자리 초기화 private void addEdge(int i, int j) {/ / TODO 자동 생성 메서드 stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// 그래프 노드 초기화 private void addVertex(Object[] object) {// TODO 자동 생성 메서드 stubthis.vertices = object;}// 그래프 초기화 public BFS(int n) {// TODO 자동 생성 생성자 stubvexnum = n ;정점 = 새 객체[n];arcs = 새 int[n][n];visited = 새 부울[n];for (int i = 0; i < vexnum; i++) {for (int j = 0; j < vexnum; j++) {arcs[i][j] = 0;}}}private void Visit(int i) {// TODO 자동 생성 메서드 stubtemp .add(정점[i]);System.out.print(정점[i] + " ");}}