그래프 순회(Graph Traversal)

📢  그래프순회

• 순회(Traversal) : 모든 정점과 간선을 검사함으로써 그래프를 탐험하는 체계적인 절차
• 주요전략
  
  👉 깊이우선탐색(DFS, Depth First Search)
  👉 너비우선탐색(BFS, Breadth First Search)
  
  

📢  깊이우선탐색(DFS)

• 깊이우선탐색(DFS, Depth First Search) : 그래프를 순회하기 위한 일반적 기법 중 하나.
• 그래프 G에 대한 DFS순회로 가능한 것들
  
  👉 G의 모든 정점과 간선을 방문
  👉 G가 연결그래프인지 결정
  👉 G의 연결요소들을 계산
  👉 G의 신장숲을 계산
  
  
• N개의 정점과 M개의 간선을 가진 그래프에 대한 DFS는 O(N + M)시간 소요
• DFS를 확장하면 해결 가능한 그래프 문제들
  
  👉 두 개의 주어진 정점 사이의 경로를 찾아 보기
  👉 그래프 내 싸이클 찾기
  
  
• 그래프에 대한 DFS는 이진트리에 대한 선위순회와 유사하다. ( 선위순회는 재귀, 즉 스택(Stack)을 활용한다. )
  ( 자료구조 스택을 모른다면, 아래 포스팅을 보고오길 바란다. )

스택(Stack) 자료구조

Alg DFS(G)
	input graph G
    output labeling of the edges of G 
    as tree edges and back edges

for each u ∈ G.vertexs()
	l(u) <- Fresh
for each e ∈ G.edges()
	l(e) <- Fresh
for each v ∈ G.vertexs()
	if(l(v) == Fresh)
    	rDFS(G,v)		// 재귀적 DFS 호출

=======================================================

Alg rDFS(G,V)		// 재귀적 DFS
	input graph G and a start vertex v of G
    output labeling of the edges of G in the connected 
    component of v as tree edges and back edges
    
l(v) <- Visited		// 방문한 노드 체크

for each e ∈ G.incidentEdges(v)		// 정점 v에 부착된 간선에 대해
	if(l(e) == Fresh)			// 간선 e가 아직 안지나간 간선이면
    	w <- G.opposite(v,e)			// 정점 v와 간선 e를 통한 반대편 정점 w
        if(l(w) == Fresh)			// w가 아직 미방문 정점이면			
        	l(e) <- Tree			// 일단, 간선 e는 Fresh -> Tree 간선으로 변경
            rDFS(G,w)				// rDFS 재귀호출
        else						// 간선 e가 Fresh한 간선이 아니다 ?
        	l(e) <- Back			// 그럼, 간선 e는 Fresh -> Back 간선으로 변경

 

• DFS 수행 예시

DFS 처리 예시

• DFS 속성
  
  👉 속성 1. rDFS(G,v)는 v의 연결요소내의 모든 정점과 간선을 방문한다.
  👉 속성 2. rDFS(G,V)에 의해 라벨된 트리 간선들은 v의 연결요소의 신장트리(DFS tree)를 형성한다.
• DFS 분석
  
  👉 정점과 간선의 라벨을 쓰고 읽는데 O(1)시간 소요
  👉 각 정점은 두 번 라벨 ( 한 번은 Fresh, 또 한번은 Visited )
  👉 각 간선은 두 번 라벨 ( 한 번은 Fresh, 또 한번은 Tree 또는 Back 으로 )
  👉 incidentEdges( ) ( 한 정점에 붙어있는 부착간선 메소드 )는 각 정점에 대해 한 번 호출
  👉 그래프가 인접리스트 구조로 표현된 경우, DFS는 O(N + M)시간에 수행 ( 어떤 그래프 G의 deg(v) 합 = 2M )
  
  
• DFS 템플릿 활용
  
  👉 연결성 검사, 경로 찾기, 싸이클 찾기 등의 문제들을 DFS를 확장해서 해결할 수 있다.

📢  비재귀적 DFS

• rDFS ( 재귀 DFS )는 이름 그대로, 재귀호출을 통해서 그래프 순회를 한다.
• 비재귀적 DFS는 재귀호출이 아닌, 스택(Stack)을 사용해서 DFS를 실행한다.

Alg DFS(G,v)
	input graph G and a start vertex v of G
    output labeling of the edges of G 
    in the connected component of v
    as tree edges and back edges

S <= empty stack
S.push(v)		// 매개변수 v정점 스택에 push

while(!(S.isEmpty())	// 스택을 비울동안
	v <= S.pop()		// 스택 pop()
	l(v) <- Visited		// pop()한 정점는,이제 Visited
    for each e ∈ G.incidentEdges(v)	// pop()한 정점에 부착된 모든 간선에 대해
		if(l(e) == Fresh)			// 그 간선이 아직 방문안한 간선이면
        	w <- G.opposite(v,e)	// pop()한 정점 v와 연결된 간선 e의 반대편 정점이 w
            if(l(w) == Fresh)		// 그 정점 w가 아직 방문안한 정점이면 ?
            	l(e) <- Tree		// 건너언 간선 e는 일단 Fresh -> Tree 간선으로 변경
                S.push(w)			// 그리고, w정점을 스택에 push
            else					// 정점 w가 이미 방문한 정점이면
            	l(e) <- Back		// 건너온 간선 e는 Fresh -> Back 간선으로 변경 ( 싸이클 제어 )
return

• 실제 구현 ( By. C )

// DFS 비재귀버젼

#include <stdio.h>
#include <stdlib.h>

typedef struct incidentedge
{
	int key;
	char state[6];
	struct incidentedge* next;
	struct incidentedge* prev;
}IncidentEdge;
typedef struct vertex
{
	int key;
	char state[6];
	IncidentEdge* head;
}Vertex;
typedef struct stack						// 비재귀 DFS를 위한 stack ( 정점의 키값을 저장할것이다. )
{
	int* list;
	int top;
}Stack;

void nrDFS(Vertex* V, int S, int n);		// 비재귀 DFS
void makeVertex(Vertex* V, int n);
void linkEdge(Vertex* V, int start, int end);
void initStack(Stack* S, int n);			// 스택 초기화
void push(Stack* S, int n);					// 스택 push
int pop(Stack* S);							// 스택 pop
int isStackEmpty(Stack* S);					// 스택 비었는가 ?
void freeVertexIncidentList(Vertex* V, int n);

int main()									
{
	int N, M, S, start, end;
	Vertex* v = NULL;
	scanf("%d %d %d", &N, &M, &S);

	v = (Vertex*)malloc(sizeof(Vertex) * N);

	makeVertex(v, N);

	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &start, &end);
		linkEdge(v, start, end);
		linkEdge(v, end, start);
	}
	nrDFS(v,S,N);							// 비재귀 DFS 호출만 다른 부분
	
	freeVertexIncidentList(v, N);			// 각 정점에 달린, 인접 리스트 동적할당 해제
	for (int i = 0; i < N; i++)
		free(v[i].head);					// 각 정점에 달린, 인접헤드 동적할당 해제
	free(v);								// 정점배열 동적할당 해제
	return 0;
}
void nrDFS(Vertex* V,int s,int n)			// 비재귀적 DFS
{
	IncidentEdge* p = NULL;					// 인접리스트 조사할 p
	Stack* stack = NULL;					// 스택 포인터					
	
	stack = (Stack*)malloc(sizeof(Stack));	// 스택 동적할당
	initStack(stack,n);						// 스택 초기화
	
	push(stack, V[s - 1].key);				// 파라미터로 넘어온 s, 정점 s부터 시작, 스택에 push
	strcpy(V[s - 1].state, "visit");		// 정점 s 는 이제 visit
	printf("%d\n", V[s-1].key);				// 방문의미하는 출력
	
	while (!isStackEmpty(stack))			// 이제부터 스택이 비울 때까지 반복할 것임
	{
		// 매 차례마다
		p = V[stack->list[stack->top]-1].head->next;	// 스택에 가장 최근에 들어온, 정점위치의, 인접노드 시작을 p에 대입해서	
		while (p != NULL && strcmp(V[p->key - 1].state, "visit") == 0)	// 인접해 있는데, 아직 방문안한, 정점 찾음
			p = p->next;
		if (p != NULL && strcmp(V[p->key-1].state,"fresh") == 0)	// 아직 방문안한, 인접한 정점이 있으면
		{
			push(stack, V[p->key - 1].key);				// 그 정점, 스택에 push
			strcpy(V[p->key - 1].state, "visit");		// 그 정점은 이제, visit
			printf("%d\n", V[p->key - 1].key);			// 그 정점으로, 방문했음을 의미,출력
		}
		if (p == NULL)		// 윗 while문을 통해서, 현재 stack에 peek한 정점의, 인접 정점을 다 방문했으면
			pop(stack);		// 그 정점은, 이제 들어갈 만큼 들어간 것이니, pop
	}
	free(stack->list);	// 스택 리스트 동적할당 해제
	free(stack);	// 스택 동적할당 해제
}
void makeVertex(Vertex* V, int n)
{
	for (int i = 0; i < n; i++)
	{
		V[i].key = i + 1;
		strcpy(V[i].state, "fresh");
		V[i].head = (IncidentEdge*)malloc(sizeof(IncidentEdge));
		if (V[i].head != NULL)
		{
			V[i].head->next = NULL;
			V[i].head->key = 0;
		}
	}
}
void linkEdge(Vertex* V, int start, int end)
{
	IncidentEdge* p, * newNode;
	
	newNode = (IncidentEdge*)malloc(sizeof(IncidentEdge));
	if (newNode != NULL)
	{
		newNode->key = end;
		newNode->prev = NULL;
		newNode->next = NULL;
		strcpy(newNode->state, "fresh");
	}
	p = V[start - 1].head;
	while (p->next != NULL && end > p->next->key)
		p = p->next;
	if (p->next == NULL)
	{
		p->next = newNode;
		newNode->prev = p;
	}
	else
	{
		newNode->next = p->next;
		p->next->prev = newNode;
		newNode->prev = p;
		p->next = newNode;
	}
}
void initStack(Stack* S, int n)
{
	S->list = (int*)malloc(sizeof(int) * n);
	S->top = -1;
}
void push(Stack* S, int n)
{
	S->top += 1;
	S->list[S->top] = n;
}
int pop(Stack* S)
{
	int returnData = S->list[S->top];
	S->top -= 1;
	return returnData;
}
int isStackEmpty(Stack* S)
{
	return S->top == -1;
}
void freeVertexIncidentList(Vertex* V, int n)
{
	IncidentEdge* p = NULL;

	for (int i = 0; i < n; i++)
	{
		while (V[i].head->next != NULL)
		{
			p = V[i].head->next;
			while (p->next != NULL) p = p->next;
			p->prev->next = NULL;
			free(p);
		}
	}
}

 

📢  너비우선탐색(BFS)

• 너비우선탐색(BFS, Breadth First Search) : 그래프를 순회하기 위한 일반적 기법 중 하나.
• 그래프 G에 대한 BFS순회로 가능한 것들
  
  👉 G의 모든 정점과 간선을 방문
  👉 G가 연결그래프인지 결정
  👉 G의 연결요소들을 계산
  👉 G의 신장숲을 계산
  
  
• N개의 정점과 M개의 간선을 가진 그래프에 대한 BFS는 O(N + M)시간 소요
• BFS를 확장하면 해결 가능한 그래프 문제들
  
  👉 두 개의 주어진 정점 사이의 최소 간선을 사용하는 경로를 찾아보기
  👉 그래프 내 단순싸이클 찾기
  
  
• 그래프에 대한 BFS는 이진트리에 대한 레벨순회와 유사하다. ( 레벨순회는 큐(Queue)를 활용했었다. )
  ( 자료구조의 레벨순회를 모른다면, 아래 포스팅을 확인하고 오길 바란다. )

[자료구조] 트리 - 레벨 순회

Alg BFS(G)
	input graph G
    output labeling of the edges of G
	as tree edges and cross edges

for each u ∈ G.vertexs()
	l(u) <- Fresh
for each e ∈ G.edges()
	l(e) <- Fresh
for each v ∈ G.vertexs()
	if(l(v) == Fresh)
		BFS1(G,v)

=======================================

Alg BFS1(G,v)
	input graph G and a start vertex v of G
	output labeling of the edges of G
	in the connected component of v as tree
    edges and cross edges
    
L(0) <- empty list		// 레벨순회 큐(queue)
L(0).addLast(v)			// 큐에 매개변수로 넘어온, 정점 v 를 enqueue
l(v) <- Visited			// 정점을 큐에 enqueue 했다는 것은, 방문했다는 의미. 고로 정점 v를 Fresh -> Visited
i <- 0					// 큐 인덱싱할 i

while(!(L(i).isEmpty())		// 큐를 비울때까지
	L(i+1) <- empty list
    for each v ∈ L(i).elements()	// 큐에 있는 정점 하나를 dequeue를 하고
    	for each e ∈ G.incidentEdges(v)	// 그 정점과 연결된 모든 간선에 대해
        	if(l(e) == Fresh)		// 아직 방문안해본 간선이면 가서
        		w <- G.opposite(v,e)	// 그 정점 v와 간선 e를 통한 반대편 정점을 w라 하고
            	if(l(w) == Fresh)		// 그 정점 w가 아직 방문안한 정점이면
            		l(e) <- Tree		// 간선 e는 Fresh -> Tree 간선으로
                	l(w) <- Visited)	// 정점 w는 Fresh -> Visited 정점으로 변경하고
                	L(i+1).addLast(w)	// 정점 w를 큐에 enqueue
				else					// 정점 w가 이미 방문한 정점이라면
            		l(e) <- Cross		// 간선 e는 Fresh -> Cross 간선으로
	i <- i + 1

 

• BFS 수행 예시

BFS 수행 예시

 

• BFS 속성
  
  👉 G(v) : v의 연결요소라 했을 때
  👉 속성 1. BFS1(G,v)는 G(v)의 모든 정점과 간선을 방문한다.
  👉 속성 2. BFS1(G,v)에 의해 라벨된 트리 간선들은 G(v)의 신장트리(BFS tree)라 불린다. ( T(v) )
  👉 속성 3. L(i)내의 각 정점 w에 대해
  
  1. T(v)의 v에서 w로 향하는 경로는 i개의 간선을 가진다.
  2. G(v)내의 v에서 w로 향하는 모든 경로는 최소 i개 간선을 가진다.
  
  
• BFS 분석
  
  👉 정점과 간선의 라벨을 쓰고 읽는데 O(1) 시간소요
  👉 각 정점은 두 번 라벨 ( 한 번은 Fresh로 , 또 한 번은 Visited 로 )
  👉 각 간선은 두 번 라벨 ( 한 번은 Fresh로 , 또 한 번은 Tree 또는 Cross 로 )
  👉 각 정점은 리스트 L(i)에 한 번 삽입 ( 여기서 리스트는 큐(queue)를 의미 )
  👉 incidentEdges( ) ( 부착간선 메소드 )는 각 정점에 대해 한 번 호출
  👉 그래프 G가 인접리스트 구조로 표현된 경우, BFS는 O(N + M)시간에 수행
  
  
• BFS 템플릿 활용
  
  👉 G의 연결요소들을 계산하기
  👉 G의 신장숲을 계산하기
  👉 G내의 단순 싸이클 찾기 또는 G가 숲임을 보고하기
  👉 G의 주어진 두 정점에 대해, 그 사이의 최소 간선로 이루어진 G 내의 경로 찾기, 또는 그런 경로 없음을 찾기
  ( 즉, 최단 경로(Directed Path) 문제 활용 가능 )