图算法查找图是否连通、二部、有环并且是一棵树 [英] graph algorithm finding if graph is connected, bipartite, has cycle and is a tree

问题描述

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

我想创建一些东西来获取图表数据并检查它是否:1-已连接2- 双方3-有周期4-是一棵树

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

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

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

谢谢:D

解决方案

检查是否是:

1. 已连接

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

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

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

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

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

<块引用>

1. 双方

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

<块引用>

1. 有循环

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

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

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

<块引用>

1. 树

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

有向图是一棵有根树，如果它没有无向环并且只有一个入度为零的顶点(只有一个根).此外，有向图是一棵有根树，如果它是连通的，没有无向环，并且每个出度为 0 的节点的入度至多为 1(每个汇都是一个叶子).

I came to a problem when I was trying to work with graphs and write some code for it but with no luck :/ !!

I wanted to created something that will take the data of the graph and check if it is: 1- connected 2- bipartite 3- has cycle 4- is a tree

so I was wondering for example if this can be written to read a graph data from a .txt file that will do the above tests ??

using simple edge-list format is the correct approach for it ?

your help is appreciated if you can give me a link to read about how to do this task or a kick start for a code !!

thanks :D

解决方案

check if it is:

1. connected

For this one, you try to traverse the entire graph from one point, and see if you succeed. Both depth-first traversal and breadth-first traversal are acceptable here. This algorithm will split the node into components:

• mark all nodes as unvisited
• for every node c, if this node is unvisited
  • create a new empty set of nodes, the current component
  • enqueue the this node for traversal
  • while there is any node t enqueued
    • remove this node from the queue
    • mark every unvisited neighbor as open and enqueue it for traversal
    • mark this node as traversed
    • add this node to the current component
  • close the current component, and add it to the set of components

If there is only one component, the graph is connected.

If a queue is used, the algorithm is a breadth-first search. If a stack is used, the algorithm is a depth-first search. Any other collection with the push and pop-any operations will do. Of special interest is the call-stack: replace "enqueue for traversal" with "traverse recursively"

For directed graphs, there are two related concepts: A directed graph is weakly connected iff it is connected neglecting all edge directions. A directed graph is strongly connected iff every node is reachable from every node. To test for strong connectedness it sufficces to check every node is reachable from the first node using only forward edges, and every node is reachable from the first node using only backwards edges (the first node is reachable from every node).

1. bipartite

A graph is bipartite iff it is bicolorable. Try to assign a bicoloring, and if you fail, the graph is not bipartite. This can be incorporated into the previous algorithm: Whenever you mark a node as open, assign a color to it, opposite to the color assigned to its neighbor t. When a neighbor of t is already open, check its color. If its color is the same as that of t, there is no bicoloring.

1. has cycle

This one is easy: If you observe any node that is already open, there is a cycle. Note that every graph that has no cycle is bipartite.

In directed graphs, this will detect the presence of an undirected cycle. To detect the presence of directed cycles, use the following (topological sort) algorithm:

• while there is a node with the indegree of zero
  • add the node to the topological sort (irrelevant for detecting cycles)
  • remove the node from the graph
• if there is still any node in the graph
  • the graph contains a directed cycle. No topological sort exists on that graph
• else
  • the graph does not contain a directed cycle (is acyclic). The topological sort generated is valid.

1. tree

An undirected graph is a tree iff it is connected and contains no cycle.

A directed graph is a rooted tree iff it has no undirected cycles and there is only one vertex with an indegree of zero (only one root). Also, a directed graph is a rooted tree iff it is connected, has no undirected cycles and every node with an outdegree of zero has an indegree of at most one (every sink is a leaf).

这篇关于图算法查找图是否连通、二部、有环并且是一棵树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！