首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >图算法如果图是连通的、二部的、有圈的、是树的

问图算法如果图是连通的、二部的、有圈的、是树的
EN

Stack Overflow用户
提问于 2013-03-13 19:06:30
回答 1查看 17K关注 0票数 9

当我试图使用图形并为其编写一些代码时,我遇到了一个问题:/ !!

我想要创建一些东西来获取图表的数据,并检查它是否是: 1-连通的2-二分3-有循环4-是一棵树。

因此,我想知道,例如,是否可以将其写入从.txt文件中读取图形数据,以便进行上述测试??

使用简单的边缘列表格式是正确的方法吗?

如果你能给我一个链接来阅读如何完成这个任务,或者代码的启动!!

谢谢:D

EN

回答 1

Stack Overflow用户

发布于 2013-03-13 19:49:10

检查是否是:

  1. 已连接

对于这一个,你试着从一个点遍历整个图,看看你是否成功。深度优先遍历和宽度优先遍历在这里都是可以接受的.此算法将将节点拆分为组件:

  • 将所有节点标记为未访问
  • 对于每个节点c,如果此节点未被访问,则为
    • 创建一个新的空节点集,当前组件
    • 将此节点排队进行遍历
    • 当有任何节点时,t排队的
      • 从队列中删除此节点
      • 将每个未访问的邻居标记为打开,并将其排队进行遍历。
      • 将此节点标记为遍历
      • 将此节点添加到当前组件

​

代码语言:javascript
复制
- close the current component, and add it to the set of components

​

如果只有一个组件,则图是连通的。

如果使用队列,则该算法是宽度优先搜索。如果使用堆栈,则该算法是深度优先搜索.任何其他集合与推送和弹出-任何操作都可以。特别令人感兴趣的是调用堆栈:将“遍历队列”替换为“递归遍历”。

对于有向图,有向图有两个相关的概念:有向图是弱连通的当且仅当它是连通的,忽略了所有的边方向。有向图是强连通的当且仅当每个节点都可以从每个节点到达。为了测试强连通性,只需使用前向边缘检查每个节点是否可从第一个节点到达,而从第一个节点仅使用向后边缘即可到达每个节点(第一个节点可从每个节点到达)。

  1. 二部

图是二分的当且仅当它是双色的。尝试分配双色,如果失败,则图不是二分图。这可以合并到前面的算法中:每当您将节点标记为打开时,为其分配颜色,与分配给其邻居t的颜色相反。当t的邻居已经打开时,检查它的颜色。如果其颜色与t相同,则不存在双色。

  1. 有周期

这一点很简单:如果您观察到任何已经打开的节点,就会有一个循环。请注意,每个没有圈的图都是二分图。

在有向图中,这将检测无向循环的存在。要检测有向循环的存在,请使用以下(拓扑排序)算法:

  • 当有一个索引为零的节点时
    • 将节点添加到拓扑排序(与检测周期无关)
    • 从图中移除节点

​

  • 如果图中仍有任何节点
    • 这个图包含一个有向循环。在该图上不存在拓扑排序

​

  • 否则
    • 图不包含有向循环(是无圈的)。生成的拓扑排序是有效的。

​

  1. 树

无向图是一棵树当且仅当它是连通的且不包含循环。

有向图是根树当且仅当它没有无向圈,并且只有一个索引为零的顶点(只有一个根)。另外,有向图是根树当且仅当它是连通的,没有无向循环,并且每一个输出度为零的节点最多有一个索引(每个接收器都是一片叶子)。

票数 25
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/15394254

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档