【数据结构——图扫描】一、介绍二、深度优先搜索DFS (深度优先搜索) 1、深度优先搜索扫描过程2、深度优先搜索扫描算法实现3、非连通图深度优先搜索扫描3、深度优先搜索BFS (深度优先搜索breadth )
一、介绍
图的遍历：从图的某个顶点出发，依次访问图中所有的顶点，每个顶点被访问一次且仅访问一次。防止多次访问某个顶点的想法：设置标记每个被访问顶点的辅助数组visited[n]，
初始化状态为visited[n]=0； 如果顶点访问，则更改辅助数组的值。 可视[ I ]=1
二、深度优先搜索DFS (深度优先搜索) 1、深度优先搜索遍历的过程深度优先搜索生成树： 对于无向连通生成图，如果将第一次深度优先搜索时前进操作经过的边保留下来则可以构成一棵深度优先搜索生成树
2、深度优先搜索遍历的算法为递归的搜索算法：dfs(G,v)
/*访问图的深度优先搜索导线*/DFS(g，v ) ) v，标记v已访问并访问v的相邻节点w，如果w未访问，则访问DFS(g，w ) } /*图的深度优先搜索导线//falsevoidDFS(graphg，int v ) )//从第v个顶点开始深度优先搜索遍历图Gcout v； 可视[ v ]=true； //访问第一个顶点v，访问标记为truefor(w=firstadjvex(g，v )； w=0； w=nextadjvex(g，v，w ) ) if (！ 可视[ w ] ) DFS(g，w )； 未访问//v的顶点递归扫描}//firstadjvex(g，v )是v的第一个相邻点//NextAdjVex(G ) g，v，w )是v的下一个相邻点采用邻接矩阵表示的图的DFS:
/*邻接矩阵的存储结构*/typedef struct { vertextypevexs [ mv num ]； //顶点表ArcType arcs[MVNum][MVNum]； //相邻矩阵int vexnum，arcnum； //当前图表的顶点数和边数}AMGraph； /*用邻接矩阵表示的图表的DFS*/voidDFS_am(amgraphg，int v ) (从第/v个顶点开始依次遍历图表Gcout v； //第v个顶点visited [ v ]=访问真//访问标记数组为真for (w=0； w=G.vexnum； w(//具有相邻矩阵v的行(if ) ) (g.ARCS[v][w]！=0()！ 可视[ w ]； DFS_am(g，w )； //w是v的相邻节点，如果w未被访问，则调用DFS_AM}}用相邻矩阵表示。 寻找各节点相邻点的时间复杂度为o(n的平方)，如果加上初始化visited数组的时间复杂度o ) n，则DFS的时间复杂度为o ) n的平方)
采用邻接表表示图的DFS
/*图邻接表的记忆定义*//弧的节点结构#define MVNum 100//最大顶点数typedef struct ArcNode{int adjvex； //该边所指顶点的位置struct ArcNode* nextarc； //指向下一边的指针OtherInfo info； //边相关信息}ArcNode； //顶点的节点结构typedefstructvnode { vertextypedata； //顶点信息ArcNode* firstarc； //指依赖于该顶点的第一边(}VNode，AdjList[MVNum]； //AdjList是邻接表类型//AdjList v为VNode v[MVNum]//图的结构定义(邻接表) typedefstruct(adjlistvertices； //vertices是vertex的多个int vexnum、arcnum； //图的当前顶点数和边数}ALGraph； /*相邻表中表示图表的DFS*/voidDFS_al(algraphg，int v ) ) /图表g为相邻表类型，从第v个节点开始，依次为DFS图表Gcout v； //访问第v个顶点visited[v]=true访问标记为truep=G.vertices[v].firstarc； //p是v的边缘链接列表中的第一个边缘节点白色(p！=空边节点不为空{w=p-adjvex； //w是p的邻接点下标if (！ 可视[ w ] ) DFS_al(g，w )； 如果//w未被访问，则递归地DFS_ALp=p-nextarc； //p指的是下一个边节点}}用邻接表表示图。 寻找各节点相邻点的时间复杂度为o(e )，加上初始化可见数组的时间复杂度o ) n )，则DFS的时间复杂度为o ) ne )
3、非连通图深度优先搜索扫描算法思想：
1、将图中各顶点的访问标志设为false
2 )依次(顶点编号)检索图中的各顶点，如果未被访问，则以该顶点为起点进行深度优先搜索的遍历，否则，在图中的所有顶点被访问之前继续检查下一个顶点。
/*非连通图g的深度优先搜索扫描*/voidDFStraverse(graphg ) ) for ) v=0； v G.vexnum； v )可视[ v ]=false； //访问标志数组初始化for(v=0； v G.vexnum； v ) if (！ 可视[ v ] ) DFS(g，v )； //对尚未访问的顶点调用DFS (三、宽度优先搜索BFS(Breadthfirstsearch ) 1、介绍树型分层扫描
1、从图中某个顶点v出发，访问v
2、依次访问v未访问的各邻点
3、从这些相邻点开始依次访问他们的相邻点，使“先访问顶点的相邻点”先于“后访问顶点的相邻点”
重复4、3，直到访问的所有顶点的相邻点被访问。
2、算法思想及说明
/*广度优先非递归连通图g*/voidBFS(graphg，int v ) {cout v； 可视[ v ]=true； //访问第一个顶点InitQueue(Q )//次队列q初始化，空enqueue(q，v )； 进入//v团队while (！ 队列深度(q )//队列不为空) dequeue，u )； //团队领导要素排列成ufor (w=first adjvex ) g，u )； w=0； w=nextadjvex(g，u，w ) ) if (！ 可见[ w ] (//w为u的尚未访问的相邻顶点{cout w； 可视[ w ]=true； //集访问标志序列的成分为真枚举(q，w )； 进入//w团队}}
对无向连通图：如果将一次广度优先搜索时前进操作经过的边保留下来则可构成一棵广度优先搜索生成树。