그래프 순회

그래프 순회

• 순회(traversal): 모든 정점과 간선을 검사함으로써 그래프를 탐험하는 체계적인 절차
• 예시
  • 수도권 전철망의 모든 역(정점)의 위치를 출력
  • 항공사의 모든 항공편(간선)에 대한 노선 정보를 수집
  • 웹 검색엔진의 데이터 수집 부문은 웹의 하이퍼텍스트 문서(정점)와 문서 내 링크(간선)를 검사함으로써 써핑
• 주요 전략
  
  • 깊이 우선 탐색
  • 너비 우선 탐색

 

깊이 우선 탐색

• 깊이우선탐색(depth-first search, DFS): 그래프를 순회하기 위한 일반적 기법
• 그래프 G에 대한 DFS 순회로 가능한 것들
  
  • G의 모든 정점과 간선을 방문
  • G가 연결그래프인지 결정
  • G의 연결요소들을 계산
  • G의 신장숲을 계산
• n개의 정점과 m개의 간선을 가진 그래프에 대한 DFS는 O(n + m) 시간 소요
• DFS를 확장하면 해결 가능한 그래프 문제들
  
  • 두 개의 주어진 정점 사이의 경로를 찾아 보고하기
  • 그래프 내 싸이클 찾기
• 그래프에 대한 깊이우선탐색은 이진트리에 대한 선위순회와 유사

 

DFS

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

{The algorithm uses a mechanism for setting and getting “labels” of vertices and edges}

1. for each u E G.vertices()
		l(u) <- Fresh
2. for each e E G.edges()
		l(e) <- Fresh
3. for each v E G.vertices()
		if (l(v) = Fresh)
			rDFS(G, v)

Alg rDFS(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

1. l(v) <- Visited
2. for each e E G.incidentEdges(v)
		if (l(e) = Fresh)
			w <- G.opposite(v, e)
			if (l(w) = Fresh)
				l(e) <- Tree
				rDFS(G, w)
			else
				l(e) <- Back

 

DFS와 미로 순회

• DFS 알고리즘은 미로를 탐험하는데 있어서의 고전적이고 모험적인 전략과 유사
• 방문한 교차로, 모퉁이, 막힌 복도(모두 정점)를 표시
• 순회한 복도(모두 간선)를 표시
• 입구(출발정점)로 되돌아가는 경로를 끈(재귀 스택)을 사용하여 추적

 

DFS 속성

• 속성 1
  
  • rDFS(G, v)는 v의 연결요소내의 모든 정점과 간선을 방문
• 속성 2
  
  • rDFS(G, v)에 의해 라벨된 트리 간선들은 v의 연결요소의 신장트리(DFS tree라 불림)를 형성

 

DFS 분석

• 정점과 간선의 라벨을 쓰고 읽는데 O(1) 시간 소요
  
  • 참고: 정점이나 간선을 구현하는 노드 위치의 기능성에 “Visited” 플래그를 포함하도록 확장 가능
• 각 정점은 두 번 라벨
  • 한 번은 Fresh로, 또 한 번은 Visited로
• 각 간선은 두 번 라벨
  
  • 한 번은 Fresh로, 또 한 번은 Tree 또는 Back으로
• 메쏘드 incidentEdges는 각 정점에 대해 한 번 호출
• 그래프가 인접리스트 구조로 표현된 경우, DFS는 O(n + m) 시간에 수행
• 참고: deg(v)의 합 (모든 정점에 부착된 간선의 합)  = 2m

 

너비 우선 탐색

• 너비우선탐색(breadth-first search, BFS): 그래프를 순회하기 위한 일반적 기법
• 그래프 G에 대한 BFS 순회로 가능한 것들
  
  • G의 모든 정점과 간선을 방문
  • G가 연결그래프인지 결정
  • G의 연결요소들을 계산
  • G의 신장숲을 계산
• n개의 정점과 m개의 간선을 가진 그래프에 대한 BFS는 O(n + m) 시간 소요
• BFS를 확장하면 해결 가능한 그래프 문제들
  
  • 두 개의 주어진 정점 사이의 최소 간선을 사용하는 경로를 찾아 보고하기
  • 그래프 내 단순싸이클 찾기
• 그래프에 대한 너비우선탐색은 이진트리에 대한 레벨순회와 유사

 

BFS

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

{The algorithm uses a mechanism for setting and getting “labels” of vertices and edges}

1. for each u E G.vertices()
		l(u) <- Fresh
2. for each e E G.edges()
		l(e) <- Fresh
3. for each v E G.vertices()
		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

1. L0 <- empty list	 	{level container}
2. L0.addLast(v)
3. l(v) <- Visited
4. i <- 0
5. while (!Li.isEmpty())
		Li+1 <- empty list
		for each v E Li.elements()
			for each e R G.incidentEdges(v)
				if (l(e) = Fresh)
					w <- G.opposite(v, e)
					if (l(w) = Fresh)
						l(e) <- Tree
						l(w) <- Visited
						Li+1.addLast(w)
					else
						l(e) <- Cross
		i <- i + 1

 

BFS와 미로 순회

• BFS 알고리즘은 미로를 탐험하는데 있어서의 다소 보수적인 전략과 유사
  
  • 방문한 교차로, 모퉁이, 막힌 복도(모두 정점임)를 표시
  • 순회한 복도(모두 간선임)를 표시
  • 레벨을 하나씩 증가시키면서 진행

 

BFS 속성

• 표기
  
  • Gv: v의 연결요소
• 속성 1
  
  • BFS1(G, v)는 Gv의 모든 정점과 간선을 방문
• 속성 2
  
  • BFS1(G, v)에 의해 라벨된 트리 간선들은 Gv의 신장트리(BFS tree라 불림) Tv를 형성
• 속성 3
  
  • Li 내의 각 정점 w에 대해,
  • Tv의 v에서 w로 향하는 경로는 i개의 간선을 가진다
  • Gv내의 v에서 w로 향하는 모든 경로는 최소 i개의 간선을 가진다

 

BFS 분석

• 정점과 간선의 라벨을 쓰고 읽는데 O(1) 시간 소요
  
  • 참고: 정점이나 간선을 구현하는 노드 위치의 기능성에 “Visited” 플래그를 포함하도록 확장 가능
• 각 정점은 두 번 라벨 O(n)
  
  • 한 번은 Fresh로, 또 한 번은 Visited로
• 각 간선은 두 번 라벨 O(m)
  
  • 한 번은 Fresh로, 또 한 번은 Tree 또는 Cross로
• 각 정점은 리스트 Li에 한 번 삽입 O(n)
• 메쏘드 incidentEdges는 각 정점에 대해 한 번 호출 O(m)
• 그래프가 인접리스트 구조로 표현된 경우, BFS는 O(n + m) 시간에 수행 -> 인접행렬은?
  
  • 참고: deg(v)의 합 (모든 정점에 부착된 간선의 합)  = 2m

 

비트리 간선

• 후향간선 (v, w)
  
  • 트리 간선들의 트리에서 w가 v의 조상
• 교차간선 (v, w)
  • n트리 간선들의 트리에서 w가 v와 동일 또는 다음 레벨에 위치