還有一種算法，就是用有向圖來實現(具體見下面代碼)：
把鏈表看成一個有向圖，深度優先遍歷該有向圖，判斷有無循環出現。
懶得再用中文寫一遍具體算法了，看下面的代碼實現吧，英文注釋解釋的很清楚了。
時間復雜度 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;
}
回復 更多評論