数据结构问题：图的深度优先遍历中有递归的应用，要用到栈，图中顶点是如何出栈进栈的？是进栈时访问还是

Question

数据结构问题：图的深度优先遍历中有递归的应用，要用到栈，图中顶点是如何出栈进栈的？是进栈时访问还是出栈时访问？还是栈的应用不直接与顶点相关？如图，从1出发深度搜索，得到的序列是12345，那么这些顶点怎么进出栈？又是如何访问的？
理解不深入，求高手解答！

Answer 1

首先你得明白函数调用本身就是通过栈来实现的。 调用函数是入栈，而函数返回是出栈。
为什么是栈， 你要知道栈的特性是 “后进先出”或者是“先进后出”， 而对于函数调用来说， 一定会有最先调用的函数，最后才返回。 举个例子： 函数a,b,c,d的调用关系是a调用b，b又调用c，c又调用d， 那么当d函数执行完后，它会返回到c，同时c执行完成后返回到b，最后返回到a。
所以函数调用的顺序是a->b->c->d
函数返回的顺序是d->c->b->a
很明显 想要实现这种效果就要依靠栈。
因此函数调用过程是有一个叫做“调用栈”来实现的。
递归函数同理，只不过上边的a,b,c,d全变成同一个函数a->a->a->a，为了人为能区分清楚，不防给a函数加上角标，来标记是第几层调用a1->a2->a3->a4 ，返回时a4->a3->a2->a1 这就是递归函数调用返回过程。
接下来 深度优先搜索（dfs）本身就是靠函数递归调用实现的。
对于一个图来说，是由结点和边构成的， 在存储时就需要用到
struct node {
int data;
struct node * next[CNT];
}
上边只是一种简单的定义，对一个结点来说主要就是2部分， 一为它所存的数据是什么（数据域），二为它能指向哪些其它的边（指针域）。
你问了这样的问题：这些顶点怎么进出栈？又是如何访问的？
这里我要解释下访问的意义， 访问应该是对节点的数据域进行某种操作， 一定要理解这句话，是对数据域进行某种操作， 对于上边定义的结构 data就是数据域， 我需要对data进行某种操作，比如调用printf输出data， 这就是一种操作， 而只有对data进行了printf之后才能说“访问了这个结点”， 否则，单纯的使用了节点的指针域不能说访问了节点。
因此，如何访问节点的， 什么时候访问的，就要由你来定，
如果是下面这样的写法：
void dfs(struct node* n)
{
if (n->next[0] == NULL) {
return ;
}
for (int i = 0; n->next[i] != NULL; i++) {
dfs(n->next[i]);

}
printf ("%d\n", n->data);
}
你可以看到，printf是在 dfs函数递归调用 “返回”的时候才会被调用，换句话说， 图中所有节点在从开始走到不能再往下走的一个节点时(某个节点没有指向其它指点的边了），返回，同时输出该节点的data。 这种情况下是“出栈时访问”
而当printf换到if语句前头时，则是“入栈时访问”。
这如同二叉数的三种顺序遍历，前、中、后序遍历区别在于 何时访问节点
如下是前序遍历
void preorder(node* n)
{
printf(n->data);

preorder(n->left);
preorder(n->right);

}
如下是后序遍历
void afterorder(node* n)
{
afterorder(n->left);
afterorder(n->right);

printf(n->data);
}
如下是中序遍历
void inorder(node* n)
{
inorder(n->left);
printf(n->data);
inorder(n->right);
}