图算法发现，如果图是连通的，二部，具有周期是一棵树 [英] graph algorithm finding if graph is connected, bipartite, has cycle and is a tree

问题描述

我来当我试图用图形来工作，写一些$ C $下它，但没有运气的问题：/ !!

我想创造的东西，将图形的数据，并检查它是否是： 1-连接 2-二部 3具有周期 4-是一棵树

所以我想知道，例如，如果这可以被写入读取一个txt文件，将做上述试验??图形数据。

使用简单的边列表格式是正确的做法呢？

您的帮助是AP preciated如果你可以给我一个链接阅读有关如何执行此任务或踢开始为code！

感谢：D

解决方案

  

检查，如果它是：

     

  
1. 连接
  

有关这一个，你试图从一个点遍历整个图，看看你成功。无论深度优先遍历和广度优先遍历是可以接受的位置。该算法将节点分成部分：

• 标记所有节点为未访问
• 为每个节点 C ，如果此节点为未访问过
  • 创建一个新的空组节点，当前组件
  • 在排队的这一节点遍历
  • 而有任何节点 T 入队
    • 从队列中删除这个节点
    • 标记每一个未访问过的邻居开放和排队它遍历
    • 标记这个节点作为遍历
    • 在这个节点添加到当前组件
  • 关闭电流分量，并把它添加到组件集合

如果只有一个部件，该图是连通的。

如果一个队列时，该算法是一种广度优先搜索。如果堆叠的情况下，该算法是一个深度优先搜索。任何其他集合与push和pop-任何操作就可以了。特别有趣的是调用堆栈：将排队等待穿越与递归遍历

有关向图，有两个相关的概念：一个有向图是弱连接当且仅当它连接忽略所有的边缘方向。有向图是强连通的当且仅当每一个节点是从每个节点访问。测试对于强连通它sufficces检查每一个节点是从第一节点可到达的仅使用前向边缘，并且每一个节点仅使用向后边缘从第一节点是可达的（第一节点是可达的从每一个节点）。

  

  
1. 二部
  

一个图是二部图当且仅当它是bicolorable。尝试指派bicoloring，如果你失败了，图不是二分。这可以被纳入previous算法：当你标记一个节点开放，颜色分配给它，相反的颜色分配给它的邻居 T 。当 T 邻居已经打开，检查其颜色。如果它的颜色是一样的 T 的，没有bicoloring。

  

  
1. 有周期
  

这一种方法比较简单：如果你观察到的任意的节点已经打开，有一个周期。需要注意的是，有没有周期的每一个图是二分。

在向图，这将检测无向循环的presence。为了检测向圈的presence，请使用以下（拓扑排序）算法：

• ，而没有与零入度的节​​点
  • 节点添加到拓扑排序（不相关的检测周期）
  • 从图中删除节点
• 如果还有图中的任何节点
  • 在图形中包含有向循环。存在于该图
  无拓扑排序
• 其他
  • 在图形中不包含有向循环（是非周期性）。生成的拓扑排序是有效的。

  

  
1. 在树
  

这是无向图是树当且仅当它连接，并且不包含循环。

一个有向图是有根树当且仅当它没有无向周期，只有一条为零（只有一个根）的入度顶点。此外，向图是一个根树当且仅当它被连接，没有无向周期和以零出度每个节点具有至多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屋！