首页 > 代码库 > 算法题——图的深度优先遍历

算法题——图的深度优先遍历

2024-07-17 23:56:12   219人阅读

原理和方法可以参考： 图的深度优先遍历 

教科书上的C代码，递归：

 1 //教科书方法，邻接表 2 bool visited[MAX]; 3 void visitFunc(int v); 4  5 void dfsTraverse(Graph G) 6 { 7     for(v = 0; v < G.vexnum; ++v)   //初始化访问标识为false 8         visited[v] = false; 9     for(v = 0; v < G.vexnum; ++v)   //深搜10         if(!visited[v])11             dfs(G, v);12 }13 14 void dfs(Graph G, int v)15 {16     visited[v] = true;17     visitFunc(v);18     for(w = firstAdjVex(G, v); w; w = nextAdjVex(G, v, w))  //遍历邻接表19         if(!visited[w])20             dfs(G, w);21 }

 

迭代版：

 1 //使用堆栈来保持顺序，迭代 2 void dfsTraverse(GraphNode *G) 3 { 4     unordered_map<GraphNode *, bool> visited; 5     stack<GraphNode*> unvisited; 6     unvisited.push(G);          //第一个结点入栈 7     while( !unvisited.empty() ) 8     { 9         cur = unvisited.top();10         unvisited.pop();11 12         for(w = G.neighbor; w != NULL; w = w->next)      //遍历邻接表13             if( visited.find(w->Node) == visited.end() )14             {15                 unvisited.push(w->Node);16                 visited[w->Node] = true;17             }18 19         visitFunc(cur);20     }21 }

 


联系
我们