C++ Program to Find the Shortest Cycle in a Graph

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;

}


Output:

Execute and get the output.


More C++ Programs: