[알고리즘2] Undirected and Directed Graphs

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶Contents

• Undirected Graph
• Directed Graph
• Web Crawling
• Topological Sort
• Strongly-Connected Component

 

▶Undirected Graph

간선에 방향성이 없는 그래프이다.

특정 조건을 만족하는 (모든 간선이 양방향) Digraph의 집합이다.

따라서 Digraph의 부분 집합이다.

 

Undirected Graph 알고리즘

조건에 맞는 일부 경우에만 동작하는 알고리즘이므로 상대적으로 간단하다.

ex. connected components 구하는데 DFS를 그대로 사용한다.

class Graph:
	def __init__(self, V):
		self.V = V
		self.E = 0
		self.adj = [[] for _ in range(V)] 

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)
		self.E += 1

	def degree(self, v):
		return len(self.adj[v])

v, w 사이에 양방향 간선이 있기 때문에, 각각을 추가해줘야 한다.

 

 

▶Directed Graph

간선에 방향성이 있는 그래프이다. (Digraph라고도 한다.)

Undirected/directed 모두 포함하므로, 더 일반적이고 포괄적인 집합이다.

 

Digraph 알고리즘

더 다양한 경우에 대해 모두 동작해야 하므로 상대적으로 더 복잡하다.

ex. connected components를 구하는데 Kosaraju-Sharir 알고리즘을 사용한다.

class Digraph:
	def __init__(self, V):
		self.V = V
		self.E = 0
		self.adj = [[] for _ in range(V)] 

	def addEdge(self, v, w):
		self.adj[v].append(w) 
		self.E += 1

	def outDegree(self, v):
		return len(self.adj[v])

v -> w 방향의 간선이 있기 때문에, 한쪽으로만 append 해주면 된다.

 

Strong-connected component를 찾을 때 reverse가 필요하기 때문에 class Digraph안에 추가해준다.

def reverse(self):
	g = Digraph(self.V)
	for v in range(self.V):
		for w in self.adj[v]:
			g.addEdge(w, v)
	return g

G에 v -> w가 있으면 G^R에는 w -> v를 더해준다.

 

[Reverse Graph의 활용 예]

그래프 G와 출발 정점 s를 입력으로 받아 s로부터 다른 모든 정점까지의 경로를 찾아주는 프로그램(알고리즘)이 있다.

같은 프로그램을 활용해 임의의 도착지 t까지의 모든 경로를 찾을 수 있을까?

목적지 t로부터 s로 가는 경로를 찾을 때 reverse를 사용한다.

 

Q. V개 정점을 가진 서로 다른 digraph 개수는?

(자기 자신에게 간선 v->v도 가능하나, 두 정점 간에 간선은 최대 1개이며 2개 이상인 경우는 없다고 가정한다.)

     A. 노드 V개가 다른 노드 V개로 갈 수 있으니 V^2이다.

         거기에 Edge가 있을 수도 없을 수도 있으니 2가지의 경우가 나와서

         정답은 2^(V^2)이다.

 

Q. Digraph를 adjacency-list 방식으로 표현했다.

정점 v로부터 나가는 모든 간선을 탐색하려면 시간은 얼마나 걸리나?

    A. v에서 나가는 간선의 수는 outdegree() 함수로 구할 수 있다.

        그렇기 때문에, outdegree(v)에 비례한 시간이 걸린다.

 

Q. adjacency-list 방식에서 정점 v로 들어오는 모든 간선을 탐색하려면 시간은 얼마나 걸리나?

    A. V+E

728x90

▶정점 s로부터 도달 가능한 모든 정점과 경로 찾기

DFS나 BFS를 사용하면 구할 수 있다.

class DFS: 
	def __init__(self, g, s): 
		def recur(v): 
			self.visited[v] = True 
			for w in g.adj[v]:
				if not self.visited[w]: 
				recur(w)
		self.fromVertex[w] = v
		self.g, self.s = g, s
		self.visited = [False for _ in range(g.V)]
		self.fromVertex = [None for _ in range(g.V)]
		recur(s)

DFS는 임의의 경로를 찾을 수 있다.

하지만 최소 간선수에 맞는 경로는 못 찾을 수도 있다.

 

BFS를 사용하면 최소 간선수 경로를 찾을 수 있다.

 

 

(Single source) BFS

한 출발지 s에서 BFS를 진행한다.

s만 queue에 넣고 탐색을 시작한다.

class BFS:
	def __init__(self, g, s): 
		assert(isinstance(g, Digraph) and s>=0 and s<g.V)
		self.g, self.s = g, s
		self.visited = [False for _ in range(g.V)]
		self.fromVertex = [None for _ in range(g.V)]
		self.distance = [None for _ in range(g.V)]
		queue = Queue()
		queue.put(s)
		self.visited[s] = True
		self.distance[s] = 0
		while queue.qsize()>0:
			v = queue.get()
			for w in g.adj[v]:
				if not self.visited[w]:
					queue.put(w)
					self.visited[w] = True
					self.fromVertex[w] = v
					self.distance[w] = self.distance[v] + 1

 

Multi-source BFS

여러 출발지에서 BFS를 진행한다.

이들 모두를 queue에 넣고 탐색을 시작한다.

정접의 집합에서 목적지까지 최단 경로를 찾을 때 필요하다.(Word Net)

같은 시간에 더 다양한 정점과 경로탐색을 할 때 필요하다.(Web Crawling)

class MultiSourceBFS:
	def __init__(self, g, sList): 
		assert(isinstance(g, Digraph) and s>=0 and s<g.V)
		self.g, self.s = g, s
		self.visited = [False for _ in range(g.V)]
		self.fromVertex = [None for _ in range(g.V)]
		self.distance = [None for _ in range(g.V)]
		queue = Queue()
		for s in sList:
			queue.put(s)
			self.visited[s] = True
			self.distance[s] = 0
		while queue.qsize()>0:
			v = queue.get()
			for w in g.adj[v]:
				if not self.visited[w]:
					queue.put(w)
					self.visited[w] = True
					self.fromVertex[w] = v
					self.distance[w] = self.distance[v] + 1

▶Web Crawling : 웹사이트 찾기

출발지 주소 s에서 시작해 링크된 모든 사이트를 탐색하는 것을 반복한다.

 

DFS를 사용 시 내부 주소도 많고, 상호 참조가 많은 도메인에 도달한 경우,새로운 도메인을 찾지 못하고 한 도메인에 오래 빠져 탐색이 정체된다.

 

BFS는 한 branch만 깊이 파지 않고 여러 branch를 돌아가면서 탐색하므로,같은 시간에 더 다양한 도메인을 발견할 수 있다.

 

Multi-Source BFS는 같은 시간에 더 다양한 도메인을 발견할 수 있다.한 source에서 정체되거나 막다른 길에 다다르더라도 다른 source에서 계속 새로운 주소를 탐색할 수 있다.

webaddrPattern = re.compile("https://(?:\\w+\\.)+(?:\\w+)") 33
def webCrawl(roots, maxDepth=1):
	queue = Queue()
	discovered = {}
	for v in roots:
		queue.put(v)
		discovered[v] = 0 
	while queue.qsize()>0:
		v = queue.get() 
		depth = discovered[v]
		if depth > maxDepth: break
		try: 
			resp = requests.get(v) 
			if resp.status_code == 200:
				print(v, f"(depth={depth})")
				for w in webaddrPattern.findall(resp.text):
					if w not in discovered:
						discovered[w] = depth + 1
						queue.put(w)
		except requests.exceptions.ConnectionError as error:
			pass

 

▶Topological Sort(위상 정렬)

간선이 향하는 방향 순으로 정점의 순서를 정하기

Cycle이 없는 digraph에서

Topological order : v -> w 경로가 있다면 v 후에 w가 오도록 하는 순서이다.Topological order 순으로 정점을 나열하는 것을 topological sort라고 한다.

 

같은 그래프에 대해 여러 topological order가 존재할 수 있다.

def topologicalSort(g):
	def recur(v): 
		visited[v] = True 
		for w in g.adj[v]: 
			if not visited[w]: recur(w)
		reverseList.append(v) 

	assert(isinstance(g, Digraph))
	visited = [False for _ in range(g.V)]
	reverseList = []
	for v in range(g.V): 
		if not visited[v]: recur(v)

	reverseList.reverse()
	return reverseList

 

Topological Sort는 DFS를 사용하기 때문에 수행 시간은 V+E에 비례한다.

 

▶Strongly-Connected Component

SCC는 양방향으로 도달 가능한(즉, 갔다가 돌아올 수 있는) 정점의 최대 집합이다.

같은 SCC 내부에는 반드시 cycle이 존재해야 한다. (즉, 양방향 경로가 존재해야 한다.)

서로 다른 SCC 간에는 i) 간선이 없거나 ii) 간선이 한 방향으로만 존재한다.

즉, 서로 다른 SCC 간에는 양방향으로 간선이 존재하지 않는다. (Cycle이 없다.)

 

 

각 SCC를 하나의 정점으로 본 그래프에서 topological order의 역순(reverse)를 찾는 방법

• Topological order는 DFS로 얻는다.
• Topological order의 역순을 얻어야 하므로 reverse graph에 DFS를 적용한다.

 

Kosaraju-Sharir(코사라쥬-샤이르) 알고리즘

• Reverse graph의 (DFS 적용해) topological order를 얻는다.
• 그 순서로 원래 그래프에 DFS (or BFS)를 수행해 SCC를 얻는다.
• reverse : V + E
• topological : V + E (DFS)
• DFS (or BFS) : V + E
• K-S 알고리즘은 V + E에 비례한다.