当前位置: 首页 > news >正文

秀屿网站建设免费个人网站制作

秀屿网站建设,免费个人网站制作,网络公司经营范围如何填写,天美影视传媒广告制作流程拓扑排序 拓扑排序是在一个有向无环图(DAG)所有顶点的线性排序。 拓扑排序核心思想非常简单,就是先找一个入度为0的顶点输出,再从图中删除该顶点和以它为起点的有向边。继续上面的操作知道所有的顶点访问完为止。 入度&#xf…

拓扑排序

拓扑排序是在一个有向无环图(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;
}

http://www.ritt.cn/news/19047.html

相关文章:

  • 营销网站设计公司排名百度知道网页版登录入口
  • 怎么在企业站建立网站深圳seo网站优化公司
  • php简单购物网站源码百度seo公司整站优化
  • 衢州网站开发公司百度指数特点
  • 任丘 做网站武汉网站seo
  • 郴州网站建设设计网店推广分为哪几种类型
  • 做一个购物网站价格济南竞价托管
  • 去国外政府网站做轮胎认证代运营哪家比较可靠
  • 网站怎么设计制作王通seo教程
  • 有哪些网站做的很有特色搜索软件使用排名
  • 朗姿青春日记 网站谁做的湖人队最新消息
  • 网站源码免费分享注册域名后怎么建网站
  • 建站与备案的具体流程是什么百度权重等级
  • 怎么制作动态网页seo搜索引擎优化平台
  • 北京丰台做网站长沙seo优化推荐
  • 仁怀哪儿做网站百度游戏客服在线咨询
  • 自适应型网站建设费用seo优化或网站编辑
  • 我的电脑做网站服务器吗seo工具有哪些
  • 百度竞价网站怎么做网络营销有哪些主要功能
  • 北京市建设工程信息网交易网站网站推广在线推广
  • b站 私人直播间有什么可以做推广的软件
  • 苏州朗冠网站建设公司磁力搜索神器
  • 公司给别人做的网站违法的吗seo计费系统开发
  • 用dz程序做的电影网站社区营销推广活动方案
  • java学完后可以做网站吗关键词挖掘工具站
  • 做地方网站要办什么证职业技能培训网上平台
  • 谷歌优化网站链接怎么做友链对网站seo有帮助吗
  • 网站升级建设费用网络营销网课
  • 如何建立一个网站及app百度的广告怎么免费发布
  • 广东网站备案需要多久建立网站的软件