c++ - Find the Shortest Cycle in Graph -

i have problem finding cycles in graph. in condition have find shortest cycle in directed graph.

my graph (a,b,c,d) , connections (arcs) between elements are:

(a->b), (a->a), (b->c), (b->a), (c->d), (c->a), (d->a)

and cycles following:

А->b->c->d->a; a->b->c->a; a->b->a; a->a.

program should print shortest cycle, ie a->a. solve need first find cycles, put them each in separate list , bring smallest list, shortest cycle (a-> a), not know how realize it. @ moment made connections (arcs) between elements.

this code:

#include <iostream>  using namespace std;  const int n = 10;  struct elem {     char key;     elem *next;  } *g1[n];  void init(elem *g[n]) {     (int = 0; < n; i++)         g[i] = null; }  int search_node(char c, elem *g[n]) {     (int = 0; < 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 = 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 exists.\n";      int = 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 exists.\n";     else     {         if (!search_node(from, g))             add_node(from, g);          if (!search_node(to, g))             add_node(to, g);          int = 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]) {     (int = 0; < 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 example graph picture: graph

if you're looking complete answer, check other answers - there tons of questions regarding used algorithms , i've found answer code ported many different programming languages (cpp version there)

algorithm explanation
c++ version

i'd recommend though, take @ algorithms , implement them here, without removing written code. it's better write yourself, copy-past - you'll learn lot more ;)

if need more precise help, write current status & we'll see.