原文:
给定一个无向图，打印其中形成圈的所有顶点。 先决条件:
在上图中，循环用深绿色标记。以上输出将为
第一周期:3 5 4 6 t3】第二周期: 11 12 13
方法:使用，用唯一的数字标记不同循环的所有顶点。一旦图遍历完成，将所有相似的标记数字推送到邻接表，并相应地打印邻接表。下面给出了算法:
- 将边插入邻接表。
- 调用使用着色方法标记顶点的 dfs 函数。
- 每当有一个部分访问的顶点时，回溯直到到达当前顶点，并用循环号标记所有顶点。标记所有顶点后，增加循环数。
- 一旦完成 dfs，迭代边，并将相同标记数的边推到另一个邻接表。
- 在另一个邻接表中迭代，并按循环数打印顶点。
以下是上述方法的实现:
c
// c program to print all the cycles
// in an undirected graph
#include
using namespace std;
const int n = 100000;
// variables to be used
// in both functions
vector graph[n];
vector cycles[n];
// function to mark the vertex with
// different colors for different cycles
void dfs_cycle(int u, int p, int color[],
int mark[], int par[], int& cyclenumber)
{
// already (completely) visited vertex.
if (color[u] == 2) {
return;
}
// seen vertex, but was not completely visited -> cycle detected.
// backtrack based on parents to find the complete cycle.
if (color[u] == 1) {
cyclenumber ;
int cur = p;
mark[cur] = cyclenumber;
// backtrack the vertex which are
// in the current cycle thats found
while (cur != u) {
cur = par[cur];
mark[cur] = cyclenumber;
}
return;
}
par[u] = p;
// partially visited.
color[u] = 1;
// simple dfs on graph
for (int v : graph[u]) {
// if it has not been visited previously
if (v == par[u]) {
continue;
}
dfs_cycle(v, u, color, mark, par, cyclenumber);
}
// completely visited.
color[u] = 2;
}
// add the edges to the graph
void addedge(int u, int v)
{
graph[u].push_back(v);
graph[v].push_back(u);
}
// function to print the cycles
void printcycles(int edges, int mark[], int& cyclenumber)
{
// push the edges that into the
// cycle adjacency list
for (int i = 1; i <= edges; i ) {
if (mark[i] != 0)
cycles[mark[i]].push_back(i);
}
// print all the vertex with same cycle
for (int i = 1; i <= cyclenumber; i ) {
// print the i-th cycle
cout << "cycle number " << i << ": ";
for (int x : cycles[i])
cout << x << " ";
cout << endl;
}
}
// driver code
int main()
{
// add edges
addedge(1, 2);
addedge(2, 3);
addedge(3, 4);
addedge(4, 6);
addedge(4, 7);
addedge(5, 6);
addedge(3, 5);
addedge(7, 8);
addedge(6, 10);
addedge(5, 9);
addedge(10, 11);
addedge(11, 12);
addedge(11, 13);
addedge(12, 13);
// arrays required to color the
// graph, store the parent of node
int color[n];
int par[n];
// mark with unique numbers
int mark[n];
// store the numbers of cycle
int cyclenumber = 0;
int edges = 13;
// call dfs to mark the cycles
dfs_cycle(1, 0, color, mark, par, cyclenumber);
// function to print the cycles
printcycles(edges, mark, cyclenumber);
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all the cycles
// in an undirected graph
import java.util.*;
class gfg
{
static final int n = 100000;
// variables to be used
// in both functions
@suppresswarnings("unchecked")
static vector[] graph = new vector[n];
@suppresswarnings("unchecked")
static vector[] cycles = new vector[n];
static int cyclenumber;
// function to mark the vertex with
// different colors for different cycles
static void dfs_cycle(int u, int p, int[] color,
int[] mark, int[] par)
{
// already (completely) visited vertex.
if (color[u] == 2)
{
return;
}
// seen vertex, but was not completely visited -> cycle detected.
// backtrack based on parents to find the complete cycle.
if (color[u] == 1)
{
cyclenumber ;
int cur = p;
mark[cur] = cyclenumber;
// backtrack the vertex which are
// in the current cycle thats found
while (cur != u)
{
cur = par[cur];
mark[cur] = cyclenumber;
}
return;
}
par[u] = p;
// partially visited.
color[u] = 1;
// simple dfs on graph
for (int v : graph[u])
{
// if it has not been visited previously
if (v == par[u])
{
continue;
}
dfs_cycle(v, u, color, mark, par);
}
// completely visited.
color[u] = 2;
}
// add the edges to the graph
static void addedge(int u, int v)
{
graph[u].add(v);
graph[v].add(u);
}
// function to print the cycles
static void printcycles(int edges, int mark[])
{
// push the edges that into the
// cycle adjacency list
for (int i = 1; i <= edges; i )
{
if (mark[i] != 0)
cycles[mark[i]].add(i);
}
// print all the vertex with same cycle
for (int i = 1; i <= cyclenumber; i )
{
// print the i-th cycle
system.out.printf("cycle number %d: ", i);
for (int x : cycles[i])
system.out.printf("%d ", x);
system.out.println();
}
}
// driver code
public static void main(string[] args)
{
for (int i = 0; i < n; i )
{
graph[i] = new vector<>();
cycles[i] = new vector<>();
}
// add edges
addedge(1, 2);
addedge(2, 3);
addedge(3, 4);
addedge(4, 6);
addedge(4, 7);
addedge(5, 6);
addedge(3, 5);
addedge(7, 8);
addedge(6, 10);
addedge(5, 9);
addedge(10, 11);
addedge(11, 12);
addedge(11, 13);
addedge(12, 13);
// arrays required to color the
// graph, store the parent of node
int[] color = new int[n];
int[] par = new int[n];
// mark with unique numbers
int[] mark = new int[n];
// store the numbers of cycle
cyclenumber = 0;
int edges = 13;
// call dfs to mark the cycles
dfs_cycle(1, 0, color, mark, par);
// function to print the cycles
printcycles(edges, mark);
}
}
// this code is contributed by
// sanjeev2552
python 3
# python3 program to print all the cycles
# in an undirected graph
n = 100000
# variables to be used
# in both functions
graph = [[] for i in range(n)]
cycles = [[] for i in range(n)]
# function to mark the vertex with
# different colors for different cycles
def dfs_cycle(u, p, color: list,
mark: list, par: list):
global cyclenumber
# already (completely) visited vertex.
if color[u] == 2:
return
# seen vertex, but was not
# completely visited -> cycle detected.
# backtrack based on parents to
# find the complete cycle.
if color[u] == 1:
cyclenumber = 1
cur = p
mark[cur] = cyclenumber
# backtrack the vertex which are
# in the current cycle thats found
while cur != u:
cur = par[cur]
mark[cur] = cyclenumber
return
par[u] = p
# partially visited.
color[u] = 1
# simple dfs on graph
for v in graph[u]:
# if it has not been visited previously
if v == par[u]:
continue
dfs_cycle(v, u, color, mark, par)
# completely visited.
color[u] = 2
# add the edges to the graph
def addedge(u, v):
graph[u].append(v)
graph[v].append(u)
# function to print the cycles
def printcycles(edges, mark: list):
# push the edges that into the
# cycle adjacency list
for i in range(1, edges 1):
if mark[i] != 0:
cycles[mark[i]].append(i)
# print all the vertex with same cycle
for i in range(1, cyclenumber 1):
# print the i-th cycle
print("cycle number %d:" % i, end = " ")
for x in cycles[i]:
print(x, end = " ")
print()
# driver code
if __name__ == "__main__":
# add edges
addedge(1, 2)
addedge(2, 3)
addedge(3, 4)
addedge(4, 6)
addedge(4, 7)
addedge(5, 6)
addedge(3, 5)
addedge(7, 8)
addedge(6, 10)
addedge(5, 9)
addedge(10, 11)
addedge(11, 12)
addedge(11, 13)
addedge(12, 13)
# arrays required to color the
# graph, store the parent of node
color = [0] * n
par = [0] * n
# mark with unique numbers
mark = [0] * n
# store the numbers of cycle
cyclenumber = 0
edges = 13
# call dfs to mark the cycles
dfs_cycle(1, 0, color, mark, par)
# function to print the cycles
printcycles(edges, mark)
# this code is contributed by
# sanjeev2552
c
// c# program to print all
// the cycles in an undirected
// graph
using system;
using system.collections.generic;
class gfg{
static readonly int n = 100000;
// variables to be used
// in both functions
static list[] graph =
new list[n];
static list[] cycles =
new list[n];
static int cyclenumber;
// function to mark the vertex with
// different colors for different cycles
static void dfs_cycle(int u, int p,
int[] color,
int[] mark,
int[] par)
{
// already (completely)
// visited vertex.
if (color[u] == 2)
{
return;
}
// seen vertex, but was not
// completely visited -> cycle
// detected. backtrack based on
// parents to find the complete
// cycle.
if (color[u] == 1)
{
cyclenumber ;
int cur = p;
mark[cur] = cyclenumber;
// backtrack the vertex which
// are in the current cycle
// thats found
while (cur != u)
{
cur = par[cur];
mark[cur] = cyclenumber;
}
return;
}
par[u] = p;
// partially visited.
color[u] = 1;
// simple dfs on graph
foreach (int v in graph[u])
{
// if it has not been
// visited previously
if (v == par[u])
{
continue;
}
dfs_cycle(v, u, color,
mark, par);
}
// completely visited.
color[u] = 2;
}
// add the edges to the
// graph
static void addedge(int u,
int v)
{
graph[u].add(v);
graph[v].add(u);
}
// function to print the cycles
static void printcycles(int edges,
int []mark)
{
// push the edges that into the
// cycle adjacency list
for (int i = 1; i <= edges; i )
{
if (mark[i] != 0)
cycles[mark[i]].add(i);
}
// print all the vertex with
// same cycle
for (int i = 1;
i <= cyclenumber; i )
{
// print the i-th cycle
console.write("cycle number " i ":");
foreach (int x in cycles[i])
console.write(" " x);
console.writeline();
}
}
// driver code
public static void main(string[] args)
{
for (int i = 0; i < n; i )
{
graph[i] = new list();
cycles[i] = new list();
}
// add edges
addedge(1, 2);
addedge(2, 3);
addedge(3, 4);
addedge(4, 6);
addedge(4, 7);
addedge(5, 6);
addedge(3, 5);
addedge(7, 8);
addedge(6, 10);
addedge(5, 9);
addedge(10, 11);
addedge(11, 12);
addedge(11, 13);
addedge(12, 13);
// arrays required to color
// the graph, store the parent
// of node
int[] color = new int[n];
int[] par = new int[n];
// mark with unique numbers
int[] mark = new int[n];
// store the numbers of cycle
cyclenumber = 0;
int edges = 13;
// call dfs to mark
// the cycles
dfs_cycle(1, 0, color,
mark, par);
// function to print the cycles
printcycles(edges, mark);
}
}
// this code is contributed by amit katiyar
java 描述语言
输出:
cycle number 1: 3 4 5 6
cycle number 2: 11 12 13
时间复杂度: o(n m)，其中 n 为顶点数，m 为边数。 辅助空间: o(n m)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
