数据结构—深度优先排线、广度优先排线深度优先排线实现广度优先排线实现排线算法应用代码实现
深度优先遍历
深度优先遍历的过程是从图中的某个初始点v出发，首先访问初始点v
然后选择与顶点v相邻但未访问的顶点w
以w为初始顶点，从中进行深度优先的遍历
直到与图中顶点v相邻的所有顶点都被访问为止
很明显，这个遍历过程是递归过程
以邻接表为存储结构的深度优先遍历算法如下
其中v是初始点，visited是全局数组，初始情况下所有元素均为0，表示所有顶点尚未访问。)
int visited[Max]={0}； voidDFS(adjgraph*g，int v )//深度优先遍历ArcNode *p； 可视[ v ]=1； coutv； p=G-adjList[v].firstArc； while(p！=NULL () if )可视[ p-adjvex ]==0) DFS(g，p-adjvex )； p=下一个Arc； }对于具有n个顶点、e条边的有向图或有向图，由于对图中的各顶点最多调用1次DFS算法，所以递归调用的合计次数为n
当访问某个顶点v时，DFS的时间主要用于从该顶点出发寻找其相邻点
用邻接表表示图表时，需要遍历该顶点的所有邻接点，因此DFS的总时间为O(n e )
用邻接矩阵表示图表时，需要遍历该顶点行的所有要素，因此DFS的总时间为o(n )
广度优先遍历广度优先遍历的过程是首先访问初始点v
下一个访问顶点v的所有未访问的相邻节点v1 v2 .vt
然后，按照v1 v2 .vt的顺序访问各顶点的所有未访问的相邻接点
这样，直到图中初始点和路径连通的顶点全部被访问为止
相邻表为存储结构，按广度优先遍历图表时需要使用队列
在此，使用循环队列，以二叉树那样的层次遍历方式遍历图表
对应的算法如下。 但是，是初始点)
代码为voidBFS(adjgraph*g，int v )//广度优先int w，I； ArcNode *p； 队列输入q； int visited[MAX]； for(I=0； iG-n； I )可视[ I ]=0； coutv； 可视[ v ]=1； q.push(v； while (！ q.empty () (q.push ) ) w； p=G-adjList[w].firstArc； while(p！=NULL () if ) visited[p-adjvex]==0) { coutp-adjvex； 可视[ p-adjvex ]=1； q .推(p-adjvex )； (} p=p-nextarc； } } coutendl； }很明显，有n个顶点、e条边的有向图或有向图
在BFS 算法上按顶点进入队伍
因此，执行时间与DFS相同，在图表由邻接表表示的情况下，BFS的总时间为o(ne )
用邻接矩阵表示图，BFS的总时间为o(n )
遍历算法的应用假设曲线g采用邻表存储，设计算法输出曲线g的顶点u到的简单路径(例如
采用深度优先遍历的方法
从顶点u出发找到顶点v的路径的过程
因此，基于深度优先遍历算法添加v、path和d几个形状参数
在此，path保存从顶点u到v的路径，d表示path中的路径长度，其初始值为11
从顶点u遍历到顶点v后，输出path并返回
代码为voidonesimplepath(adjgraph*g，int u，int v，int path[]，int d )//简单路径int w，I； ArcNode *p； 可视[ u ]=1； d； path[d]=u； if(u==v ) for ) I=0； i=d； I ) coutpath[i]； coutendl； 返回； } p=G-adjList[u].firstArc； while(p！=null}{w=p-adjvex； if (可视[ w ]==0) onesimplepath(g，w，v，path，d )； p=下一个Arc； }