• 그래프(Graph)
  • 깊이 우선 탐색(Depth-First Search)
  • 너비 우선 탐색(Breadth-First Search)


Chapter 3. Graph-theoretic Models 강의를 듣고 정리한 내용입니다.


그래프(Graph)

  • 그래프는 꼭짓점 혹은 노드로 이루어지고, 이들은 간선 혹은 변으로 이루어짐
  • 노드의 집합(꼭짓점)
    • 각 노드는 다른 노드와 관계된 정보를 담고 있음
    • ex) 학생의 성적, 그래프는 한 반의 성적을 모아놓은 것이라고 할 수 있음
  • 간선, 변이
    • 노드의 쌍을 연결
    • 간선을 이용해 그래프를 만드는 2가지 방법
      • 무방향
      • 유향(방향 그래프의 일종이 트리)
  • 사용 예시
    • 개체 사이의 관계 표시
      • 예) 파리에서 런던으로 여행을 갈 때 노드는 각 도시, 연결은 도시사이 레일
    • 약의 발견
      • 각각의 관계를 파악하면서 복잡한 분자를 모델링
  • 유용한 이유
    • 세상에 존재하는 여러관계는 그래프로 표현하기 적합
    • 컴퓨터 네트워크, 교통 네트워크, 금융 네트워크, 정치네트워크, 범죄 네트워크, 사회 네트워크 등
    • 관심이 있는것의 관계를 찾을 수 있음
  • 그래프를 만드는 방법
    • 두 요소 사이에 연속된 간선이 있는지 확인
    • 최소비용 혹은 최단 경로를 찾을 수 있는지 확인
    • 그래프 분할 문제로 접근(그래프에서 연결된 요소만 분리)


-- python 객체 클래스 상속받음
class Node(object):
		def __init__(self, name):
				self.name = name

		def getName(self):
				return self.name

		def __str__(self):
				return self.name



class Edge(object):
		def __init__(self, src, dest):
				self.src = src
				self.dest = dest
		
		def getSource(self):
				return self.src

		def getDestination(self):
				return self.dest

		def __str__(self):
				return self.src.getName() + '->'\
							+ self.dest.getName()


  • 중요한 가정: 인자로 받는 시작점과 도착점은 노드여야한다(실제 인스턴스)
  • 간선안에서 노드를 가르키는 포인트를 얻고 노드에서 해당하는 함수에 접근하고 출력


인접 행렬 : 행은 시작점, 열은 도착점

  • 유향 그래프에선 행렬은 대칭행렬이 아님


인접 리스트 : 노드별로 목적지 리스트로 만들어줌


class Digraph(object):
			def __init__(self):
					self.edges = {} #노드 키를 딕셔너라에 저장

			def addNode(self.node): # 노드를 추가할때 딕셔너리가 있는지 확인
					if node in self.edges:
							raise ValueError('Duplicate node')
					else:
							self.edges[node] = [] #키가 노드 자체

			def addEdge(self, edge):
					src = edge.getSource()
					dest = edge.getDestination()
					if not (src is self.edges and dest in self.edges):
							raise ValueError('node is not grape')
					self.edges[src].append(dest)

			def childrenOf(self, node):
					return self.edges[node]

			def hasNode(self, node):
					return node in self.edges

			def getNode(sel, name):
					for n in self.edges:
							if n.getName() == name:
									return n
					raise NameError(name)

			def __str__(self):
					result = ''
					for src in self.edges:
							for dest in self.edges[src]:
									result = result + src.getName() + '->'\
													+ dest.getName() + '\n'
					return result[:-1]


  • 노드는 딕셔너리의 키, 간선은 키와 목적노드 리스트로 표현된다.
  • 특정 시작점과 도착점 사이 간선이 있는지 알고 싶을 때 딕셔너리에서 도착점이 리스트에 있는지 확인하면 된다.
  • 특정노드의 자식이 알고싶으면 딕셔너리에 가서 해당 노드와 연관된 리스트를 보면 된다.


class Graph(Digraph):
		def addEdge(self, edge):
				Digraph.addEdge(self, edge)
				rev = Edge(edge.getDsetination(), edge.getSource())
				Digraph.addEdge(self, rev)


  • 시작점에서 도착점으로 가는 간선 추가, 다른 방향의 간선도 만들어준다.
  • 이점) 간선의 방향성이 없어 양방향으로 갈 수 있다.
  • 명시적으로 호출하여 서브클래스로부터 상속받는다.


그래프 탐색

  • 한 노드에서 다른 노드로 가는 최단 경로를 구하는 방법은?
  • 최단경로 : 시작점의 첫 간선 ~ 도착점의 마지막 간선
    • 각 간선에는 가중치가 있음 → 단순히 거리를 가중치로 둘 수 있음
    • 일종의 사슬처럼 보임
  • 알고싶은 것 : 최소 단계 수(시작점-도착점 사이의 간선들)


1) 깊이 우선 탐색(Depth-First Search)

  • 루트 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 모두 탐색하는 방법
    • 막힐때까지 다음 간선을 따라 감(막히면 돌아옴)
    • 쉽게 수정 가능
  • 루프의 가능성이 있기 떄문에 경로를 기억해야함
  • 이미 들렀던 노드는 가지않음
    • 첫 간선을 따라가다 올바르게 왔는지 확인, 올바르지않으면 루프
    • 목표 노드에 도착하거나 선택지가 없어질 때까지 반복
  • 특징
    • 자기 자신을 호출하는 순환 알고리즘
    • 어떤 노드를 방문했는지 반드시 확인


def DFS(graph, start, end, path, shortest, toPrint=False):
		path = path[start]
		if toPrint:
			print('Current DFS path', printPath(path))
			return path
		for node in graph.childrenOf(start):
				if node not in path:
					if shortest == None or len(path) < len(shortest):
						newPath = DFS(graph, node, end, path, shortest, toPrint)
							if newPath != None:
								shorest = newPath
							elif toPrint:
								print('Already visited', node)
						return shortest

def shortestPath(graph, start, end, toPrint = False): 
		return DFS(graph, start, end, [], None, toPrint)


2) 너비 우선 탐색(Breadth-First Search)

  • 루트 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법
    • 길이가 같은 경로를 탐색
    • 큐를 계속 돌면서 남은 경로를 탐색
    • 쉽게 수정 불가
      • 최소 가중 경로가 최소 개수 경로가 아닐 수 있어서 고려해서 수정해야함
  • 특정한 순서로 시작점에서 나가는 모든 변을 고려
  • 도착점을 찾거나, 선택지가 없어질 때까지 반복
    • 변의 선택지가 없어지면, 시작점에서의 거리가 같은 다음 꼭짓점으로 가서 과정을 반복
    • 꼭짓점의 선택지가 없어지면, 그래프의 다음 레벨로 가서 반복
  • 특징
    • 루트 노드에서 목표노드까지의 최단 거리를 보장


def BFS(graph, start, end, toPrint=False):
		initPath = [start]
		pathQueue = [initpath]
		while len(pathQueue) != 0:
			pathQueue.pop(0)
			if toPrint:
					print('Current BFS path', printPath(tmpPath))
			lastNode = tmpPath[-1]

			if lastNode == end:
					return tmpPath
			for nextNode in graph.childrenOf(lastNode):
				if nextNode not in tmpPath:
					newPath = tmpPath + [nextNode]
					pathQueue.append(newPath)
			return None
  • n 루프 이상의 경로를 탐색하기 전에 n 루프의 모든 경로를 탐색


다음강의 : Chapter 4. Stochastic Thinking