2023/2/10总结

拓扑排序

拓扑排序是在一个有向无环图（DAG）所有顶点的线性排序。

拓扑排序核心思想非常简单，就是先找一个入度为0的顶点输出，再从图中删除该顶点和以它为起点的有向边。继续上面的操作知道所有的顶点访问完为止。

入度：指的是能访问到该节点的其他节点总数。

出度：指的是该节点能访问到其他节点的总数。

拓扑排序说起来简单代码实现就不一定咯。

有俩种方法：

第一种：

卡恩算法。

1. 先遍历图，记住图的入度。
2. 再找到一个 入 度 为0的 删掉它（把它标记为-1）
3. 并且把由入度为0能访问的节点的入度减去1.
4. 如果有些节点没有出来，说明这个图存在环。

第二种： 

dfs方法。

1. 我们设立一个数组visted[N];当visited数组值为0，表示还未访问，为1表示正在访问，为-1表示访问结束
2. 递归访问节点，将该节点状态设置为1
3. 递归访问该节点的后续节点
4. 将该节点状态设置为-1，并且输出（输出结果是逆序）

卡恩算法和dfs算法，dfs算法像是卡恩算法的逆序操作，他们的时间复杂度是一样的。

最好使用邻接表存储

下面是我自己写出的卡恩算法和dfs算法：

我在dfs算法里面没有判断出现环路的情况。

#include<stdio.h>
#include<malloc.h>
#define N 100
#define MAX 999999
int m,n,stin[N],visted[N],res[N],nox;
typedef struct node
{int v;struct node *next;
}NODE;
NODE k[N];
int fun(NODE *head,int v)
{NODE *p,*q;if(head==NULL){head=(NODE *)malloc(sizeof(NODE));head->v=v;head->next=NULL;}p=head;while(p!=NULL){q=p;p=p->next;}p=(NODE *)malloc(sizeof(NODE));p->v=v;q->next=p;p->next=NULL;
}
int put(NODE *head)
{head=head->next;while(head){printf("%d ",head->v);head=head->next;}puts("");
}
int kahn()
{int i,flag=1;NODE *p;while(flag){flag=0;for(i=1;i<=n;i++){if(stin[i]==0) {stin[i]=-1;flag=i;break;}}if(flag) printf("%d ",flag);p=k+flag;p=p->next;while(p!=NULL){stin[p->v]--;p=p->next;}}puts("");
}
int dfs(int x)
{int i;NODE *p=k+x;p=p->next;while(p!=NULL){if(visted[p->v]==0){dfs(p->v);visted[p->v]=1;}p=p->next;}res[nox++]=x;return 0;
}
int main()
{int i,j,u,v;puts("请输入顶点数量：");scanf("%d",&n);puts("请输入边的数量：");scanf("%d",&m);for(i=0;i<=n;i++){k[i].v=0;k[i].next=NULL;}for(i=0;i<m;i++){scanf("%d%d",&u,&v);stin[v]++;fun(k+u,v);}puts("邻接表为：");for(i=1;i<=n;i++){printf("%d-> ",i);put(k+i);}puts("拓扑排序为：");//	kahn();for(i=1;i<=n;i++){if(stin[i]==0)dfs(i);}for(i=nox-1;i>=0;i--)printf("%d ",res[i]);return 0;
}