dfs 알고리즘을 java 로 구현하기

dfs 알고리즘

import java.util.Scanner; /** * dfs algorithm. * * @author hskimsky */ public class Dfs { private static int numberOfVertex; private static int numberOfEdge; private static int[][] adjacencyMatrix;// 인접행렬 private static boolean[] search; /* /-2 1 | \-3-4-5 input number of vertex: 5 input number of edge : 5 input vertex of start : 1 input vertex of end : 2 input vertex of start : 1 input vertex of end : 3 input vertex of start : 2 input vertex of end : 3 input vertex of start : 3 input vertex of end : 4 input vertex of start : 4 input vertex of end : 5 print adjacency matrix 1: 01100 2: 10100 3: 11010 4: 00101 5: 00010 search 1: 1 0 0 0 0 search 2: 1 1 0 0 0 search 3: 1 1 1 0 0 search 4: 1 1 1 1 0 search 5: 1 1 1 1 1 /-4-\ /-2 \ / \-5-\ \ 1 --8 \ /-6-/ / \-3 / \-7-/ input number of vertex: 8 input number of edge : 10 input vertex of start : 1 input vertex of end : 2 input vertex of start : 1 input vertex of end : 3 input vertex of start : 2 input vertex of end : 4 input vertex of start : 2 input vertex of end : 5 input vertex of start : 3 input vertex of end : 6 input vertex of start : 3 input vertex of end : 7 input vertex of start : 4 input vertex of end : 8 input vertex of start : 5 input vertex of end : 8 input vertex of start : 6 input vertex of end : 8 input vertex of start : 7 input vertex of end : 8 print adjacency matrix 1: 01100000 2: 10011000 3: 10000110 4: 01000001 5: 01000001 6: 00100001 7: 00100001 8: 00011110 search 1: 1 0 0 0 0 0 0 0 search 2: 1 1 0 0 0 0 0 0 search 4: 1 1 0 1 0 0 0 0 search 8: 1 1 0 1 0 0 0 1 search 5: 1 1 0 1 1 0 0 1 search 6: 1 1 0 1 1 1 0 1 search 3: 1 1 1 1 1 1 0 1 search 7: 1 1 1 1 1 1 1 1 */ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("input number of vertex: "); numberOfVertex = scanner.nextInt(); System.out.print("input number of edge : "); numberOfEdge = scanner.nextInt(); adjacencyMatrix = new int[numberOfVertex][numberOfVertex]; search = new boolean[numberOfVertex]; for (int i = 0; i < numberOfEdge; i++) { System.out.print("input vertex of start : "); int startVertex = scanner.nextInt() - 1; System.out.print("input vertex of end : "); int endVertex = scanner.nextInt() - 1; adjacencyMatrix[startVertex][endVertex] = 1; adjacencyMatrix[endVertex][startVertex] = 1; } System.out.println("print adjacency matrix"); for (int i = 0; i < numberOfVertex; i++) { System.out.print((i + 1) + ": "); for (int j = 0; j < numberOfVertex; j++) { System.out.print(adjacencyMatrix[i][j]); } System.out.println(); } int searchStartVertex = 1; dfs(searchStartVertex); } public static void dfs(int vertex) { search[vertex - 1] = true; System.out.print("search " + vertex + ": "); for (int i = 0; i < search.length; i++) { System.out.print((search[i] ? 1 : 0) + " "); } System.out.println(); for (int endVertex = 1; endVertex <= adjacencyMatrix[vertex - 1].length; endVertex++) { int edge = adjacencyMatrix[vertex - 1][endVertex - 1]; if (edge == 1 && !search[endVertex - 1]) { dfs(endVertex); } } } }