还有一种算法，就是用有向图来实现(具体见下面代码)：
把链表看成一个有向图，深度优先遍历该有向图，判断有无循环出现。
懒得再用中文写一遍具体算法了，看下面的代码实现吧，英文注释解释的很清楚了。
时间复杂度 O(e), 链表边的总数。
空间复杂度 O(1).
有向图采用邻接表实现。
/* file: DFSDetectLoop.cpp */
/*
* Detect if the graph has loop -- For both Undigraph and digraph
* Complexity: O(e); e is the number of arcs in Graph.
*
* BUG Reported:
* 1. Apr-26-07
* Not support Undigraph yet ! Fix me !!!
* - Fixed on Apr-26-08.
*
* Return
* 1 - Loop detected.
* 0 - No loop detected.
* *
* Algrithm:
* 1. Init all the nodes color to WHITE.
* 2. DFS graph
* For each the nodes v in graph, do step (1) and (2).
* (1) If v is WHITE, DFS from node v:
* (a) Mark v as GRAY.
* (b) For every nodes tv adjacent with node v,
* (i) If the current visiting node is gray, then loop detected. exit.
* (ii) Goto Step (1).
* (iii) All the nodes on sub-tree of tv have been visited. Mark node tv as BLACK.
* (2) All the nodes on sub-tree of v have been visited. Mark node v as BLACK.
*
* Function DFSDetectLoop is valid for both Undigraph and digraph.
*
* */
int DFSDetectLoop (ALGraph *graph, int VisitFunc (ALGraph *graph, int v))
{
int v;
for (v = 0; v < graph->vexnum; v++)
{
MarkNodeColor (graph, v, WHITE);
}
for (v = 0; v < graph->vexnum; v++)
{
if (graph->vertices[v].color == WHITE)
{
/* We are good to call DFSDetectLoopSub the first
* time with pv = -1, because no node equals -1.
* */
if (1 == DFSDetectLoopSub (graph, v, -1, VisitFunc))
return 1;
}
MarkNodeColor (graph, v, BLACK);
}
return 1;
}
/*
* Start from node v, DFS graph to detect loop.
* pv is the node that just visited v. pv is used to avoid v to visit pv again.
* pv is introduced to support Undigraph.
*
* NOTE:
* Before calling DFSDetectLoopSub, make sure node v is not visited yet.
* */
int DFSDetectLoopSub (ALGraph *graph, int v, int pv, int VisitFunc (ALGraph *graph, int v))
{
assert (graph->vertices[v].color == WHITE);
MarkNodeColor (graph, v, GRAY);
VisitFunc (graph, v);
ArcNode *arc;
arc = graph->vertices[v].firstarc;
while (arc)
{
int tv = arc->adjvex;
/* For Undigraph, if tv equals pv, this arc should not be count.
* Because we have just visited from pv to v.
* Just go ahead to check next vertex connected with v.
* 1----2, after visit 1, we will visit 2, while visiting 2, 1 will be the 1st node visited.
*
* For digraph, we need to check loop even tv equals pv.
* Because there is case that node v points to u, and u points to v.
* */
if ((graph->kind == AG) && (tv != pv))
{
if ( graph->vertices[tv].color == GRAY )
{
cout << "Gray node visited at node: " << tv + 1 <<endl;
cout << "DFSDetectLoopSub: Loop Detected at from node " << v + 1<<" to "<< tv + 1 <<" !" <<endl;
return 1;
}
if (graph->vertices[tv].color == WHITE)
{
if (1 == DFSDetectLoopSub (graph, tv, v, VisitFunc))
{
return 1;
}
}
/* At this line:
* (1)If tv's color is already BLACK; Go ahead checking next arc;
* (2)If the sub-tree of node tv has all been visited, mark as BLACK and check next arc;
* Backward tv to to v's other adjacent node. So tv should be marked as black.
* */
MarkNodeColor (graph, tv, BLACK);
}
arc = arc->nextarc;
}
return 0;
}
回复 更多评论