图的深度优先算法

A. 图的深度优先搜索算法dfs函数里面firstadjvex是什么意思

FirstAdiVex(G,v);
初始条件：图G存在，v是G中某个顶点。
操链辩作结果：返回v的第一个领接顶点，若弊野定点在G中没有领接顶点，则返回棚卜缺空。

B. 图的矩阵深度和广度遍历算法

图的遍历是指从图中任一给定顶点出发，依次访问图中的其余顶点。如果给定的图是连通图，则从图中的任意一点出发，按照一个指定的顺序就可以访问到图中的所有顶点，且每个顶点只访问一次。这个过程称为图的遍历。
图的遍历比树的遍历复杂的多。树是一种特殊类型的图，即无圈（无回路）连通图。树中的任意两个顶点间都有唯一的路径相通。在一个顶点被访问过之后，不可能又沿着另外一条路径访问到已被访问过的结点。而图中的顶点可能有边与其他任意顶点相连
。因此在访问了某个顶点之后，可能沿着另一条边访问已被访问过的顶点。例如图（a）中的G1，在访问了V1，V2和V3之后，有可能沿着边（V3，V1）访问到V1。为了避免一顶点被多次访问，可以设立一个集合Visited，用来记录已被访问过的顶点。它的初值为空
集。一旦V1被访问过，即把V1加到集合Visited中。图的遍厉通常有两种:图的深度优先
搜索和图的广度优先搜索。
1）图的深度优先搜索
从图G=（V，E）的一个顶点V0出发，在访问了任意一个与V0相邻且未被访问过的顶点W1之后，再从W1出发，访问和W1相邻且未被访问过的顶点W2，然后再从W2出发进行如上所述访问，直到找到一个它相邻的结点，都被访问过的结点为止。然后退回到尚有相
邻结点未被访问过的顶点，再从该顶点出发，重复上述搜索过程，直到所有被访问过的顶点的邻接点都被访问过为止。图的这种遍历过程就称为图的深度优先搜索。例如从顶点V1出发对图3.3.5进行深度优先搜索，遍历的顺序为 V1,V2,V5,V10,V6,V7,V3,V12,V1
1,V8,V4,V9。（与邻接表中的邻接点排列顺序有关，即p->next.vertex=v2 or v3对遍历
顺序有影响 ）
例25.(p194.c)图的深度优先搜索。从图G的顶点V0
发进行深度优先搜索，打印出各个顶点的遍历顺序。
解：图的深度优先搜索法为：
（1）首先访问V0并把V0加到集合visited中；
（2）找到与V0相邻的顶点W，若W未进入
visited中，则以深度优先方法从W开始搜索。
（3）重复过程（2）直到所有于V0相邻的顶点
都被访问过为止。

下面是对用邻接表表示的图G进行深度优先搜索的程序
int rear=0; /*Visit和rear都为全局变量*/
int visit[500];
depth_first_search(g,v0) /*从V0开始对图G进行深度
优先搜索*/
graphptr g[ ]; /*指针数组,为邻接表表头顶点指针
g[vi]...g[vn]*/
int v0; /*这里V0和W都是顶点标号,如V0=0或1*/
{ /*g[v0]是顶点V0的表头指针*/
int w;
graphptr p; /*链表的结点指针*/
visit [++rear]=v0;
printf("%d\n",v0);
p=g[v0];/*指定一个顶点，通过邻接表表头指针
，访问v0的邻接顶点*/
while (p!=NULL)
{
w=p->vertex ;/*这里W是与V0相邻的一个顶点*/
if (!visited(w))/*当V0的相邻结点，W未被访问时，从W开始遍厉*/
depth_first_search(g,w);
p=p->next;/*接着访问另一个相邻顶点*/
}
}
int visited(w) /*检查顶点w是否进入visited(w)*/
int w ;
{
int i;
for (i=1;i<=rear;i++)
if (visit [ i ] == w) return(1);/*W在visit[]中，说明被访问过*/
return(0); /*W不在visit[]中，说明未被访问过，返回0*/
}
2）图的广度优先搜索
从图G的一个顶点V0出发，依次访问V0的邻接点K1,K2...Kn。然后再顺序访问K1,K2...Kn的所有尚未被访问过的邻接点。如此重复，直到图中的顶点都被访问过为止。图的这种搜索称为图的广度优先搜索。例如：从V1出发按广度优先搜索方法遍历图3.3.5,顶
点的访问顺序为V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11,V12。
图的广度优先搜索类似树的按层次遍历，需要有一个队列来存放还没
有来得及处理的顶点。图的广度优先搜索算法为：
（1）首先把V0放入队列；
（2）若队列为空则结束，否则取出队列的头V；
（3）访问V并把所有与V相邻且未被访问的顶点插入队列；
（4）重复（2）-（3）直到队列为空。
上述算法中所有已被访问过的顶点都放在队列中，因此只要检查某个顶点是否在队列中就可以判断出该顶点是否已被访问过。
广度搜索法的程序如下：
broad_first_search(g,v0) /*从V0开始对图g进行广度优先搜索*/
graphptr g[ ]; /*为邻接表，表头顶点指针*/
int v0;
{
int queue[500],front =1, tail=1,v;
graphptr p;
queue [tail]=v0; /*把V0插入队列queue*/
while (front <=tail)/*当队列不为空*/
{
v=queue[front++]; /*取出队列中的顶点*/
printf("%d\n",v); /*访问该顶点*/
p=g[v]; /*从顶点V的链表来考虑与V相邻的顶点*/
while (p!=NULL)
{
v=p->vertex; /*从第一个结点（即边）中找出相邻的顶点*/
if (!visited(queue,tail,v))/*判断顶点是否进入队列，如进入队列
说明已被访问或将要访问*/
queue[++tail]=v;/*如果该顶点未被访问过，将此相邻顶点插入队列*/
p=p-->next;/*再考虑该结点的下一个相邻顶点*/
}
}
}
visited (q,tail,v)/*判断顶点是否被访问过，访问过时，返回1，否则返回0*/
int q[ ],tail,v;/*进入队列的顶点，在front之前的顶点已被访问过打印输出，
在front和tail之间的顶点是即将要访问顶点*/
{
int i;
for(i=1;i<=tail;i++)/*扫描队列，确定v是否在队列中，在队列中返回1，否则返回0*
/
if (q[i]==v)return(1);/*队列中的顶点都认为已被访问过*/
return(0);
}

深度优先的非递归算法

/*设当前图(或图的某个连通分枝)的起始访问点为p*/
NodeType stackMain,stackSec
visit(p)
p->mark=true;
do
{
for(all v isTheConnectNode of (G,p))//将当前点的邻接点中的所有结点压入副栈中
if(v.marked==false)
statckSec.push(v)
//将副栈中的点依次弹出，压入主栈中，这与非递归算法中使用队列的意图类似
while(!stackSec.isEmpty())
stackMain.push(statckSec.pop());
do//找出下一个未访问的结点或者没找到，直到栈为空
{
if(!stackMain.isEmpty())

{
p=stackMain.pop();

}
}while(p.marked==true&&!stackMain.isEmpty())
if(p.marked==false)//访问未访问结点.

{

visit(p);

p.marked=true;

}

}while(!stackMain.isEmpty())

C. 图遍历算法之DFS/BFS

在计算机科学， 图遍历（Tree Traversal，也称图搜索）是一系列图搜索的算法， 是单次访问树结构类型数据（tree data structure)中每个节点以便检查或更新的一系列机制。图遍历算法可以按照节点访问顺序进行分类，根据访问目的或使用场景的不同，算法大致可分为28种：

图遍历即以特定方式访问图中所有节点，给定节点下有多种可能的搜索路径。假定以顺序方式进行（非并行），还未访问的节点就需通过堆栈（LIFO）或队列（FIFO）规则来确定访问先后。由于树结构是一种递归的数据结构，在清晰的定义下，未访问节点可存储在调用堆栈中。本文介绍了图遍历领域最流行的广度优先搜索算法BFS和深度优先搜索算法DFS，对其原理、应用及实现进行了阐述。通常意义上而言，深度优先搜索（DFS）通过递归调用堆栈比较容易实现，广义优先搜索通过队列实现。

深度优先搜索（DFS）是用于遍历或搜索图数据结构的算法，该算法从根节点开始（图搜索时可选择任意节点作为根节点）沿着每个分支进行搜索，分支搜索结束后在进行回溯。在进入下一节点之前，树的搜索尽可能的加深。
DFS的搜索算法如下（以二叉树为例）：假定根节点（图的任意节点可作为根节点）标记为 ,
(L) : 递归遍历左子树，并在节点 结束。
(R): 递归遍历右子树，并在节点 结束。
(N): 访问节点 。
这些步骤可以以任意次序排列。如果（L）在（R）之前，则该过程称为从左到右的遍历；反之，则称为从右到左的遍历。根据访问次序的不同，深度优先搜索可分为 pre-order、in-order、out-order以及post-order遍历方式。

（a）检查当前节点是否为空；
（b）展示根节点或当前节点数据；
（c）递归调用pre-order函数遍历左子树；
（d）递归调用pre-order函数遍历右子树。
pre-order遍历属于拓扑排序后的遍历，父节点总是在任何子节点之前被访问。该遍历方式的图示如下：

遍历次序依次为：F -B -A-D- C-E-G- I-H.

（a）检查当前节点是否为空；
（b）递归调用in-order函数遍历左子树；
（c）展示根节点或当前节点数据；
（d）递归调用in-order函数遍历右子树。
在二叉树搜索中，in-order遍历以排序顺序访问节点数据。该遍历方式的图示如下：

遍历次序依次为：A -B - C - D - E - F - G -H-I

（a）检查当前节点是否为空；
（b）递归调用out-order函数遍历右子树；
（c）展示根节点或当前节点数据；
（d）递归调用out-order函数遍历左子树。
该遍历方式与LNR类似，但先遍历右子树后遍历左子树。仍然以图2为例，遍历次序依次为：H- I-G- F- B- E- D- C- A.

（a）检查当前节点是否为空；
（b）递归调用post-order函数遍历左子树；
（c）递归调用post-order函数遍历右子树；
（d）展示根节点或当前节点数据。
post-order遍历图示如下：

遍历次序依次为：A-C-E-D-B-H-I-G-F.

pre-order遍历方式使用场景：用于创建树或图的副本；
in-order遍历使用场景：二叉树遍历；
post-order遍历使用场景：删除树

遍历追踪也称树的序列化，是所访问根节点列表。无论是pre-order，in-order或是post-order都无法完整的描述树特性。给定含有不同元素的树结构，pre-order或post-order与in-order遍历方式结合起来使用才可以描述树的独特性。

树或图形的访问也可以按照节点所处的级别进行遍历。在每次访问下一层级节点之前，遍历所在高层级的所有节点。BFS从根节点（图的任意节点可作为根节点）出发，在移动到下一节点之前访问所有相同深度水平的相邻节点。

BFS的遍历方法图示如下：

遍历次序依次为： F-B-G-A-D-I-C-E-H.

图算法相关的R包为igraph，主要包括图的生成、图计算等一系列算法的实现。

使用方法：

参数说明：

示例：

结果展示：

DFS R输出节点排序：

使用方法：

参数含义同dfs
示例：

结果展示：

BFS R输出节点排序：

以寻找两点之间的路径为例，分别展示BFS及DFS的实现。图示例如下：

示例：

输出结果：

示例：

输出结果：

[1] 维基网络： https://en.wikipedia.org/wiki/Tree_traversal
[2] GeeksforGeeks: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
[3] http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html
[4]Martin Broadhurst, Graph Algorithm: http://www.martinbroadhurst.com/Graph-algorithms.html#section_1_1
[5]igraph: https://igraph.org/r/doc/dfs.html
[6]igraph: https://igraph.org/r/doc/bfs.html
[7] Depth-First Search and Breadth-First Search in python: https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

D. 图的广度、深度优先搜索和拓扑排序

广度优先搜索是最简单的图搜索算法之一。之所以得名是因为该算法始终将已经发现的结点集合，沿着其 广度方向 向外扩展去寻找未发现结点。
具体算法执行过程如下图所示：

深度优先搜索，只有可能就在图中尽可能的 深入 ，总是从最近才发现的结点出发，寻找下一个结点。
具体算法执行过程如下图所示：

拓扑排序是计算机中经常遇到的概念，下面用于《算法导论》的定义

如下图3-1所示，事件E1完成之后，可以同时执行事件E2和E3，两事件执行结束之后，执行事件E4，最后可以同时执行事件E5和E6。每个事件的执行都依赖于它之前事件是否执余槐陪行完成，执行的顺序是固定的，这样的线性顺序就是 拓扑排序 。

图的广度、深度优先搜索和拓扑排序是图论算法中的基础，也是实践中经常遇到的问题。在考研和面试笔试中会通过选择题或者填空题考察，学习理解上文图示中的算法思想，辅助练习问题不大。当然也有关于这里的算法题，例如LeetCode815公交路线问题，就是利用图的广度优先搜索求解，因竖蠢为解题复杂，并且在平时的应试中出现概率不大，这里不做详细讲解。有兴趣的可明段以在LeetCode中搜索，题目后面有我提交过的题解。

E. 基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）

        深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。

一、深度优先搜索

        深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

基本步奏

（1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。

（2）从stack中访问栈顶的点；

（3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；

（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；

（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。

二、广度优先搜索

        广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

基本步奏

（1）给出一连通图，如图，初始化全是白色（未访问）；

（2）搜索起点V1（灰色）；

（3）已搜索V1（黑色），即将搜索V2，V3，V4（标灰）；

（4）对V2，V3，V4重复以上操作；

（5）直到终点V7被染灰，终止；

（6）最短路径为V1，V4，V7.

F. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的先序遍历，为什么是先序呢

这是因为图的深度优先遍历算法先访问所在结点，再访问它的邻接点。与二叉树的先序遍历先访问子树的根结点，再访问它的孩子结点（邻接点）类似。图的广度优先遍历算法类似于二叉树的按层次遍历。
先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。
首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。
例如，下图所示二叉树的遍历结果是：ABDECF。

(6)图的深度优先算法扩展阅读：
遍历种类：
一、NLR：前序遍历(Preorder
Traversal
亦称（先序遍历）），访问根结点的操作发生在遍历其左右子树之前。
二、LNR：中序遍历(Inorder
Traversal)，访问根结点的操作发生在遍历其左右子树之中（间）。
三、LRN：后序遍历(Postorder
Traversal)，访问根结点的操作发生在遍历其左右子树之后。
注意：
由于被访问的结点必是某子树的根，所以N(Node）、L(Left
subtree）和R(Right
subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为
先根遍历、中根遍历和后根遍历。
参考资料来源：网络-先序遍历

G. 图的深度优先遍历序列什么唯一

图的深度优先遍历序列不唯一的 。如下面这个图 深度优先遍历可以是ABEFCD ，也可以是ADCBFE。

假设给定图G的初态是所有顶点均未曾访问拍孙过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。

若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。

若此时图中仍有未访问的顶点，袭数链则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

(7)图的深度优先算法扩展阅读：

图的遍历要比树的遍历毕答复杂得多，由于图的任一顶点都可能和其余顶点相邻接，故在访问了某顶点之后，可能顺着某条边又访问到了已访问过的顶点。

因此，在图的遍历过程中，必须记下每个访问过的顶点，以免同一个顶点被访问多次。为此给顶点附设访问标志visited，其初值为false，一旦某个顶点被访问，则其visited标志置为true。

图的遍历方法有两种：

一、深度优先搜索遍历（Depth-First Search 简称DFS）。

二、广度优先搜索遍历（Breadth_First Search 简称BFS）。

H. DFS(深搜)算法

深度优先搜索算法(Depth-First-Search) :是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。

话说大诗人李白，一生好饮。幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：

无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次销念早序。像这样的答案一共有多少呢？请你计算出所有可能方案的亏雀个数（包含题目给出的）。

注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。

答案：14

小明刚刚看完电影《第39级台阶》，离开高铅电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。

要求提交的是一个整数。
注意：不要提交解答过程，或其它的辅助说明文字。

I. 深度优先搜索法和广度优先搜索法

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度正模优先搜索中，对于最新发现的结点，如果它还有以此为起点而未搜过的边，就沿着边继续搜索下去。当结点v的所有边都已被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个过程反复进行直到所有结点都被发现为止。

深度优先搜索基本算法如下{递归算法}：
PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子结点 mr 符合条件 THEN
BEGIN
产生的子结点mr入栈；
IF 子结点mr是目标结点
THEN 输出
ELSE dfs_try(i+1);
栈顶元素出栈;
END;
END; 宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。
宽度优先搜索的核心思想带模是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第举行缓二层所有结点……，如此依次扩展，直到发现目标结点为止。

宽度优先搜索基本算法如下：
list[1]:=source; {加入初始结点，list为待扩展结点的表}
head:=0; {队首指针}
foot:=1; {队尾指针}
REPEAT
head:=head+1;
FOR x:=1 to 规则数 DO
BEGIN
根据规则产生新结点nw;
IF not_appear(nw,list) THEN {若新结点队列中不存在，则加到队尾}
BEGIN
foot:=foot+1;
list[foot]:=nw;
list[foot].father:=head;
IF list[foot]=目标结点 THEN 输出；
END；
END；
UNTIL head>foot; {队列为空表明再无结点可扩展}

J. 求c语言图的深度优先遍历算法

#define MaxVerNum 100 /* 最大顶点数为*/
typedef enum {False,True} boolean;
#include "stdio.h"
#include "stdlib.h"
boolean visited[MaxVerNum];

typedef struct node /* 表结点*/
{
int adjvex;/* 邻接点域,一般是放顶点对应的序号或在表头向量中的下标*/
char Info; /*与边(或弧)相关的信息*/
struct node * next; /* 指向下一个邻接点的指针域*/
} EdgeNode;
typedef struct vnode /* 顶点结点*/
{
char vertex; /* 顶点域*/
EdgeNode * firstedge; /* 边表头指针*/
} VertexNode;
typedef struct
{
VertexNode adjlist[MaxVerNum]; /* 邻接表*/
int n,e; /* 顶点数和边数*/
} ALGraph; /* ALGraph是以邻接表方式存储的图类型*/

//建立一个无向图的邻接表存储的算法如下：
void CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/
{
int i,j,k;
int N,E;
EdgeNode *p;
printf("请输入顶点数和边数：");
scanf("%d %d",&G->n,&G->e);
printf("n=%d,e=%d\n\n",G->n,G->e);
getchar();
for(i=0;i<G->n;i++) /* 建立有n个顶点的顶点表*/
{
printf("请输入第%d个顶点字符信息(共%d个)：",i+1,G->n);
scanf("%c",&(G->adjlist[i].vertex)); /* 读入顶点信息*/
getchar();
G->adjlist[i].firstedge=NULL; /* 顶点的边表头指针设为空*/
}
for(k=0;k<2*G->e;k++) /* 建立边表*/
{
printf("请输入边<Vi,Vj>对应的顶点序号(共%d个)：",2*G->e);
scanf("%d %d",&i,&j);/* 读入边<Vi,Vj>的顶点对应序号*/
p=(EdgeNode *)malloc(sizeof(EdgeNode)); // 生成新边表结点p
p->adjvex=j; /* 邻接点序号为j */
p->next=G->adjlist[i].firstedge;/* 将结点p插入到顶点Vi的链表头部*/
G->adjlist[i].firstedge=p;
}
printf("\n图已成功创建!对应的邻接表如下：\n");
for(i=0;i<G->n;i++)
{
p=G->adjlist[i].firstedge;
printf("%c->",G->adjlist[i].vertex);
while(p!=NULL)
{
printf("[ %c ]",G->adjlist[p->adjvex].vertex);
p=p->next;
}
printf("\n");
}
printf("\n");
} /*CreateALGraph*/

int FirstAdjVertex(ALGraph *g,int v)//找图g中与顶点v相邻的第一个顶点
{
if(g->adjlist[v].firstedge!=NULL) return (g->adjlist[v].firstedge)->adjvex;
else return 0;
}

int NextAdjVertex(ALGraph *g ,int vi,int vj )//找图g中与vi相邻的，相对相邻顶点vj的下一个相邻顶点
{
EdgeNode *p;
p=g->adjlist[vi].firstedge;
while( p!=NULL && p->adjvex!=vj) p=p->next;
if(p!=NULL && p->next!=NULL) return p->next->adjvex;
else return 0;
}
void DFS(ALGraph *G,int v) /* 从第v个顶点出发深度优先遍历图G */
{
int w;
printf("%c ",G->adjlist[v].vertex);
visited[v]=True; /* 访问第v个顶点，并把访问标志置True */
for(w=FirstAdjVertex(G,v);w;w=NextAdjVertex(G,v,w))
if (!visited[w]) DFS(G,w); /* 对v尚未访问的邻接顶点w递归调用DFS */
}

void DFStraverse(ALGraph *G)
/*深度优先遍历以邻接表表示的图G，而以邻接矩阵表示时，算法完全相同*/
{ int i,v;
for(v=0;v<G->n;v++)
visited[v]=False;/*标志向量初始化*/
//for(i=0;i<G->n;i++)
if(!visited[0]) DFS(G,0);
}/*DFS*/

void main()
{
ALGraph G;
CreateALGraph(&G);
printf("该无向图的深度优先搜索序列为：");
DFStraverse(&G);
printf("\nSuccess!\n");
}