고대어 사전 문제의 테스트 케이스 2번을 보면
o -> g -> k -> l -> h 의 방향그래프가 만들어지는데요
책 p.836의 tolopogical sort를 보면
for(int i=0; i<m; ++i) if(!seen[i]) difs(i);
처럼 알파벳 a부터 dfs를 실행하는데 이렇게 되면 위의 그래프에서 o가 아닌 g부터 탐색하게 되면서 hlkg순서로 order에 삽입되고 o는 나중에 i값이 한참 증가한 후에 order에 삽입되면서 순서가 이상하게 나옵니다. 제가 어디를 잘못 이해하고 있을까요? 위 코드에서는 어떻게 위상정렬 시 맨 처음 오는 정점을 (위에서는 o) 찾아서 거기서부터 탐색할 수 있을까요?
아래 종만북 코드입니다.
해결했습니다.
혹시라도 저같은 의문을 가지실 분들을 위해
위상 정렬된 후의 첫 정점이 dfs로 처음 탐색되는 정점보다 사전순으로 뒤에 오는 경우 어자피 뒤집으면 앞으로갑니다.
위상 정렬된 후의 첫 정점이 dfs로 처음 탐색되는 정점보다 사전순으로 앞에 오는 경우 첫 정점이 처음 탐색됩니다. 어떤 경우든 사전순으로 출력됩니다.
종만북끝내기
그래프 파트 읽는 중에 이해가 안되는 부분이 생겨서 질문드립니다.
고대어 사전 문제의 테스트 케이스 2번을 보면
o -> g -> k -> l -> h 의 방향그래프가 만들어지는데요
책 p.836의 tolopogical sort를 보면
for(int i=0; i<m; ++i) if(!seen[i]) difs(i);
처럼 알파벳 a부터 dfs를 실행하는데 이렇게 되면 위의 그래프에서 o가 아닌 g부터 탐색하게 되면서 hlkg순서로 order에 삽입되고 o는 나중에 i값이 한참 증가한 후에 order에 삽입되면서 순서가 이상하게 나옵니다. 제가 어디를 잘못 이해하고 있을까요? 위 코드에서는 어떻게 위상정렬 시 맨 처음 오는 정점을 (위에서는 o) 찾아서 거기서부터 탐색할 수 있을까요?
아래 종만북 코드입니다.
vector seen, order;
void dfs(int here){
seen[here]=1;
for(int there=0; there<adj.size(); ++there)
if(adj[here][there] && !seen[there])
dfs(there);
}
vector topologicalSort(){(m,0);
reverse(order.begin(),order.end());
for(int j=i+1; j
if(adj[order[j]][order[i]])();
int m=adj.size();
seen=vector
order.clear();
for(int i=0; i
for(int i=0; i
return vector
return order;
}
4년 전