在图中找到最短周期 [英] Find the Shortest Cycle in Graph
问题描述
我在查找图中的周期时遇到问题.在这种情况下，我们必须在有向图中找到最短的周期.
I have a problem with finding cycles in graph. In the condition we have to find the shortest cycle in directed graph.
我的图是(A，B，C，D)，元素之间的连接(弧)是:
My graph is (A,B,C,D) and the connections (arcs) between the elements are:
(A-> B)，(A-> A)，(B-> C)，(B-> A)，(C-> D)，(C-> A)，(D-> A )
(A->B), (A->A), (B->C), (B->A), (C->D), (C->A), (D->A)
，因此周期如下:
А-> B-> C-> D-> A; A-> B-> C-> A; A-> B-> A; A-> A.
А->B->C->D->A; A->B->C->A; A->B->A; A->A.
程序应打印最短的周期，即A-> A.为了解决这个问题，我需要首先找到所有循环，然后将它们分别放在一个单独的列表中，最后带出最小的列表，这将是最短的循环(A-> A)，但我不知道如何实现.此刻，我在元素之间建立了连接(弧).
Program should print the shortest cycle, ie A->A. To solve it i need first to find all cycles, then put them each in a separate list and finally bring the smallest list, which will be the shortest cycle (A-> A), but I do not know how to realize it. At the moment I made connections (arcs) between elements.
这是我的代码:
#include <iostream>
using namespace std;
const int N = 10;
struct elem
{
char key;
elem *next;
} *g1[N];
void init(elem *g[N])
{
for (int i = 0; i < N; i++)
g[i] = NULL;
}
int search_node(char c, elem *g[N])
{
for (int i = 0; i < N; i++)
if (g[i])
if (g[i]->key == c)
{
return 1;
}
return 0;
}
int search_arc(char from, char to, elem *g[N])
{
if (search_node(from, g) && search_node(to, g))
{
int i = 0;
while (g[i]->key != from) i++;
elem *p = g[i]->next;
while (true)
{
if (p == NULL)
{
break;
}
if (p->key == to)
{
return 1;
}
p = p->next;
}
}
return 0;
}
void add_node(char c, elem *g[N])
{
if (search_node(c, g))
cout << "Node already exists.\n";
int i = 0;
while (g[i] && (i < N)) i++;
if (g[i] == NULL)
{
g[i] = new elem;
g[i]->key = c;
g[i]->next = NULL;
}
else
{
cout << "Maximum nodes reached.\n";
}
}
void add_arc(char from, char to, elem *g[N])
{
if (search_arc(from, to, g))
cout << "Arc already exists.\n";
else
{
if (!search_node(from, g))
add_node(from, g);
if (!search_node(to, g))
add_node(to, g);
int i = 0;
while (g[i]->key != from) i++;
elem *p = new elem;
p->key = to;
p->next = g[i]->next;
g[i]->next = p;
}
}
void print(elem *g[N])
{
for (int i = 0; i < N; i++)
{
if (g[i] != NULL)
{
elem *p = g[i];
while (p)
{
cout << p->key << "\t";
p = p->next;
}
cout << endl;
}
}
}
void iscycle(elem *g[N])
{
}
int main()
{
system ("cls");
cout << "init: " << endl;
init(g1);
cout << "graph 1: " << endl;
add_arc('a', 'b', g1);
add_arc('a', 'a', g1);
add_arc('b', 'c', g1);
add_arc('b', 'a', g1);
add_arc('c', 'a', g1);
add_arc('c', 'd', g1);
add_arc('d', 'a', g1);
print(g1);
cout << "cycles: ";
iscycle(g1);
system("pause");
return 0;
}
这是我的示例图形图片:图形
This is my example graph picture: graph
推荐答案
如果您正在寻找一个完整的答案，那么只需检查其他答案即可-关于使用的算法有很多问题，我也找到了答案代码移植到许多不同的编程语言(也有Cpp版本)
算法说明
C ++版本
If You're looking for a complete answer, then just check other answers - there are tons of questions regarding used algorithms and I've also found an answer with code ported to many different programming languages (Cpp version is also there)
Algorithm explanation
C++ version
不过，我强烈建议您在不删除已经编写的代码的情况下查看算法并在此处实现它们.最好自己写，然后复制过去-您会学到更多；)
I'd strongly recommend though, that You take a look at algorithms and implement them here, without removing already written code. It's much better to write it yourself, then just copy-past - You'll learn a lot more ;)
如果您需要任何更精确的帮助，请写上您的当前状态&我们会看到的.
If You need any more precise help, write Your current status & we'll see.
这篇关于在图中找到最短周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
