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

[프로그래밍]

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

FeliZ_하늘.. 2017. 2. 16. 00:33

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);
            }
        }
    }
}

저작자표시 변경금지 (새창열림)