Python Algorithm 4. 그래프

# 해시테이블 -> 딕셔너리랑 같은 형태를 가진 데이터

# 그래프 용어
# 1) 그래프는 여러 노드(node), 또는 정점(vertex)들이 
# 간선(edge)  또는 아크(arc)로 연결된 추상 네트워크를 뜻합니다.

# G = (V, E)

# 노드 집합 V -> 유한 집합
# 간선 집합 E -> 노드 쌍들의 집합입니다.

# V = {a,b,c,d}
# E = {{a,b},{b,c},{c,d},{d,a}}

# 그래프 방향
# 그래프는 방향이 있는 유향 그래프
# 방향이 없는 무향 그래프

# 무향 그래프는 간선에 방향이 지정되어 있지 않습니다.
# 간선으로 연결된 노드는 서로 인접해 있으며
# 이웃이라고 합니다.

# 유향그래프는 순서가 말단 노드가 존재합니다.
# 노드와 노드 사이의 간선은 a노드에서 b까지의 간선
# b에서 a까지의 간선이 있습니다.

# 완전 그래프
# 모든 노드가 서로 인접한 그래프를 말합니다.

# 노드에 있는 간선의 수 -> 차수
# 차수가 0인 노드는 고립되었다
# 유향그래프 -> 입력차수와 출력차수로 나눌수 있다.
# 입력차수 : 한 노드로 들어오는 간선의 수
# 출력차수 : 한 노드로 나가는 간선의 수

# 경로 : 간선이 어떤 노드도 방문하지 않고
# 일렬로 연결된 부분 그래프
# 보행 : 노드와 간선이 번갈아 가면 반복적으로 방문하는
# 노드와 간선
# 순환 : 경로와 같지만 마지막에 연결된 간선의 노드가 첫번째 노드에 연결

# 경로 길이
# 경로 또는 보행의 길이는 간선의 수와 동일합니다.

# 가중그래프
# 가중 -> 가중치(weight) -> 경로 또는 순환의 가중치는
# 간선들의 가중치의 총합

# 평면그래프
# 간선들이 서로 횡단하지 않고 평면에 그릴수 있는
# 그래프를 뜻합니다.
# 간선에 의한 경계면만 가지게 됩니다.
# 연결된 평면 그래프의 공식
# V - E + F = 2 
# v : 노드 수, E : 간선 수 , F는 면 수

# 순회
# 그래프에 연결된 모든 요소를 탐색을 한다.

# 강한 연결 요소\
# 무향 그래프 -> 모든 노드에서 다른 모든 노드로 넘어갈때
# [경로]가 존재 하면 연결되어 있다.

# 연결 요소 : 모든 노드가 연결된 최대 부분 그래프
# (깊이 우선 탐색)DFS, BFS(너비 우선 탐색) -> 순회 알고리즘을 사용해서 찾아야 한다.

# 강한 연결 요소 : 강하게 연결된 최대 하위 그래프

# 트리와 포레스트
# 트리 -> 비순환적이고 연결되어 있는 유향 그래프
# 포레스트 -> 하나 이상의 트리로 구성되어 있다. 독립적인 트리의 모임

# 트리 : 두 노드는 정확히 하나의 경로로 연결이 됩니다.
# 트리에 새로운 간선이 하나 생기면 순환이 생기고 어떤 간선이 삭제되면
# 연결되이 않은 요소가 생성됩니다.

# 이웃함수
# 모든 이웃의 컨터에너(반복 가능한 객체)
# 인접리스트 : 각 노드에서 이웃리스트(셋, 컨테이너 같은 반복객체)에 접근할 수 있다.

# 셋
a,b,c,d,e,f = range(6)
N = [{b,c,d,f}, {a,d,f}, {a,b,d,e}, {a,e}, {a,b,c},{b,c,d,e}]
# 멤버쉽 테스틑
b in N[a]
b in N[b]
len(N[f])

# 리스트로 인접리스트 만들어보세요.
# 인접리스트
# 그래프가 촘촘한 경우에는 셋을 쓰고 이웃 노드를 반복해서 접근하는 경우에는 리스트를 씁니다.
a,b,c,d,e,f = range(6)
N = [[b,c,d,f], [a,d,f], [a,b,d,e], [a,e], [a,b,c],[b,c,d,e]]
b in N[a]

# 딕셔너리
# 노드가 키가 됩니다.
# 간선의 가중치가 값이 됩니다.
a,b,c,d,e,f =range(6)
N = [{b:2, c:1, d: 4, f : 1}]

# 인접 행렬
# 각 노드의 모든 이웃에 대해 하나의 행을 갖습니다.
# 각 행은 1(True), 0(False)로 이루어집니다.
# 인접행렬은 중첩리스트로 간단하게 구현할 수 이씁니다.
# 행렬의 대각선의 요소는 항상 0입니다.
a,b,c,d,e,f = range(6)

N = [[0,1,1,1,0,1], [1,0,0,1,0,1], [1,1,0,1,1,0],[1,0,0,0,1,0],[1,1,1,0,0,0],[0,1,1,1,1,0]]

N[a][e]

# 무향그래프의 인접행렬은 항상 대칭입니다.
# 인정 행렬에 가중치를 추가하려면 1, 0을 다른 숫자로 바꾸면 됩니다.
# 존재하지 않는  간선은 float('inf'), None, -1등 혹은 매우 큰값으로 바꿉니다.

_ = float('inf')
N = [[_, 2, 1, 4, _, 1], [4, _, _, 1, _, 4], [1, 1, _, 2, 4, _], [3, _, _, _, 2,_],
    [3,4,1,_,_,_], [1,2,_,4,3, _]]
    
# 트리를 한번 만들어봅니다.
# a
#           b
#                      d
#                      e
#           c
#                      h
#                      g

T  = ['a', ['b',['d','f']],['c', ['e','g']]]
print(T)

class SimpleTree(object):
    def __init__(self, value=None, children=None):
        self.value = value
        self.children = children
        if self.children is None:
            self.children = []
    def __repr__(self, level=0):
        ret = "\t" * level + repr(self.value) + "\n"
        for child in self.children:
            ret += child.__repr__(level+1)
        return ret
    
def main():
    st = SimpleTree('a',[
        SimpleTree('b',
                  [
                      SimpleTree('d'),
                      SimpleTree('e')
                  ]),
        SimpleTree('c',[
            SimpleTree('h'),
            SimpleTree('g')
        ])
    ])
    print(st)
    
if __name__ == "__main__":
    main()
    
    
>>> 
'a'
	'b'
		'd'
		'e'
	'c'
		'h'
		'g'