06 연결 집합 목록 (자바 구현)

연결 집합 목록 (25 분)
N 개의 정점 과 E 개의 변 이 있 는 무 방향 그림 을 지정 합 니 다. DFS 와 BFS 로 각각 모든 연결 집합 을 보 여 주 십시오.정점 을 0 에서 N - 1 번 으로 가정 하 다.검색 을 할 때, 우리 가 항상 번호 가 가장 작은 정점 에서 출발 하여 번호 가 증가 하 는 순서에 따라 인접 지점 에 접근한다 고 가정 합 니 다.
입력 형식:
첫 번 째 줄 을 입력 하여 정수 N 2 개 주기 (0)
출력 형식:
"{v1, v2,... vk}" 형식 으로 줄 마다 연결 집합 을 출력 합 니 다. DFS 결 과 를 먼저 출력 하고 BFS 결 과 를 출력 합 니 다.
입력 예시:
8 6 0 7 0 1 2 0 4 1 2 4 3 5
출력 예시:
{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 }
사고의 방향

		                          
		1、     ，        
				        
		2、    
				      
				      

import java.util.*;

public class ListConnectedSetDemo 
{
	public static void main(String[] args) 
	{
		/**
			                          
			1、     ，        
					        
			2、    
					      
					      
		*/
		Scanner scan = new Scanner(System.in);
		String[] s = scan.nextLine().split(" ");
		int vertex = Integer.parseInt(s[0]);	
		int edge = Integer.parseInt(s[1]);

//1、           
		int[][] map = new int[vertex][vertex];
		int[] visited = new int[vertex];
		for(int i=0; i<edge; i++){
			String[] s1 = scan.nextLine().split(" ");
			int vertex1 = Integer.parseInt(s1[0]);
			int vertex2 = Integer.parseInt(s1[1]);
			map[vertex1][vertex2] = 1;
			map[vertex2][vertex1] = 1;
		}

//2.1       。    i  vertex   ，     vertex*vertex   
		for(int i=0; i<vertex; i++){
			if(visited[i]!=1){		//   i   
				visited[i] = 1;
				System.out.print("{");
				dfs(i, vertex, visited, map);		//   i        vertex   。   ：    i，  vertex，visited  (       ，      visited)，    map[][]
				System.out.println("}");
			}
		}

		reset(visited);

//2.2       
		for(int i=0; i<vertex; i++){
			if(visited[i]!=1){
				visited[i] = 1;
				System.out.print("{");
				Queue<Integer> queue = new LinkedList<Integer>(); 
				queue.add(i);
				System.out.print(i+" ");
				while(!queue.isEmpty()){
					bfs( queue, vertex, visited, map);
				}
				System.out.println("}");
			}
		}

		scan.close();
	}

	//        。  root    ，       
	public static void dfs(int root, int vertex, int[] visited,int[][] map){
		System.out.print(root+" ");		//         
		//      
		for(int i=0; i<vertex; i++){
			if(visited[i]!=1 && map[root][i]==1){
				visited[i] = 1;
				dfs(i, vertex, visited, map);
			}
		}
	}
	
	//      。
	public static void bfs(Queue<Integer> queue, int vertex, int[] visited,int[][] map){
		int root = queue.poll();		//         
		for(int j=0; j<vertex; j++){
			if(visited[j]!=1 && map[root][j]==1){
				visited[j] = 1;
				queue.add(j);
				System.out.print(j+" ");
			}
		}
	}

	//reset  ，        ， visited    0，        
	public static void reset(int[] visited){
		for(int i=0; i<visited.length; i++){
			visited[i] = 0;
		}
	}
}