Day_04. Graph / Tree traversal

Graph / Tree Traversal
--Depth First Search – 시작 노드에서 stack구조를 이용해 Tree에서 깊이를 먼저 탐색한다
--Breadth First Search- Queue 구조를 사용함, 싶이보다 넓이를 우선으로 탐색한다



Finding Shortest path
--정의 :그래프가 연결되어 있을 때 임의의 두 노드를 대상으로 가장 최단의 거리를 찾는 것
---1)다익스트라 알고리즘 – 노드의 가중치가 방문한 node와 edge의 가중치에 의해 변경된다, 가중치가 작은게 기존의 노드의 가중치를 변경한다, 알고리즘의 끝은 설정한 종착점을 찾을 때로 종착점을 찾으면 알고리즘을 마무리 짓는다 

---2)prim 알고리즘- 시작 노드에서 다른 노드로 이동시 edge의 weight 가 가장작은 weight 로 이동하고 이동한 node, 이동하지 않은 node로 구분해서 지정한다. 

Bridge , local bridge
--1)bridge – 삭제하면 node와 node간의 연결이 전혀 없어지는 edge
--2)Local bridge – edge를 제거시 연결하기 위해 2개의 edge이상으로 돌아서 다시 해당 노드를 방문해야 하는 edge