[자료구조 복습 13 ] 연결성분 찾기 (connected component)

연결성분

그래프에서 최대로 연결된 부분 그래프

 

어떻게 구할까

방법은 간단하다.

1. 정점을 차례대로 DFS/BFS 를 실행한다. -> 이때 방문되면 서로 연결되어 있음
2. 해당 visited 배열에 boolean 값 대신, 각각의 부분그래프를 나타낼 요소를 넣는다.
3. visted 배열을 돌려가며 가장 빈도수가 높은 숫자의 요소들을 출력한다.

* 아래 연결성분 찾는 메서드는 그래프의 간선이 1-2-3  4-5 이렇게 순차적으로 되어있다고 가정한것. 

- dfs 메서드를 포함한 graph 클래스 (인접리스트로 구현)

class Graph{
	private static int vn; //정점개수
	private static int[] visited; //방문여부
	private static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	
	public Graph(int vn)  //초기화 
	{
		this.vn=vn;
		visited= new int[vn];
		for(int i=0; i<vn;i++) {
			graph.add(new ArrayList<Integer>());
		}
	}

	public void setBoth(int v, int e) { //양방향 
		graph.get(v).add(e);
		graph.get(e).add(v);
	}
	
	public ArrayList<Integer> getNode(int i) //특정노드 반환 
	{
		return graph.get(i);
	}
	
	
	public void dfs(int v, int count) 
	{
		visited[v]=count; //true대신
		
		for(int i: graph.get(v)) {
			if(visited[i]==0) {
				dfs(i,count);
			}
		}	
	}
	
	public int getVisited(int i) {
		return visited[i];
	}
	
}

 

public class connected_components {
	private static int vn;
	public static void main(String[]args) 
	{
		vn = new Integer(5);
		Graph g = new Graph(vn);
		g.setBoth(0, 1);
		g.setBoth(1, 2);
		g.setBoth(3, 4);
		find_connected_component(g,vn);
	}
	
	
	private static void find_connected_component(Graph g, int vn) {
		int count = 0; 
		for(int i=0; i<vn ; i++)  
		{
			if(g.getVisited(i)==0) {
				count ++ ; //이렇게 count ++ 한 값을 visited에 넣어주면 부분 그래프가 구분된다. 
				g.dfs(i,count);
			}
		}
		//연결성분 출력 
		int len_count = 0; //빈도수  
		int max_len = 0; //가장 큰 빈도수 기록 
		int max_comp=0; //가장 큰 빈도수의 숫자 기록 
		int comp = 0 ;  
		
		for(int i=0; i<vn; i++) {
			if(i==0) comp=g.getVisited(i);
			if(g.getVisited(i)!=comp) { //부분그래프가 바뀔 때 
          		if(max_len<len_count) { //이전의 가장 큰 빈도수보다 현재 빈도수가 크다면 
          			max_len=len_count; //일단 연결성분으로 기록 
          			max_comp=comp;
          		}
          		comp=g.getVisited(i); //다음 부분그래프로 
          		len_count = 0;
          	}
          	len_count++; //빈도수 계산 
		}
		
		for(int i = 0; i<vn; i++) {
			if(g.getVisited(i)==max_comp) { //가장 큰 빈도수의 숫자 (연결성분의 count num) 찾기 
				System.out.println(i+" ");
			}
		}	
	}
}