基于邻接矩阵存储的图的深度优先搜索（DFS）实现思路以及代码（超级详细）

野性酷女 2023-06-30 08:47 5阅读 0赞

#### 图 ####

##### 深度优先搜索（DFS） #####

**深度优先搜索类似于树的前序遍历，而不一样的地方是图的深度优先搜索遍历在遍历的过程中可能会因为图本身的结构原因而反复地访问到一个顶点。这个是不被允许的，所以我们需要对应的解决的方法来针对这个问题。下面是算法实现的主要实现思路：**  
**实现深度优先搜索算法我们一般有两种思路：一种是通过递归的方法，一种是借助栈来实现。以下讨论的是借助栈来实现的思路**

*  1、首先，由于我们讨论的图结构是用邻接矩阵进行存储的，我们就以邻接矩阵来进行讨论
 *  2、准备工作，因为我们需要避免在遍历的过程中**对一个顶点**访问超过1次，所以我们需要一个用来标记顶点**是否已经访问过的数组visited**，只有当还没有访问的时候才进行访问。因为我们需要借助**栈的先进后出的特点来进行辅助实现深度优先搜索遍历**，所以我们创建一个栈s。
 *  2、输入一个**起点v**, 以此当做是深度优先搜索遍历的起点，然后我们通过locateVex函数（输入顶点v,返回顶点v在顶点表中的下标）找到v的下标**index**，因为此时顶点v已经访问完了，所以我们需要将**visited\[index\]进行标记，表示已经访问过，并且加入栈中**，然后到图的邻接矩阵的第**index**行进行依次访问该点到其他点的权值，如果对应的权值不为默认值**并且visited数组表示这个顶点还没有被访问**，那么就将这个点加入**栈s**中，然后将这个顶点打印出来，进行**下一次循环**，**下一次的起点就取为栈s的栈顶元素，循环往复，那么有入栈必有出栈**，什么时候出栈，当已经访问完邻接矩阵的一整行之后，就将栈顶元素进行弹出，**循环的停止条件是当栈s为空的时候就表示已经完成。**

#### 具体实现代码如下： ####

void DFS_Stack(MyGraph mygraph, char v) {
    
    	MyStack* s = new MyStack(-1);//创建一个栈s
    
    	cout << v << " ";
    	visited[locateVex(mygraph, v)] = true;
    	s->push(locateVex(mygraph, v));//将v压入栈中
    
    	while (s->next != NULL) {
    		//当栈为空时停止
    		int index = s->top();//下一次的起点为栈s的栈顶元素
    		
    		int i;
    		for (i = 0; i < mygraph.curVexNum; i++) {
    			if (mygraph.arcs[index][i] != de_num && visited[i] != true) {//只有当权值不为默认值并且还没有访问过
    				//就将其放入栈中
    				cout << mygraph.vexs[i] << " ";
    				visited[i] = true;//表示已经访问过
    				s->push(i);
    				break;//这个很重要，只有这样才能构成深度优先搜索
    			}
    		}
    
    		//啥时候出栈？出栈的时候说明访问的该行所有邻接点都已经访问完了
    		if (i == mygraph.curVexNum) {
    			s->pop();
    		}
    	}
    	delete[] s;//将栈s进行删除
    }

**如有错误，劳烦指正！谢谢**