-3

I have a problem with finding cycles in graph. In the condition we have to find the shortest cycle in directed graph.

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)

and so cycles are the following:

А->B->C->D->A; A->B->C->A; A->B->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.

This is my code:

#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

4

1 回答 1

0

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

算法解释
C++版本


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

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

于 2015-06-03T09:11:12.387 回答