토폴로지 정렬 총화
7401 단어 데이터 구조 정리
1. 머리말
토폴로지 정렬 의 주요 역할 은 현재 그림 에 고리 가 있 는 지 판단 하 는 데 사용 된다.그 주요 한 실현 사상 은 그림 속 의 입 도 를 0 으로 하 는 점 부터 찾 으 면 이 점 을 그림 에서 삭제 하고 이 점 과 연 결 된 다른 점 의 입 도 정 보 를 업데이트 하 며 모든 점 이 삭제 되 거나 그림 에 입 도 를 0 으로 하 는 점 이 없다 는 것 이다. 만약 에 뒤의 상황 이 라면 그림 에 고리 가 포함 되 어 있다 는 것 을 증명 하 는 것 이다.
2. 실현
코드 의 실현 은 구체 적 으로 다음 과 같다.
#include
using namespace std;
void Top_sort(int **map,int n)//n ,m
{
int number[105] = { 0 };
for(int i=1;i<=n;i++)//
{
for(int j=1;j<=n;j++)
{
if(map[j][i])
{
number[i]++;
}
}
}
int queue[105];// Top_sort
int tail = 1;
int start = 0;
int count = 0;
while (1)
{
int flag = 0;
for (int i = 1; i <= n; i++)
{
if (number[i] == 0)// 0
{
number[i] = -1;
queue[tail] = i;
tail++;
flag = 1;
for (int j = 1; j <= n; j++)//
{
if (map[i][j])
{
number[j]--;
}
}
count++;
}
}
if(count==n||!flag)//
{
break;
}
// 0
}
}
?실현 하 는 것 은 결코 번 거 롭 지 않 고, 생각 이 뚜렷 한 후에 사실은 매우 간단 하 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
토폴로지 정렬 총화토폴로지 정렬 총화 1. 머리말 토폴로지 정렬 의 주요 역할 은 현재 그림 에 고리 가 있 는 지 판단 하 는 데 사용 된다.그 주요 한 실현 사상 은 그림 속 의 입 도 를 0 으로 하 는 점 부터 찾 으 면 이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.