在图中找到最短周期

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

我在查找图中的周期时遇到问题.在这种情况下，我们必须在有向图中找到最短的周期.

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.