-3

グラフでサイクルを見つけるのに問題があります。この状態では、有向グラフで最短のサイクルを見つける必要があります。

私のグラフは（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;

}

これは私の例のグラフ画像です:グラフ

4

1 に答える 1

0

完全な回答を探している場合は、他の回答を確認してください-使用されているアルゴリズムに関する質問がたくさんあり、多くの異なるプログラミング言語に移植されたコードを含む回答も見つけました（Cppバージョンもあります）

アルゴリズムの説明
C ++バージョン


ただし、既に作成されたコードを削除せずに、アルゴリズムを見て、ここで実装することを強くお勧めします。自分で書いたほうがずっといいです。

さらに正確なサポートが必要な場合は、現在のステータスを記入してください。

于 2015-06-03T09:11:12.387 に答える