Question

图深度优先遍历非递归算法 怎么写?

图的邻接表结构定义如下
typedef char type;
typedef float weight;
typedef struct Enode{
int VertexNumber;// 记录出边表中结点在顶点表中的序号
weight cost;//边权值
struct Enode *next;//邻接表链接指针 指向顶点的下一个邻接顶点
}Edge;
typedef struct Vnode{
type Vname;//顶点名
struct Enode *FirstEdge;//邻接表头指针
}Vertex;
typedef struct{
Vertex *VertexList;//指向顶点表数组的指针
int NumVertex,NumEdge;//顶点数 边数
}ALGraph;

请问 图深度优先遍历非递归算法 怎么写?(用堆栈实现 假设进栈操作为void Push(Stack S,int i) 出栈操作为int Pop(Stack S)

Answer 1

参看有关回溯法的非递归算法，人为使用一个栈保存遍历的路径供退回时使用，类似于迷宫问题的非递归解决，总体而言，这类回溯法的非递归算法比递归算法效率高一些，但是代码长一些，需要程序员自行管理一个栈

Answer 2

首先我要知道你用的是什么语言，才好解决

追问

用c++或者c

追答

还是打一个程序员做一下，