토폴로지 정렬 (링 이 있 는 지 판단 할 수 있 습 니 다 (링 네 거 티 브 링 은 상 관 없 음)

1762 단어 #정렬 알고리즘
데이터 구조 AOE 망 과 AOV - 망 1 절 
 
의 미 는:
일부 사건 과 활동 (그림) 을 제시 합 니 다. 이 사건 이 진행 되 는 전제조건 은 이 사건 을 후계 로 하 는 모든 활동 이 완성 되 었 다 는 것 입 니 다.
이 사건 들 에 순 서 를 배열 하여 사건 진행 과정 이 충돌 하지 않도록 하 다.
하면, 만약, 만약...  
         하나의 고리 가 존재 합 니 다.
그렇지 않 으 면
     토폴로지 서열 을 얻 을 수 있 고 대응 하 는 사건 이나 변 의 최초 발생 사건 과 가장 늦게 발생 하 는 시간 도 계산 할 수 있다.
코드 구현:
/*
    

*/
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1010;
struct Edge
{
    int v;
    int val;
    int next;
    Edge()
    {
        next=-1;
    }
} edge[maxn]; //    
int head[maxn];
int Indegree[maxn];
int seque[maxn];
int beg_time[maxn],end_time[maxn];
bool GetTuopu(int n,struct Edge edge[],int head[],int Indegree[],int seque[])//                  
{
    stackmmp;
    for(int i=0; ibeg_time[edge[to].v])
                    beg_time[edge[to].v]=beg_time[now_v]+edge[to].val;
                to=edge[to].next;
            }
        }
        /*----------------          ------------*/
        for(int i=0; iend_time[edge[to].v]-edge[to].val)
                    end_time[now_v]=end_time[edge[to].v]-edge[to].val;
                to=edge[to].next;
            }
        }
        for(int i=0; i

좋은 웹페이지 즐겨찾기