算法总结2——拓扑排序

一.概念部分

1.拓扑排序介绍

        将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列，就是拓扑排列。在C++语言中，我们可以使用邻接表来表示有向图。

       例如，一个项目包括A、B、C、D四个子部分来完成，并且A依赖于B和D，C依赖于D。现在要制定一个计划，写出A、B、C、D的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。

2.有向无环图介绍

        一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。一个AOV网就是一个有向无环图。

3.邻接表介绍

        邻接表是图的一种链式存储方法，其数据结构包括两部分：节点和邻接点。

（1）无向图的邻接表

图表如下：

解释：

• 节点V0的邻接点是节点V1，V2 ，V3，其邻接点的存储下标为1，2，3，按照头插法（逆序）将其放入节点V0后面的单链表中；

• 节点V1 的邻接点是节点V0 ，V2，其邻接点的存储下标为0，2，将其放入节点V1 后面的单链表中；

• 节点V2 的邻接点是节点V0，V1，V3，其邻接点的存储下标为0，1，3，将其放入节点V2 后面的单链表中；

• 节点V3 的邻接点是节点V0，V,2，其邻接点的存储下标为0，2，将其放入节点V3 后面的单链表中。

特点如下：

• 如果无向图有n 个节点、e 条边，则节点表有n 个节点，邻接点表有2e 个节点。

• 节点的度为该节点后面单链表中的节点数。

（2）有向图的邻接表（出弧）

图表如下：

   解释：

• 节点V0 的邻接点（只看出边，即出弧）是节点V3，其邻接点的存储下标为3，按照头插法（逆

序）将其放入节点V0 后面的单链表中；

• 节点V1 的邻接点是节点V0 ，V2，其邻接点的存储下标为0，2，将其放入节点V1后面的单链表中；

• 节点V2 的邻接点是节点V0，V1 ，其邻接点的存储下标为0，1，按头插法将其放入节点V0 后面的单链表中；

• 节点V3 没有邻接点，其后面的单链表为空。

特点如下：

• 如果有向图有n 个节点、e 条边，则节点表有n 个节点，邻接点表有e 个节点。

• 节点的出度为该节点后面单链表中的节点数。

（3）有向图的逆邻接表（入弧）

图表如下：

解释：

• 节点V0  的逆邻接点（只看入边，即入弧）是节点V1，V2，其邻接点的存储下标是1，2，其放入

节点V0 后面的单链表中；

• 节点V1  的逆邻接点是节点V2  ，其邻接点的存储下标为2，将其放入节点V1 后面的单链表中；

• 节点V2  的逆邻接点是V1，其邻接点的存储下标为1，按照头插法将其放入节点V2 后面的单链表中；

• 节点V3  的逆邻接点是节点V0  ，其邻接点的存储下标为0，将其放入节点V3 后面的单链表中；

特点如下：

• 如果有向图有n 个节点、e 条边，则节点表有n 个节点，邻接点表有e 个节点。

• 节点的入度为该节点后面的单链表中的节点数。

（4）邻接表的代码实现

//创建有向图的邻接表
#include using namespace std;
const int MaxVnum=100;//顶点数最大值
 
typedef char VexType;//顶点的数据类型为字符型
typedef struct AdjNode{ //定义邻接点类型
	int v; //邻接点下标
	struct AdjNode *next; //指向下一个邻接点
}AdjNode;
 
typedef struct VexNode{ //定义顶点类型
	VexType data; // VexType为顶点的数据类型，根据需要定义
	AdjNode *first; //指向第一个邻接点
}VexNode;
 
typedef struct{//定义邻接表类型
    VexNode  Vex[MaxVnum];
    int vexnum,edgenum; //顶点数，边数
}ALGragh;
 
int locatevex(ALGragh G,VexType x)
{
    for(int i=0;iv=j;
    s->next=G.Vex[i].first;
    G.Vex[i].first=s;
}
 
void printg(ALGragh G)//输出邻接表
{
   cout<<"----------邻接表如下：----------"<v<<"]  ";
           t=t->next;
       }
       cout<>G.vexnum>>G.edgenum;
    cout << "请输入顶点信息:"<>G.Vex[i].data;
    for(i=0;i>u>>v;
        i=locatevex(G,u);//查找顶点u的存储下标
        j=locatevex(G,v);//查找顶点v的存储下标
        if(i!=-1&&j!=-1)
            insertedge(G,i,j);
        else
        {
           cout << "输入顶点信息错！请重新输入！"< 
4.拓扑排序的实现
 
（1）步骤：
 
 
1. 构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological)； 
 
2. 把所有没有依赖顶点的节点放入Q； 
 
3. 当Q还有顶点的时候，执行下面步骤： 
 
3.1 从Q中取出一个顶点n(将n从Q中删掉)，并放入T(将n加入到结果集中)； 
 
3.2 对n每一个邻接点m(n是起点，m是终点)； 
 
3.2.1 去掉边; 
 
3.2.2 如果m没有依赖顶点，则把m放入Q; 
 
注：顶点A没有依赖顶点，是指不存在以A为终点的边。
 
 
（2）代码实现
 
#include #include #include using namespace std;
 
class Graph {
private:
    int V;
    vector> adj;
 
public:
    Graph(int v) : V(v), adj(v) {}
 
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
 
    void topologicalSortUtil(int v, vector& visited, stack& stk) {
        visited[v] = true;
 
        for (int i : adj[v]) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stk);
            }
        }
 
        stk.push(v);
    }
 
    void topologicalSort() {
        vector visited(V, false);
        stack stk;
 
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stk);
            }
        }
 
        cout << "拓扑排序结果：" << endl;
        while (!stk.empty()) {
            cout << stk.top() << " ";
            stk.pop();
        }
        cout << endl;
    }
};
 
int main() {
    int V = 6; // 图的节点数
    Graph g(V);
 
    // 添加图的边
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
 
    g.topologicalSort();
 
    return 0;
}
 
二.实例
 
 New Gae
 
解题思路：关键信息为 A 赢 B，B 赢 C，则排名为 A → B → C。
 
题解：
 
#includeusing namespace std;
const int maxn=2e3+100;
const int inf=0x3f3f3f3f;
inline int rd() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int t;
int n,m;
vectorve[maxn],res;
int a,b,in[maxn];
signed main() {
    t=rd();
    while(t--) {
        for(int i=1; i<=n; i++)ve[i].clear();
        memset(in,0,sizeof in);
        n=rd();
        m=rd();
        for(int i=1; i<=m; i++) {
            a=rd();
            b=rd();
            ve[a].push_back(b);
            in[b]++;
        }
        priority_queue,greater >q;
        for(int i=1; i<=n; i++) {
            if(!in[i]) {
                q.push(i);
            }
        }
        while(!q.empty()) {
            int u=q.top();
            q.pop();
            res.push_back(u);
            for(int i=0; i