代码随想录算法训练营day58：图论08：拓扑排序精讲；dijkstra（朴素版）精讲
拓扑排序精讲
卡码网：117. 软件构建(opens new window)
题目描述：
某个大型软件项目的构建系统拥有 N 个文件，文件编号从 0 到 N - 1，在这些文件中，某些文件依赖于其他文件的内容，这意味着如果文件 A 依赖于文件 B，则必须在处理文件 A 之前处理文件 B （0 <= A, B <= N - 1）。请编写一个算法，用于确定文件处理的顺序。
输入描述：
第一行输入两个正整数 M, N。表示 N 个文件之间拥有 M 条依赖关系。
后续 M 行，每行两个正整数 S 和 T，表示 T 文件依赖于 S 文件。
输出描述：
输出共一行，如果能处理成功，则输出文件顺序，用空格隔开。
如果不能成功处理（相互依赖），则输出 -1。
分析：
应用场景：对于复杂的依赖关系，给出线性的依赖顺序
eg：大学排课，例如 先上A课，才能上B课，上了B课才能上C课，上了A课才能上D课，等等一系列这样的依赖顺序。 问给规划出一条 完整的上课顺序。
概括来说，给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。
当然拓扑排序也要检测这个有向图 是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。
所以拓扑排序也是图论中判断有向无环图的常用方法。
思路 bfs：
**初始化：
因为是有向，可以用邻接表记录
需要记录每个结点的入度（在vnode里可以记录，注意s->t的边，t的innode++），和每个结点的依赖关系
for循环：循环n次，因为要把所有的点都取出来
1、找开头 入度为0的结点，加入结果集
**开头的结点入度=0
找入度为0 的节点，我们需要用一个队列放存放。
因为每次寻找入度为0的节点，不一定只有一个节点，可能很多节点入度都为0，所以要将这些入度为0的节点放到队列里，依次去处理。
加入队列之后，入度改为-1，这样不会重复影响结果
2、把这个结点从图上去掉
反复，直到所有节点都被删除
实际上操作时，要把 该节点作为出发点所连接的节点的 入度 减一。
eg：准备删0，那就是把1和2的结点入度-1
判断有向环的方式：
如果我们发现结果集元素个数 不等于 图中节点个数，我们就可以认定图中一定有 有向环！
#include <math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>typedef struct arcnode{int node;struct arcnode *nextnode;
}Arcnode;typedef struct {int into;Arcnode *firstarc;
}Vnode;typedef struct {Vnode list[1000];
}graph;int main(){int n,m;scanf("%d%d",&n,&m);graph* g=(graph* )malloc(sizeof(graph));//用邻接表for(int i=0;i<n;i++) g->list[i].firstarc=NULL;for(int i=0;i<n;i++) g->list[i].into = 0;for(int i=0;i<m;i++){int s,t;scanf("%d%d",&s,&t);Arcnode *p=(Arcnode *)malloc(sizeof(Arcnode));p->node=t;p->nextnode=g->list[s].firstarc;g->list[s].firstarc = p;g->list[t].into++;}int queue[60000];int front=-1,rear=-1;int count=0;int *ans = (int*)malloc(sizeof(int)*n);for(int i=0;i<=n-1;i++){for(int j=0;j<n;j++){//所有入度为0的结点都进队if(g->list[j].into==0){rear++;queue[rear]=j;g->list[j].into=-1;}}front++;//出一个入度为0的结点，并且记录int s = queue[front];ans[count++]=s;Arcnode*p = g->list[s].firstarc;//把以该结点为起点，终点处的入度都-1while(p!=NULL){int w = p->node;g->list[w].into--;p=p->nextnode;}}if(count!=n) printf("-1");else {for(int i=0;i<n-1;i++) printf("%d ",ans[i]);printf("%d",ans[n-1]);}return 0;
}