[Algorithm]그래프(Graph)의 정의 - 그래프의 순회

1. 그래프 순회란? : 주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점을 방문하는 것

2. 그래프 순회의 종류

   a. DFS(깊이 우선 탐색)

     i) 동작: 정점 i 방문 -> 인접한 정점 중 아직 방문하지 않은 정점을 스택(stack)에 저장 ->  스택에서 정점 삭제 후 새로운                      i 설정 -> 공백 시 연산 종료

     ii) 정점 방문 여부를 배열로 표현: visited[i] = { true or false}

     iii) 알고리즘

DFS(i) // i=시작 정점
	for(i<-0; i<n; i<-i+1) do 
    	visited[i] <- false;   // 방문x로 초기화
    stack <- createStack(); 
    push(stack, i);    // 시작 정점 i를 스택에 저장
    while(not isEmpty(stack)) do{
    	j <- pop(stack)  // 공백 될 떄까지 반복처리
        if(visited[j] = false) then {  // j 방문하지 않았다면
        	visit j;
            visited[j] <- true;
            for(each k in adjacency(j)) do{ 
            	if(visited[k]=false) // j에 인접한 정점 중 
                	push(stack,k); // 방문x 정점 스택에 저장
            }
        }

    b. BFS(너비 우선 탐색)

       i) 동작: 정점 i방문 -> 인접 정점 중 방문x 정점 모두 큐(queue)에 저장 -> 큐에서 정점 삭제 후 새로운 i설정 -> 큐 공백                  시 종료

       ii) 알고리즘

BFS(i) // i는 시작 정점
	for(i<-0; i<n; i<-i+1) do
    	visited[i] <- false   // 초기화
    queue <- createQ();       // 방문 정점을 저장하는 큐
    enqueue(queue, i);
    while(not isEmpty(queue)) do{
    	j <- dequeue(queue);
        if(visited[j]=false) then {
        	visit j;
            visited[j] <- true;
        }
        for(each k in adjacency(j)) do{
        	if(visited[k] = false) then
            	enqueue(queue, k);
        }
    }

DFS     vs     BFS

3. 연결 요소

    a. 연결 그래프 여부 판별 방법: DFS-BFS이용, 하나 정점 i로 시작해 DFS로 방문한 노드집합 V와같으면 연결그래프

    b. 연결 요소 찾기 방법: DFS-BFS 수행, 2개 이상 연결요소 있다면 방문안한 나머지 정점 j에 대해 DFS-BFS 수행

    c. 알고리즘

dfsComponent(G, n) // G = (V,E), n은 G의 정점 수
	for(i<-0; i<n; i<-i+1) do
    	visited[i] <- false;
    for(i<-0; i<n; i<-i+1) do{ // 모든 정점에 대해 검사
    	if(visited[i]=false) then{
        	print("new component");
            DFS(i)  // 정점 i가 포함된 연결 요소 탐색
        }
    }

4. 신장 트리

    a. 신장트리: 그래프G에서 E(G)에 있는 간선과 V(G)에 있는 모든 정점으로 구성된 트리                       

 

        

   b. 트리간선(tree edge)

      i) G가 연결그래프일 때: 트리간선과 비트리 간선으로 나뉨

         - 트리간선 구하는법: 간선(j,k)의 집합 = T라할때, 명령문 T <- T∪{(j,k)}삽입

        - T 간선 전부 결합시키면 트리가 된다 = 트리간선

   c. 신장 트리의 종류

       i) 깊이 우선 신장 트리(depth first spanning tree): DFS사용

       ii) 너비 우선 신장 트리(breadth first spanning tree): BFS사용

   d. 비트리 간선(nontree edge)집합

       - 신장트리에 사용되지 않은 간선들의 집합

 

 

 

    d. 최소 연결 부분 그래프(minimal connected subgraph): G 부분 그래프G'  중 조건만족 그래프

        - 조건: V(G') = V(G),  E(G') ⊆ E(G),  G'는 연결그래프, G'는 최소 간선 수를 포함

        - 신장트리는 최소연결 부분 그래프, n-1개의 간선 가짐