深度优先遍历(Depth First Search,DFS)是一种用于遍历或搜索图的算法。下面是实现深度优先遍历的步骤解释:
首先定义一个Graph类,其中包含私有成员变量V表示顶点数目,adjMatrix表示邻接矩阵,vertexMap表示顶点名称到索引的映射表。
在构造函数中初始化顶点数目和邻接矩阵,并使用resize()函数创建相应大小的二维vector。
addVertex()函数用于添加新的顶点。首先检查该顶点是否已经存在于vertexMap中,如果不存在,则将其加入vertexMap,并设置对应的索引值。
addEdge()函数用于添加边。通过获取源顶点和目标顶点在vertexMap中的索引值,将邻接矩阵对应位置置为1,表示两个顶点之间存在边。
DFSUtil()函数是递归地进行深度优先遍历的核心方法。它接受一个起始节点v和一个visited数组,用来记录节点是否被访问过。首先将当前节点v标记为已访问,并输出节点名称。然后遍历与当前节点v相邻且未访问过的节点,并对这些相邻节点递归调用DFSUtil()函数。
DFS()函数是对整个图进行深度优先遍历的方法。首先创建一个visited数组,并将其初始化为false,表示所有节点均未被访问。然后遍历所有节点,对每个未被访问的节点调用DFSUtil()函数。
getVertexName()函数根据索引值获取顶点名称,通过遍历vertexMap找到对应的名称。
printAdjMatrix()函数用于打印邻接矩阵。
在主函数中创建一个Graph对象graph,并添加顶点和边。然后依次调用DFS()和printAdjMatrix()函数进行深度优先遍历和打印邻接矩阵。
以上就是实现深度优先遍历的步骤解释。该程序会输出深度优先遍历结果和邻接矩阵。
内容由零声教学AI助手提供,问题来源于学员提问