找出图中的最短环

Question

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

我的图是 (A,B,C,D)，元素之间的连接（弧）是：

(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。

程序应该打印出最短的循环，即A->A。要解决它，我需要首先找到所有循环，然后将它们分别放在一个单独的列表中，最后带来最小的列表，这将是最短的循环（A-> A），但我不知道如何实现它。目前我在元素之间建立了连接（弧线）。

这是我的代码：

#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;

}

这是我的示例图：graph

Answer 1

如果您正在寻找一个完整的答案，那么只需查看其他答案 - 关于所用算法的问题有很多，我还找到了一个答案，代码移植到许多不同的编程语言（Cpp 版本也是那里）

Algorithm explanation
C++ version

不过，我强烈建议您查看算法并在此处实现它们，而不要删除已编写的代码。最好自己写，然后复制过去 - 你会学到更多 ;)

如果您需要任何更精确的帮助，请写下您的当前状态，我们会看到。

找出图中的最短环

Find the Shortest Cycle in Graph

c++

graph

cycle

circuit

shortest