알고리즘/알고리즘 개념

그래프의 탐색(DFS, BFS)

그래프 탐색의 목적 : 임의의 시작점 x에서 시작해서 모든 정점을 한번씩 반복하는 것 1. DFS(깊이우선탐색) - 한 시작점에서 갈 수 있을때 까지 계속진행하다 뒤도돌아오고 다시 갈수있는데 까지 감 - 스택사용해서 갈 수 있는 만큼 최대한 많이가고 - 갈 수 없으면 이전 정점으로 돌아간다. - 재귀호출을 이용해서 구현할 수 있다. // dfs(x) : x에 방문했다는 의미 // 인접 행렬 void dfs(int x){ check[x] = true; printf("%d",x); for(int i=1; i

그래프와 BFS

- 정점 : (Node, Vertex) - 간선(Edge) : 정점간의 관계를 나타낸다. - 그래프 : 정점과 간선이 있는것 - 경로 : 간선의 연속(시작점 ~ 도착점 까지 정점을 거쳐 감) - 최단경로 : 그래프의 경로 중 가장 짧은 것 - 사이클 : 경로인데, 시작점과 도착점이 같은 것 - 단순 경로/사이클 : 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클 (특별한 말이 없으면, 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말한다.) - 간선은 방향이 있을 수도 있고, 없을 수도 있다. - 방향이 없는 그래프 : 양방향 그래프 (서로 오갈 수 있음) - 방향이 없는 그래프는 저장을 할 수 없기 때문에 각 방향당 하나씩 총 두개 저장해 줘야 한다. - 간선이 여러개일 수..