当我试图使用图形并为其编写一些代码时,我遇到了一个问题:/ !!
我想要创建一些东西来获取图表的数据,并检查它是否是: 1-连通的2-二分3-有循环4-是一棵树。
因此,我想知道,例如,是否可以将其写入从.txt文件中读取图形数据,以便进行上述测试??
使用简单的边缘列表格式是正确的方法吗?
如果你能给我一个链接来阅读如何完成这个任务,或者代码的启动!!
谢谢:D
发布于 2013-03-13 19:49:10
检查是否是:
对于这一个,你试着从一个点遍历整个图,看看你是否成功。深度优先遍历和宽度优先遍历在这里都是可以接受的.此算法将将节点拆分为组件:
c,如果此节点未被访问,则为t排队的
- close the current component, and add it to the set of components
如果只有一个组件,则图是连通的。
如果使用队列,则该算法是宽度优先搜索。如果使用堆栈,则该算法是深度优先搜索.任何其他集合与推送和弹出-任何操作都可以。特别令人感兴趣的是调用堆栈:将“遍历队列”替换为“递归遍历”。
对于有向图,有向图有两个相关的概念:有向图是弱连通的当且仅当它是连通的,忽略了所有的边方向。有向图是强连通的当且仅当每个节点都可以从每个节点到达。为了测试强连通性,只需使用前向边缘检查每个节点是否可从第一个节点到达,而从第一个节点仅使用向后边缘即可到达每个节点(第一个节点可从每个节点到达)。
图是二分的当且仅当它是双色的。尝试分配双色,如果失败,则图不是二分图。这可以合并到前面的算法中:每当您将节点标记为打开时,为其分配颜色,与分配给其邻居t的颜色相反。当t的邻居已经打开时,检查它的颜色。如果其颜色与t相同,则不存在双色。
这一点很简单:如果您观察到任何已经打开的节点,就会有一个循环。请注意,每个没有圈的图都是二分图。
在有向图中,这将检测无向循环的存在。要检测有向循环的存在,请使用以下(拓扑排序)算法:
无向图是一棵树当且仅当它是连通的且不包含循环。
有向图是根树当且仅当它没有无向圈,并且只有一个索引为零的顶点(只有一个根)。另外,有向图是根树当且仅当它是连通的,没有无向循环,并且每一个输出度为零的节点最多有一个索引(每个接收器都是一片叶子)。
https://stackoverflow.com/questions/15394254
复制相似问题