Euler trail1 [C++ 알고리즘] 오일러 회로 / 오일러 경로 (Euler ciruit / Euler trail) 오일러 회로 문제 : 그래프의 모든 간선을 한 번씩만 지나면서, 모든 정점을 들린 뒤 시작점으로 돌아오는 문제. 다른 조건은 만족하되, 시작점으로 돌아오지 않아도 되는 문제는 오일러 경로 문제이다. 어떠한 양방향 그래프가 주어졌을 때, 오일러 회로 또는 경로가 존재할 수 있는지 판단할 수 있는 필요충분조건 두 가지가 존재한다. 양방향 그래프에서 오일러 회로 또는 경로가 존재하기 위한 필요충분조건 1. 모든 정점이 하나의 컴포넌트 안에 속해 있는가? 이를 확인하기 위해서 사용할 수 있는 방법 중 하나는, 한 정점에 대하여 dfs 또는 bfs를 사용해서 탐색을 한 번 마친 뒤, 방문하지 않은 정점이 존재할 경우 두 개 이상의 컴포넌트가 존재함을 알아낼 수 있다. int chk[N]; int adj[N][N].. 2021. 3. 1. 이전 1 다음
