①无向图的非递归深度优先搜索需借用一个堆栈保存被访问过的顶点,以便回溯查找已被访问结点的被访问过的邻接点。
②访问起始顶点v0,visited[v0]标记1,v0入栈,指针p指向v0对应的边表首结点;
③从左到右扫描p所指的边表(邻接表),查找边表中对应顶点的visited[v]标志为0的结点;
④若找到所求结点,则对应的顶点记为v。然后访问v,visited[v]标记1,v入栈,p指向v对应的边表首结点。否则,从栈中出栈一个顶点作为v(即回溯)p指向v对应的边表首结点;
⑤重复②、③直至所有的顶点都被访问一次。