[알고리즘] 그래프 GRAPH

0. 정의

• 그래프(G)는 정점(Vertex)와 간선(Edge)로 이루어집니다.   * G = (V, E)
• 인접(Adjacent) : 간선(Edge)으로 연결된 두 정접(Vertex)
• 완전그래프(Complete Graph) : 간선(Edge)의 개수가 최대인 그래프
• 경로(Path) : 경로의 길이는 경로사이의 간선(Edge)의 수
• Directed Graph : 방향성이 있는 간선(Edge)을 갖는 그래프
• Undirected Graph : 방향성이 없는 간선(Edge)을 갖는 그래프

 

그래프는 아래와 같이 표현합니다.

그래프 예제

 

표를 이용한 그래프 표현

 

 

1. Graph Traversal

그래프의 탐색방법은 크게 두가지로 나눠집니다.

 

• Depth First Search(DFS) : 깊이 우선 탐색
• Breadth First Search(BFS) : 너비 우선 탐색

두 개념은 그래프와 트리와 같이 Vertex와 Edge로 이루어진 자료구조에서 사용되는 탐색방법입니다.

 

두개의 차이는 아래를 참고하면 쉽게 이해할 수 있습니다.

 

출처 : http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

 

DFS는 순환호출 형태로 많이 구현하며 BFS는 Quere를 이용하여 쉽게 구현할 수 있습니다.

 

void DFS(Vertex* V)
{
	Edge* E = NULL;
    printf("%d ", V->Data);
    
    V->Visited = Visited;
    
    E = V->AdjacencyList;
    
    while(E != NULL){
    	if( E->Target != NULL && E->Target->Visited == NotVisited )
        	DFS( E-> Target );
        
        E = E->Nest;
    }
}
       

전체 알고리즘자료는 깃헙에 올리고있습니다. => https://github.com/yekyu94

yekyu94 - Overview