토폴로지 정렬 총화

토폴로지 정렬 총화
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               
	}
}

?실현 하 는 것 은 결코 번 거 롭 지 않 고, 생각 이 뚜렷 한 후에 사실은 매우 간단 하 다.

좋은 웹페이지 즐겨찾기