간선의 종류1 DFS트리에서 간선의 종류, 사이클 검출 ㅁ방향그래프 dfs를 수행하면 그래프의 모든 간선을 한 번씩은 만나게 된다. 그래프에서 어떤 점에서 dfs를 수행하면 트리가 만들어지는데, 트리를 중심으로 그래프의 모든 간선의 종류를 구분해보면 1. 트리간선 dfs트리를 이루는 간선 2. 순방향 간선 스패닝 트리의 선조에서 자손으로 연결되지만 트리간선이 아닌 간선 3. 역방향 간선 트리의 자손에서 선조로 연결되는 간선. 당연히 트리간선에 포함 안됨. 그래프의 사이클유무 판단할때 사용하는 간선. ( 이 간선이 존재하면 그래프에 사이클 존재 ) 4. 교차간선 그 외의 모든 간선. 선조-자손관계가 아닌 정점들 간 연결된 간선. vector adj[MAX]; int vst[MAX]; //방문순서 기록. -1이면 방문안된것. bool fin[MAX]; int c.. 2020. 2. 13. 이전 1 다음