9

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

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

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

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

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

感谢：D

4

1 回答 1

25

检查是否是：

  1. 连接的

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

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

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

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

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

  1. 双方

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

  1. 有循环

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

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

  • 而有一个入度为零的节点
    • 将节点添加到拓扑排序（与检测循环无关）
    • 从图中删除节点
  • 如果图中还有节点
    • 该图包含有向循环。该图上不存在拓扑排序
  • 别的
    • 该图不包含有向循环（是非循环的）。生成的拓扑排序是有效的。
  1. 树

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

有向图是一棵有根树，当且仅当它没有无向环并且只有一个入度为零的顶点（只有一个根）。此外，有向图是一棵有根树，如果它是连通的，没有无向环，并且每个出度为零的节点的入度最多为 1（每个接收器都是叶子）。

于 2013-03-13T19:49:10.227 回答