如何进行数据结构之图的深度优先搜索，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。
遍历原则：
从图中某一个指定的顶点v出发，先访问v，然后从该顶点未被访问过的邻接顶点w出发进行深度优先搜索，直到图中与v想通的所有顶点都被访问，此时相当于完成图中一个包含顶点v的连通分量的遍历。如果图中存在尚未遍历过的顶点，则从另一个未被访问的顶点出发重复上述过程，直到图中所有顶点均被遍历到。
显然，深度优先搜索算法是一种递归算法。
分析：
假设有一幅图，如下图所示。
该图的邻接表为：
如果对该图进行深度优先搜索，步骤如下：
STEP1：从顶点A出发进行深度优先搜索。首先访问顶点A，并将A标注为已访问状态（图中标注为黄色），然后去找顶点A的第一个邻接点，如果第一个邻接点已被访问，则搜索顶点A的下一个邻接点。显然，顶点A的第一个邻接点为顶点B，且B未被访问。
STEP3：访问顶点C，并将C标注为已访问状态（图中标注为橙色），寻找C的第一个邻接点B，因为B已经被访问，因此寻找下一个邻接点D，D未被访问过。
STEP5：访问顶点E，并将E标注为已访问状态（图中标注为红色），访问E的第一个邻接点D，发现D已经被访问过，然后去找E的下一个邻接点，发现没有邻接点，则返回上一层，也就是STEP4。
STEP7：寻找顶点D的未被访问的邻接点，发现不存在这样的邻接点，则返回STEP3层；寻找顶点C的未被访问的邻接点，发现不存在这样的邻接点，则返回STEP2层；寻找顶点B的未被访问的邻接点，发现不存在这样的邻接点，则返回STEP1层；寻找顶点A的未被访问的邻接点，发现不存在这样的邻接点，则退出程序。此时，图中各个顶点的访问便结束了。
看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注亿速云行业资讯频道，感谢您对亿速云的支持。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
