在无向图中找到强连接的组件

本文介绍了在无向图中找到强连接的组件的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想在无向图中找到一个紧密连接的组件，即，如果我从节点A开始，那么我将回到节点A，并且每个边缘都将被精确访问一次.

I want to find a strongly connected components in undirected graph i.e If i start from a Node A then i will get back to node A and each edge is visited exactly by once.

对于有向图，可以使用Tarjan的算法来查找强连接的组件，但如何对无向图进行处理.

For Directed Graph can use Tarjan’s algorithm for finding the strongly connected components , but how to do for undirected graph.

推荐答案

我认为您想念了解强连接组件的含义.

I think you miss understood the meaning of strongly connected component.

牢固连接的组件

如果所有对顶点之间都有路径，则有向图是紧密连接的.有向图的强连接组件(SCC)是最大的强连接子图.

A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connectedsubgraph. 

但是，从您的定义到您要寻找的东西，我想说的是您想在无向图中找到循环:

But, from your definition to what your looking for, I'd say you want to find cycle in unDirected graph:

• 一次输入每个节点

• enters each node once

您可以从节点A开始，然后在节点A中结束.

you can start from node A and finish in node A.

如果这只是您要查找的内容，我会说使用Dfs算法在无向图中找到循环.

If it's only what you look for I'd say use Dfs algorithm to find cycle in unDirected graph.

希望我回答了您的问题