图形算法查找图形是否连接,二分,有周期并且是树

Question

当我尝试使用图形并为它编写一些代码但没有运气时,我遇到了一个问题:/ !!

我想创建一些能够获取图形数据的东西并检查它是否:1-连接2-二分3-具有循环4-是树

所以我想知道,例如,如果这可以写入从.txt文件中读取图形数据,将执行上述测试？

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

如果您能给我一个链接,了解如何执行此任务或启动代码,我们将非常感谢您的帮助!

感谢:D

Answer 1

检查是否:

1. 连接的

对于这个,您尝试从一个点遍历整个图形,看看您是否成功.这里可以接受深度优先遍历和广度优先遍历.该算法将节点拆分为组件:

• 将所有节点标记为未访问
• 对于每个节点c,如果未访问此节点
  • 创建一个新的空节点集,即当前组件
  • 将此节点排入队列以进行遍历
  • 虽然有任何节点t入队
    • 从队列中删除此节点
    • 将每个未访问的邻居标记为开放并将其排入队列进行遍历
    • 将此节点标记为已遍历
    • 将此节点添加到当前组件
  • 关闭当前组件,并将其添加到组件集中

如果只有一个组件,则图表已连接.

如果使用队列,则算法是广度优先搜索.如果使用堆栈,则算法是深度优先搜索.使用push和pop-any操作的任何其他集合都可以.特别感兴趣的是call-stack:将"enqueue for traversal"替换为"递归遍历"

对于有向图,有两个相关的概念:如果连接忽略所有边缘方向,则有向图是弱连接的.如果每个节点都可以从每个节点到达,则有向图是强连接的.为了测试强连接性,仅使用前向边缘检查每个节点是否可从第一节点到达,并且仅使用向后边缘从第一节点可到达每个节点(第一节点可从每个节点到达).

1. 二部

如果它是双重的,则图是二分的.尝试分配双色,如果失败,图表不是二分图.这可以合并到以前的算法中:每当您将节点标记为打开时,为其指定一种颜色,与分配给其邻居的颜色相反t.当邻居t已经打开时,检查其颜色.如果它的颜色与它的颜色相同t,则没有双色.

1. 有周期

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

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

• 虽然有一个零度为indegree的节点
  • 将节点添加到拓扑排序(与检测周期无关)
  • 从图中删除节点
• 如果图中仍有任何节点
  • 该图包含有向循环.该图表上不存在拓扑排序
• 其他
  • 该图不包含有向循环(非循环).生成的拓扑排序有效.

1. 树

如果它是连接的并且不包含循环,则无向图是树.

有向图是根树,如果它没有无向循环,并且只有一个顶点具有零度(只有一个根).此外,有向图是根树,如果它是连接的,没有无向循环,并且具有零度的零的每个节点具有至多一个的indegree(每个接收器是叶子).