그래프
Vertex, edge 의 모임
G = (V,E)
인접 관계?
이웃 관계라고도 부른다.
path의 개념
말 그대로 '길' 을 나타내는데, edge로 연결된 각 verte 사이에 '길'
Cycle의 개념
Vertex 들을 edge로 연결하다 보면, 원형으로 path가 되는 경우가 있는데, 이때 Cycle이라고 부른다.
연결성
위와 같은 개념들을 활용해서, edge 간의 인접 관계를 어떻게 나타낼 수 있을까?
방법은 2가지로 나뉜다.
인접행렬
설명 및 특징
그래프를 행렬로 나타낸 것을 말한다.
행렬의 특정 원소를 통해서 vertex 간의 인접 관계를 알 수 있다.
예를 들면, 행렬의 0,1 번째가 '1'이라면 0번째, 1번째 vertex 가 인접함을 알 수 있다.
방향이 존재하는 그래프의 경우에
방향이 존재하지 않는 그래프에 비해서 비어있는 부분이 더 존재 할 수도 있다.
방향이 존재하지 않는 그래프의 경우에
인접 행렬의 형태가 대칭으로 나타난다.
장점
특정 원소에 접근하는데 걸리는 시간이 상수 시간이다. -> 특정 path가 존재하는지 상수 시간에 알 수 있다. (O(1))
구현이 상대적으로 쉽다.(vertex, edge를 확인 한후 배열로 행렬을 쭉 나타내면 된다.)
단점
Vertex의 개수를 n 이라고 할때,
인접 행렬을 만드는데 O(n^2) 만큼의 시간이 걸린다.
각 Vertex에 연결된 모든 노드를 방문해 보고 싶은 경우(특정 노드에 연결된 노드들이 몇번 노드인지 확인할 경우)는 Vertex 개수 만큼 확인해야되기 떄문에 O(n) 만큼 걸린다. -> Vertex 개수에 비해서 Edge의 개수가 적으면 적을 수록 더 손해이다.
방향이 존재할 경우, 쓸데없이 공간을 낭비한다. - 비어있는 부분이 발생하기 때문에
인접 리스트
설명 및 특징
인접행렬의 각 행을 하나의 연결 리스트로 나타낸다.
Vertex의 개수에 비해 edge수가 적을 때 사용하면 좋다.
모든 vertex에 대해서 존재하는 edge만 탐색
O(V+E)의 공간을 사용
장점
인접행렬에 비해서 공간 효율이 높다.
각 노드에 연결된 노드를 방문해보기 위해서, 전체 edge 개수만큼만 확인해서 알 수 있다.
단점
특정 vertex 끼리 연결되어있는지 확인 할 때, 인접행렬은 O(1)으로 확인할 수 있었지만, 인접리스트의 경우는 O(V) 인데.. 이부분은 잘 이해가 안됨.. => 추후 확인후 수정 필요
class Vertex:
def __init__(self, key):
'''
Vertex의 id 값을 인자로 전달받는 key로 초기화 한다.
연결관게를 나타내는 connectedTo dict를 초기화 한다.
'''
self.id = key
self.connectedTo = {}
def addNeighbor(self, nbr, weight=0):
'''
인접노드를 추가한다.
노드의 연결관계 dict의 key 값을 인자로 받는 nbr로 넣어주고 그 value를 weight로 넣는데,
인자로 받는 weight가 없을 시에는 0으로 들어간다.
'''
self.connectedTo[nbr] = weight
def __str__(self):
'''
Vertex instance를 출력 했을 때, 아래 와 같은 형태로 return 한다.
'''
return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])
def getConnections(self):
'''해당 노드의 인접한 노드들의 리스트를 리턴한다.'''
return self.connectedTo.keys()
def getId(self):
''' 해당 노드의 id 값을 리턴한다.'''
return self.id
def getWeight(self, nbr):
'''해당 노드와 연결된 노드의 weight 값을 리턴한다.'''
return self.connectedTo[nbr]class Graph:
def __init__(self):
'''Vertex 리스트와 노드의 번호를 초기화 한다.'''
self.vertList = {}
self.numVertices = 0
def addVertex(self, key):
'''
그래프의 Vertex 넘버를 1 증가 시키고(개수가 하나 증가했으니까)
인자로 받은 key를 Vertex 인스턴스로 넘기면서 새로운 vertex를 생성한다.
verList dict에 인자로 전달받은 key를 key 값으로 가지고 value를 newVertex 값을 가지는 것을 생성하고
새로 추가된 Vertex를 추가한다.
'''
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertList[key] = newVertex
return newVertex
def getVertex(self, n):
'''
그래프의 vertexList 안에 인자로 받은 n이 존재하면,
vertexList의 key 'n'에 해당하는 value 값인 vertex 객체를 리턴하고
아니면 None을 리터한다.
'''
if n in self.vertList:
return self.vertList[n]
else:
return None
def __contains__(self, n):
'''
그래프의 vertexList n이 있으면, true, 없으면 false를 리터한다.
'''
return n in self.vertList
def addEdge(self, f,t, cost=0):
'''
그래프의 vertexList에서
인자로 받은 f 와 t 가 속해있지 않다면,
그래프의 각각 f, t를 key를 가지는 vertex를 생성한 후,
addNeighbor를 이용해서 f, ㅅ를 잇는 edge를 추가한다.
'''
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost)
def getVertices(self):
'''
그래프의 vertexList의 key 리스트를 리턴한다.
'''
return self.vertList.keys()
def __iter__(self):
'''
그래프의 vertexList의 value 값의 리스트를 리턴한다.
'''
return iter(self.vertList.values())
g = Graph()
# Graph 인스턴스 인 g를 생성하고 Vertex를 생성한다.
for i in range(6):
g.addVertex(i)g.vertList{0: <__main__.Vertex at 0x10b44ea58>,
1: <__main__.Vertex at 0x10b44ec18>,
2: <__main__.Vertex at 0x10b44e390>,
3: <__main__.Vertex at 0x10b44edd8>,
4: <__main__.Vertex at 0x10b4edac8>,
5: <__main__.Vertex at 0x10b4edf98>}
g.addEdge(0,1,5)
g.addEdge(0,5,2)
g.addEdge(1,2,4)
g.addEdge(2,3,9)
g.addEdge(3,4,7)
g.addEdge(3,5,3)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)for v in g:
for w in v.getConnections():
print("( {} , {} )".format(v.getId(), w.getId()))( 0 , 1 )
( 0 , 5 )
( 1 , 2 )
( 2 , 3 )
( 3 , 4 )
( 3 , 5 )
( 4 , 0 )
( 5 , 4 )
( 5 , 2 )
그래프 구현 연습 템플릿
class Vertex:
def __init__(self, key):
'''
Vertex의 id 값을 인자로 전달받는 key로 초기화 한다.
연결관게를 나타내는 connectedTo dict를 초기화 한다.
'''
def addNeighbor(self, nbr, weight=0):
'''
인접노드를 추가한다.
노드의 연결관계 dict의 key 값을 인자로 받는 nbr로 넣어주고 그 value를 weight로 넣는데,
인자로 받는 weight가 없을 시에는 0으로 들어간다.
'''
def __str__(self):
'''
Vertex instance를 출력 했을 때, 아래 와 같은 형태로 return 한다.
'''
def getConnections(self):
'''해당 노드의 인접한 노드들의 리스트를 리턴한다.'''
def getId(self):
''' 해당 노드의 id 값을 리턴한다.'''
def getWeight(self, nbr):
'''해당 노드와 연결된 노드의 weight 값을 리턴한다.'''
class Graph:
def __init__(self):
'''Vertex 리스트와 노드의 번호를 초기화 한다.'''
def addVertex(self, key):
'''
그래프의 Vertex 넘버를 1 증가 시키고(개수가 하나 증가했으니까)
인자로 받은 key를 Vertex 인스턴스로 넘기면서 새로운 vertex를 생성한다.
verList dict에 인자로 전달받은 key를 key 값으로 가지고 value를 newVertex 값을 가지는 것을 생성하고
새로 추가된 Vertex를 추가한다.
'''
def getVertex(self, n):
'''
그래프의 vertexList 안에 인자로 받은 n이 존재하면,
vertexList의 key 'n'에 해당하는 value 값인 vertex 객체를 리턴하고
아니면 None을 리터한다.
'''
def __contains__(self, n):
'''
그래프의 vertexList n이 있으면, true, 없으면 false를 리터한다.
'''
def addEdge(self, f,t, cost=0):
'''
그래프의 vertexList에서
인자로 받은 f 와 t 가 속해있지 않다면,
그래프의 각각 f, t를 key를 가지는 vertex를 생성한 후,
addNeighbor를 이용해서 f, ㅅ를 잇는 edge를 추가한다.
'''
def getVertices(self):
'''
그래프의 vertexList의 key 리스트를 리턴한다.
'''
def __iter__(self):
'''
그래프의 vertexList의 value 값의 리스트를 리턴한다.
'''
관련 키워드
관련 문제 풀이
'Legacy(~18.10) > 컴퓨터공학' 카테고리의 다른 글
| [Data Structure] Hashing - 이론 (0) | 2018.09.10 |
|---|---|
| [Data Structure] Deque - 이론 && ADT (0) | 2018.09.10 |
| [Data Structure] Queue - 이론 && ADT (0) | 2018.09.10 |
| [Data Structure] Stack - 이론 && ADT (0) | 2018.09.10 |
| [자료구조 && 알고리즘] 버블정렬 (0) | 2018.07.15 |