algorithm - 图算法判断图是否连通、二分、有环且是树

Question

当我尝试使用图表并为其编写一些代码但没有成功时，我遇到了一个问题:/!!

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

所以我想知道，例如，是否可以将其写入以从将执行上述测试的 .txt 文件中读取图形数据？？

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

如果您能给我一个链接以阅读有关如何完成此任务或快速启动代码的链接，我们将不胜感激!

谢谢:D

Answer 1

check if it is:

1. connected

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

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

如果只有一个分量，则图是连通的。

如果使用队列，算法就是广度优先搜索。如果使用堆栈，则该算法是深度优先搜索。任何其他具有 push 和 pop-any 操作的集合都可以。特别感兴趣的是调用堆栈:将“遍历排队”替换为“递归遍历”

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

1. bipartite

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

1. has cycle

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

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

• 当存在入度为零的节点时
  • 将节点添加到拓扑排序中(与检测循环无关)
  • 从图中删除节点
• 如果图中还有节点
  • 该图包含有向环。该图上不存在拓扑排序
• 其他
  • 该图不包含有向循环(是非循环的)。生成的拓扑排序有效。

1. tree

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

有向图是一棵有根树，当且仅当它没有无向环且只有一个入度为零的顶点(只有一个根)。此外，有向图是有根树，前提是它是连通的，没有无向环，并且出度为零的每个节点的入度至多为一(每个汇都是叶子)。