Cycle detection
#include <stdio.h>
#define MAXMUMSIZE 9
#define NONEXT -1
#define NOCYCLE 0
#define ISCYCLE 1
typedef struct _node{
int nNextNode;
int nPassCount;
int bCycle;
}node;
void InitNode(node *aNode)
{
aNode[0].nNextNode = NONEXT;
aNode[0].nPassCount = 0;
aNode[0].bCycle = NOCYCLE;
aNode[1].nNextNode = 2;
aNode[1].nPassCount = 0;
aNode[1].bCycle = NOCYCLE;
aNode[2].nNextNode = NONEXT;
aNode[2].nPassCount = 0;
aNode[2].bCycle = NOCYCLE;
aNode[3].nNextNode = 4;
aNode[3].nPassCount = 0;
aNode[3].bCycle = NOCYCLE;
aNode[4].nNextNode = 3;
aNode[4].nPassCount = 0;
aNode[4].bCycle = NOCYCLE;
aNode[5].nNextNode = 6;
aNode[5].nPassCount = 0;
aNode[5].bCycle = NOCYCLE;
aNode[6].nNextNode = 7;
aNode[6].nPassCount = 0;
aNode[6].bCycle = NOCYCLE;
aNode[7].nNextNode = 8;
aNode[7].nPassCount = 0;
aNode[7].bCycle = NOCYCLE;
aNode[8].nNextNode = 6;
aNode[8].nPassCount = 0;
aNode[8].bCycle = NOCYCLE;
}
void StartDetect(node *aNode, int nIndex)
{
if(NONEXT == aNode[nIndex].nNextNode)
return;
aNode[nIndex].nPassCount++;
if(aNode[nIndex].nPassCount > 1)
{
aNode[nIndex].bCycle = ISCYCLE;
return;
}
StartDetect(aNode, aNode[nIndex].nNextNode);
}
void Cycledetect(node *aNode)
{
int nIndex = 0;
for(nIndex = 0; nIndex < MAXMUMSIZE; nIndex++)
{
if(NOCYCLE == aNode[nIndex].bCycle)
{
if(NONEXT != aNode[nIndex].nNextNode)
{
StartDetect(aNode, nIndex);
}
}
}
}
int main()
{
node aNode[MAXMUMSIZE];
InitNode(aNode);
Cycledetect(aNode);
for(int nIndex = 0; nIndex<MAXMUMSIZE; nIndex++)
printf("Is Node_%d in cycle?: %d\n", nIndex, aNode[nIndex].bCycle);
return 0;
}