[section 2] 알고리즘(2) - DFS, BFS

DFS 깊이 우선 탐색

public static void DFS(int[][] matrix, int vertex, boolean[] visited) {
	visited[vertex] = true;
    for (int v = 0; v < matrix.length; v++)
        if (matrix[vertex][v] == 1 && !visited[v])
            DFS(matrix, v, visited);
}

BFS 너비 우선 탐색

private static void BFS(int[][] matrix, int vertex, boolean[] visited) {
	List<Integer> queue = new ArrayList<>();
    queue.add(vertex);
    while (queue.size() > 0) {
    	vertex = queue.remove(0);
        visited[vertex] = true;
        for (int i = 0; i < matrix.length; i++)
        	if (matrix[vertex][i] == 1 && !visited[i]) queue.add(i);
	}
}

connected component 연결 성분

public static int connectedVertices(int[][] matrix, int vertexNum) {
	boolean[] visited = new boolean[size + 1];
	int count = 0;
    for (int v = 0; v < vertexNum; v++) {
    	if (!visited[v]) {
        	count++;
            DFS(matrix, v, visited);
        }
    }
    return count;
}