title: Find the Shortest Cycle in Graph
body: <p>I have a problem with finding cycles in graph. In the condition we have to find the shortest cycle in directed graph.</p>
  
  <p>My graph is (A,B,C,D) and the connections (arcs) between the elements are:</p>
  
  <p>(A->B), (A->A), (B->C), (B->A), (C->D), (C->A), (D->A) </p>
  
  <p>and so cycles are the following: </p>
  
  <p>А->B->C->D->A; A->B->C->A; A->B->A; A->A. </p>
  
  <p>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.</p>
  
  <p>This is my code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  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 &lt; N; i++)
          g[i] = NULL;
  }
  
  int search_node(char c, elem *g[N])
  {
      for (int i = 0; i &lt; N; i++)
          if (g[i])
              if (g[i]-&gt;key == c)
              {
                  return 1;
              }
  
      return 0;
  }
  
  int search_arc(char from, char to, elem *g[N])
  {
      if (search_node(from, g) &amp;&amp; search_node(to, g))
      {
          int i = 0;
  
          while (g[i]-&gt;key != from) i++;
  
          elem *p = g[i]-&gt;next;
  
          while (true)
          {
              if (p == NULL)
              {
                  break;
              }
  
              if (p-&gt;key == to)
              {
                  return 1;
              }
  
              p = p-&gt;next;
          }
      }
  
      return 0;
  }
  
  void add_node(char c, elem *g[N])
  {
      if (search_node(c, g))
          cout &lt;&lt; "Node already exists.\n";
  
      int i = 0;
      while (g[i] &amp;&amp; (i &lt; N)) i++;
  
      if (g[i] == NULL)
      {
          g[i] = new elem;
          g[i]-&gt;key = c;
          g[i]-&gt;next = NULL;
      }
      else
      {
          cout &lt;&lt; "Maximum nodes reached.\n";
      }
  }
  
  void add_arc(char from, char to, elem *g[N])
  {
      if (search_arc(from, to, g))
          cout &lt;&lt; "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]-&gt;key != from) i++;
  
          elem *p = new elem;
          p-&gt;key = to;
          p-&gt;next = g[i]-&gt;next;
  
          g[i]-&gt;next = p;
      }
  }
  
  void print(elem *g[N])
  {
      for (int i = 0; i &lt; N; i++)
      {
          if (g[i] != NULL)
          {
              elem *p = g[i];
  
              while (p)
              {
                  cout &lt;&lt; p-&gt;key &lt;&lt; "\t";
                  p = p-&gt;next;
              }
  
              cout &lt;&lt; endl;
          }
      }
  }
  
  
  void iscycle(elem *g[N])
  {
  
  }
  
  int main()
  {
      system ("cls");
  
      cout &lt;&lt; "init: " &lt;&lt; endl;
      init(g1);
  
      cout &lt;&lt; "graph 1: " &lt;&lt; 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 &lt;&lt; "cycles: ";
      iscycle(g1);
  
      system("pause");
      return 0;
  
  }
  </code></pre>
  
  <p>This is my example graph picture: <a href="https://drive.google.com/file/d/0B7njExdlco7OWnRDa28zOV9zMWs/view?usp=sharing" rel="nofollow">graph</a></p>