그래프와 인접리스트 인접행렬, 순회(전위,중위,후위)

그래프, 인접리스트, 인접행렬, 순회(전위,중위,후위)

 

 

 

그래프

 

• 그래프는 노드간의 관계를 나타낸다.
• 그래프의 특성은 directed(방향성) 또는 undirected(무방향성) 그래프가 있다.
• 그래프 용어
  • 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
  • 단말 노드(leaf node) : 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
  • 내부(internal) 노드 : 단말 노드가 아닌 노드
  • 형제(sibling) : 같은 부모를 가지는 노드
  • 간선(edge) : 노드를 연결하는 선 (link, branch 라고도 부름

 

 

인접행렬, 인접리스트

그래프

다음과 같은 그래프를 인접행렬과 인접리스트로 구현해보자.

# 인접리스트 구현
class Graph:
    def __init__(self):
        self.vertices = {
                            "A": {"B": 1},          
                            "B": {"C": 3, "D": 2},  
                            "C": {},
                            "D": {},
                            "E": {"D": 1}           
                        }

# 인접행렬 구현
class Graph:
    def __init__(self):
        self.edges = [[0,1,0,0,0],
                      [0,0,3,2,0],
                      [0,0,0,0,0],
                      [0,0,0,0,0],
                      [0,0,0,1,0]]

 

 

 

순회 (전위, 중위, 후위)

 

• 순회는 그래프에 연결된 노드를 탐색한다. 

---

전위순회(Preorder Traversal)

• 부모노드 > 왼쪽 자식노드 > 오른쪽 자식노드

전위순회

 

중위순회(Inorder Traversal)

• 왼쪽 자식노드 > 부모노드 > 오른쪽 자식노드

중위순회

 

후위순회(Postorder Traversal)

• 왼쪽 자식노드 > 오른쪽 자식노드 > 부모노드

후위순회

 

참고 코드

class Node:
    # root -> left -> right 방향대로 노드 생성
    def __init__(self, value, left=None, right=None): 
        self.value = value
        self.left = left
        self.right = right

# 전위 순회 
def pre_order(node):
    print(node.value, end=' ')       # 루트노드
    if node.left:
        pre_order(node.left)    # 왼쪽노드
    if node.right:
        pre_order(node.right)   # 오른쪽노드

# 중위 순회
def in_order(node):
    if node.left:
        in_order(node.left)    # 왼쪽노드
    print(node.value, end=' ')      # 루트노드
    if node.right:
        in_order(node.right)   # 오른쪽노드

# 후위 순회
def post_order(node):
    if node.left:
        post_order(node.left)   # 왼쪽노드
    if node.right:
        post_order(node.right)  # 오른쪽노드
    print(node.value, end=' ')       # 루트노드


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.left = Node(8)
root.left.left.right = Node(9)
root.left.right.left = Node(10)
root.left.right.right = Node(11)
root.right.left.right = Node(13)
root.right.right.left = Node(14)

print('전위순회')
pre_order(root)
print()
print('중위순회')
in_order(root)
print()
print('후위순회')
post_order(root)