그래프

그래프 용어

1.노드(node) : 위치를 말하고 Vertex(정점)라고도 함
2. 간선(edge) : 위치 간의 관계를 표시헌 선, link 또는 branch 라고도 함
3. 인접 정점 (Adjacent Vertax) 간선으로 직접 연결된 정점

그래프와 트리의 차이

1. 그래프
   1-정의 : 노드와 노드를 연결하는 간선으로 표현한 자료구조
   2-방향성 : 방향 그래프, 무방향 그래프 둘 다 존재
   3-사이클 : 순환 및 비순환 그래프 둘 다 존재
   4-루트 노드 : 루트 노드 존재하지 않음
   5-부모/자식 : 부모 자식 개념 존재하지 않음
   
   
2. 트리
   1-정의 : 그래프의 한 종류, 방향성 있는 비순환 그래프
   2-방향성 : 방향 그래프만 존재
   3- 사이클 : 비순환 그래프로 사이클 존재하지 않음
   4-루트 노드 : 루트 노드 존재
   5- 부모/자식: 개념 존재

너비 우선 탐색 Breadth-Frist Search)

-> 정점들과 같은 레벨에 있는 형제 노드들을 먼저 탐색하는 방식
-> 큐 두개를 이용한다
-> 시간 복잡도 : O(node+edge)

#shift+ Enter 
def BFS(graph, root):
    visited, need_visit = list() , list() # 큐 두개
    need_visit.append(root) #need_visit 에 시작할 원소를 넣음
    
    while need_visit: # need_visit가 NUll 이란 것은 모든 그래프를 순환했다
        node = need_visit.pop(0) # 큐 역활

        if node not in visited: # need_Vist 의 첫 원소가 방문한 건지 아닌지 확인
            visited.append(node)
            need_visit.extend(graph[node])

    return visited


graph =dict(); # 그래프를 딕셔너리에 넣음
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

print(BFS(graph,'A'))

깊이 우선 탐색 Depth-Frist Search

->한 노드를 타고 끝까지 순회한 후 현제 자식의 노드를 타고 내려가며 순회
-> 큐, 스택을 사용한다
->-> 시간 복잡도 : O(node+edge)

graph =dict(); # 그래프를 딕셔너리에 넣음
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

def DFS(graph,start_node):
	visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
    	node = need_visit.pop()
        if node not in visited:
        	visited.append(node)
            need_visit.extend(graph[node])
    return visited