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.
";
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.
";
}
}
void add_arc(char from, char to, elem *g[N])
{
if (search_arc(from, to, g))
cout << "Arc already exists.
";
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 << " ";
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
See Question&Answers more detail:
os