토폴로지 정렬 bfs 알고리즘
DFS 보다 이해 하기 쉬 운 게 많아 요.
토폴로지 정렬 알고리즘 사상
1. AOV 네트워크 에서 직접 전구 가 없 는 정점 을 선택 하고 출력 합 니 다.
2. 그림 에서 이 정점 을 삭제 하고 모든 방향 을 삭제 합 니 다.
3. 상기 절 차 를 반복 하여
◆ 모든 정점 이 출력 되 고 토폴로지 의 질서 있 는 서열 이 형성 되 며 토폴로지 정렬 이 완료 되 었 습 니 다.
◆ 그림 에 출력 되 지 않 은 정점 이 있 지만 처리 순환 에서 벗 어 났 다.이 설명 그림 에는 아직 정점 이 남 았 는데, 그것들 은 모두 직접적인 선구 가 있어 서, 더 이상 선구 가 없 는 정점 을 찾 을 수 없다.이때 AOV 네트워크 에는 반드시 방향 고리 가 존재 한다.두 가지 상황 으로 만 든 문제 로 이 해 를 심화 시킨다 (토폴로지 정렬 이 완성 되 고 AOV 네트워크 에 반드시 방향 고리 가 존재 한다).
이런 좋 은 실현:
사실 토폴로지 순 서 는 넓 은 검색 이다.
토폴로지 정렬 방법 은 다음 과 같다.
(1) 그림 에서 전구 가 없 는 정점 을 선택 하고 출력 합 니 다.
(2) 인터넷 에서 이 정점 을 삭제 하고 이 정점 에서 나 오 는 모든 방향 을 삭제 합 니 다.
(3) 상기 두 단 계 를 반복 하여 남 은 네트워크 에 더 이상 앞으로 나 아가 지 않 는 정점 이 존재 하지 않 을 때 까지 한다.
int graph[narray][narray]; //
int indegree[narray]; //
int n; //n
memset(graph,0,sizeof(graph));
memset(indegree,0,sizeof(indegree));
for(i=1;i<=n;++i) // n
{
for(j=1;j<=n;++j) //
{
if(indegree[j]==0)
{
indegree[j]--; // -1，
if(i!=n) printf("%d ",j);
else printf("%d
",j);
for(k=1;k<=n;++k)
{
if(graph[j][k])
indegree[k]--; //
}
break;
}
}
}출처:http://blog.chinaunix.net/uid-26602509-id-3196077.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
