拓扑排序

说明

拓扑排序用于处理有向图顺序的问题,比如在到达一个顶点之前必须要先到达一个顶点。

BFS

说明

将所有入度为0的点全都push进队列,然后对队列中的每一个点u执行两个操作。

  1. 将其排入topo数组之中
  2. 找对应的临接点v,并将这条边删除(表现为将v的入度减一),如果此时v的入度为0了,则将v点Push进队列。当队列为空时,topo数组即为排好序的序列。

使用方法

  1. init()初始化
  2. head[u].push_back(v); indegree[v]++; 顶点下标从1~n,表示完成v之前必须要完成u
  3. bool ok = toposort(); //返回值为false表示有环
  4. 得到topo[]即为排好序的数组

Tips

  • 下标必须从1开始

模版

//下标从1~n
const maxn=1000;
int n,m;//n个点 m条边
vector<int>head[maxn];
int indegree[maxn];//记录入度
int topo[maxn];
void init(){
    for (int i=0; i<=n; i++) {
        head[i].clear();
        indegree[i]=0;
        topo[i]=0;
    }
}
bool toposort(){
    int index=1,cnt=0;
    priority_queue<int>q;
    for (int i=1; i<=n; i++) {
        if (indegree[i]==0) {
            q.push(i);
        }
    }
    if(q.empty()) return false;
    while (!q.empty()) {
        cnt++;        
        int u=q.top();
        q.pop();
        topo[index++]=u;
        int sz=head[u].size();
        for (int i=0; i<sz; i++) {
            int v=head[u][i];
            if (--indegree[v]==0) {
                q.push(v);
            }
        }
    }
    if(cnt==n) return true;
    else return false;
}
void showAns(){
    for (int i=1; i<=n; i++) {
        printf("%d%c",topo[i],i==n?'\n':' ');
    }
}

DFS

说明

总共n个点(0~n-1),m组关系。

t:topo数组反向记录时的位置下标。

G数组:邻接矩阵 G[u][v]=1表示 u到v单向连通。

c数组:0表示未访问,1表示已找过,-1表示在DFS递归中。

topo数组:记录拓扑排序后的结果。

使用举例:UVa 10305 Ordering Tasks

使用方法

  1. memset(G,0,sizeof(G)); 清空G数组
  2. adde(u, v);加一条从u指向v的边,顶点下标从1~n,但是在G中存是从0~n-1
  3. toposort();调用该函数进行排序,返回值为false表示有环,否则表示没有环

模版

//下标1~n
const maxn=1000;
int G[maxn][maxn];//邻接矩阵
int n,m;
int c[maxn];
int topo[maxn],t;
void adde(int u, int v){
    G[u-1][v-1]=1;
}
bool dfs(int u){
    c[u]=-1;//访问标志
    for (int v=0; v<n; v++)
        if (G[u][v])
            if (c[v]<0) return false;
            else if (!c[v]&&!dfs(v)) return false;
    c[u]=1;
    topo[--t]=u;
    return true;
}
bool toposort(){
    t=n;
    memset(c,0,sizeof(c));
    for (int u=0; u<n; u++)
        if (!c[u]&&!dfs(u)) return false;
    return true;
}
void showAns(){
    for (int i=0; i<n; i++) {
        printf("%d%c",topo[i]+1,i==n-1?'\n':' ');
    }
}

results matching ""

    No results matching ""