怎么才能登网站做外贸,南宁网上房地产官网,自助建网站哪个好,网站建立有哪些功能拓扑排序
拓扑排序是在一个有向无环图#xff08;DAG#xff09;所有顶点的线性排序。
拓扑排序核心思想非常简单#xff0c;就是先找一个入度为0的顶点输出#xff0c;再从图中删除该顶点和以它为起点的有向边。继续上面的操作知道所有的顶点访问完为止。
入度#xf…拓扑排序
拓扑排序是在一个有向无环图DAG所有顶点的线性排序。
拓扑排序核心思想非常简单就是先找一个入度为0的顶点输出再从图中删除该顶点和以它为起点的有向边。继续上面的操作知道所有的顶点访问完为止。
入度指的是能访问到该节点的其他节点总数。
出度指的是该节点能访问到其他节点的总数。
拓扑排序说起来简单代码实现就不一定咯。
有俩种方法
第一种
卡恩算法。
先遍历图记住图的入度。再找到一个 入 度 为0的 删掉它把它标记为-1并且把由入度为0能访问的节点的入度减去1.如果有些节点没有出来说明这个图存在环。
第二种
dfs方法。
我们设立一个数组visted[N];当visited数组值为0表示还未访问为1表示正在访问为-1表示访问结束递归访问节点将该节点状态设置为1递归访问该节点的后续节点将该节点状态设置为-1并且输出输出结果是逆序
卡恩算法和dfs算法dfs算法像是卡恩算法的逆序操作他们的时间复杂度是一样的。
最好使用邻接表存储
下面是我自己写出的卡恩算法和dfs算法
我在dfs算法里面没有判断出现环路的情况。
#includestdio.h
#includemalloc.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(headNULL){head(NODE *)malloc(sizeof(NODE));head-vv;head-nextNULL;}phead;while(p!NULL){qp;pp-next;}p(NODE *)malloc(sizeof(NODE));p-vv;q-nextp;p-nextNULL;
}
int put(NODE *head)
{headhead-next;while(head){printf(%d ,head-v);headhead-next;}puts();
}
int kahn()
{int i,flag1;NODE *p;while(flag){flag0;for(i1;in;i){if(stin[i]0) {stin[i]-1;flagi;break;}}if(flag) printf(%d ,flag);pkflag;pp-next;while(p!NULL){stin[p-v]--;pp-next;}}puts();
}
int dfs(int x)
{int i;NODE *pkx;pp-next;while(p!NULL){if(visted[p-v]0){dfs(p-v);visted[p-v]1;}pp-next;}res[nox]x;return 0;
}
int main()
{int i,j,u,v;puts(请输入顶点数量);scanf(%d,n);puts(请输入边的数量);scanf(%d,m);for(i0;in;i){k[i].v0;k[i].nextNULL;}for(i0;im;i){scanf(%d%d,u,v);stin[v];fun(ku,v);}puts(邻接表为);for(i1;in;i){printf(%d- ,i);put(ki);}puts(拓扑排序为);// kahn();for(i1;in;i){if(stin[i]0)dfs(i);}for(inox-1;i0;i--)printf(%d ,res[i]);return 0;
}
