一、无向无权连通图

给定一个无向无权连通图，在该图中找到一个简单的环（如果存在）。

简单循环：

简单循环是图中没有重复顶点的循环（起点和终点顶点除外）。

基本上，如果一个周期不能分解为两个或两个以上的周期，那么它就是一个简单的周期。

方法：目的是检查图表是否包含循环。这可以通过简单地使用DFS来完成。

现在，如果图包含一个循环，我们可以从DFS本身获得该循环的端点（例如a和b）。现在，如果我们从a到b运行BFS（忽略a和b之间的直接边），我们将能够获得从a到b的最短路径，这将为我们提供包含点a和点b的最短循环的路径。通过使用父数组可以轻松跟踪路径。这个最短的周期将是一个简单的周期。

证明最短周期为简单周期的证明：

我们可以用矛盾来证明这一点。假设在这个循环中存在另一个简单的循环。这意味着内部简单循环的长度将更短，因此可以说从a到b的路径更短。但我们已经使用BFS找到了从a到b的最短路径。因此，不存在较短的路径，找到的路径是最短的。所以，在我们发现的周期内，不可能存在任何内部周期。

 

此数据结构仅完成未加权图规范，不定义进一步的操作。作为一个完整的实现，它必须决定如何在其中存储顶点。选项与存储边时使用的选项相同：

实现顶点列表的动态数组：迭代速度非常快，搜索值/顶点速度非常慢。如果顶点内的值不唯一，则使用！如果使用，边缘必须使用相同的存储选项。

实现顶点集的哈希表：迭代速度非常快，搜索值/顶点速度非常快。如果顶点内的值唯一，则使用！如果使用，边缘必须使用相同的存储选项。

二、图术语汇编

术语汇编下面是我们使用的一些定义。

自循环是将顶点连接到自身的边。

如果两条边连接同一对顶点，则它们是平行的。

当一条边连接两个顶点时，我们说这些顶点彼此相邻，并且该边关联在两个顶点上。

顶点的阶数是其上关联的边数。

子图是构成图的图的边（和相关顶点）的子集。

图中的路径是由边连接的顶点序列，没有重复的边。

简单路径是没有重复顶点的路径。

循环是第一个顶点和最后一个顶点相同的路径（至少有一条边）。

简单循环是没有重复顶点的循环（第一个和最后一个顶点的必要重复除外）。

路径或循环的长度是其边数。

如果存在一条包含两个顶点的路径，我们说一个顶点连接到另一个顶点。

如果有一条从每个顶点到其他每个顶点的路径，则图是连通的。

非连通图由一组连通分量组成，这些连通分量是最大连通子图。

无圈图是一个没有圈的图。

树是一个非循环连通图。

森林是一组不相交的树木。

连通图的生成树是包含该图所有顶点的子图，是一棵树。图的生成林是其连通部分的生成树的并集。

二分图是一个图，其顶点可以分为两个集，这样所有边都可以将一个集中的顶点与另一个集中的顶点连接起来。

 

参考：

C#，图（Graph）的数据结构设计与源代码https://blog.csdn.net/beijinghorn/article/details/125133711

源程序：

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
 
namespace Legalsoft.Truffer.Algorithm
{
	public partial class Graph
	{
		public bool Detect_Cycle(int node, int par, ref bool[] vis, out int start_node, out int end_node)
		{
			start_node = -1;
			end_node = -1;
 
			vis[node] = true;
 
			foreach (int child in Adjacency[node])
			{
				if (vis[child] == false)
				{
					if (Detect_Cycle(child, node, ref vis, out start_node, out end_node))
					{
						return true;
					}
				}
				else if (child != par)
				{
					start_node = child;
					end_node = node;
					return true;
				}
			}
			return false;
		}
 
		public List<int> Find_Simple_Cycle(int a, int b, ref bool[] vis)
		{
			List<int> simple_cycle = new List<int>();
			int[] par = new int[Int16.MaxValue];
 
			Queue<int> q = new Queue<int>();
 
			q.Enqueue(a);
			bool ok = true;
 
			while (q.Count != 0)
			{
				int node = q.Peek();
				q.Dequeue();
				vis[node] = true;
 
				foreach (int child in Adjacency[node])
				{
					if (node == a && child == b)
					{
						continue;
					}
 
					if (vis[child] == false)
					{
						par[child] = node;
 
						if (child == b)
						{
							ok = false;
							break;
						}
						q.Enqueue(child);
						vis[child] = true;
					}
				}
 
				if (ok == false)
				{
					break;
				}
			}
 
			simple_cycle.Add(a);
			int x = b;
 
			while (x != a && x > 0)
			{
				simple_cycle.Add(x);
				x = par[x];
			}
 
			return simple_cycle;
		}
	}
 
	public static partial class GraphDrives
	{
		public static string Simple_Cycle()
		{
			Graph g = new Graph(13);
			bool[] vis = new bool[Int16.MaxValue];
			g.AddEdge(1, 2);
			g.AddEdge(2, 3);
			g.AddEdge(3, 4);
			g.AddEdge(4, 6);
			g.AddEdge(4, 7);
			g.AddEdge(5, 6);
			g.AddEdge(3, 5);
			g.AddEdge(7, 8);
			g.AddEdge(6, 10);
			g.AddEdge(5, 9);
			g.AddEdge(10, 11);
			g.AddEdge(10, 13);
			g.AddEdge(11, 12);
			g.AddEdge(11, 13);
			g.AddEdge(12, 13);
 
			StringBuilder sb = new StringBuilder();
 
			if (g.Detect_Cycle(9, -1, ref vis, out int start_node, out int end_node) == true)
			{
				for (int i = 0; i < vis.Length; i++)
				{
					vis[i] = false;
				}
 
				List<int> simple_cycle = g.Find_Simple_Cycle(9, 10, ref vis);
 
				sb.AppendLine("A simple cycle: ");
 
				foreach (int node in simple_cycle)
				{
					sb.AppendLine(node + " => ");
				}
				sb.AppendLine(start_node + "");
				sb.AppendLine("<br><br>");
			}
			else
			{
				sb.AppendLine("The Graph doesn't contain a cycle j=9.<br>");
			}
 
			return sb.ToString();
		}
	}
}