图的广度优先遍历与深度优先遍历

港控/mmm° 2022-03-15 06:48 377阅读 0赞

### 一. 广度优先遍历(Depth-First Search) ###

在进行遍历时，从图的深度入手，使用栈从起始顶点遍历到与之相连的某条通路的末尾，没有路时再选择回退，即顶点元素出栈。具体过程可以进行如下描述：

> 创建一个访问标记数组visited，并初始化为false，表示此顶点没有被访问  
> 创建栈，将某个元素入栈(这里我们选取的是顶点数组中下标为0的元素)，并将其输出  
> while (!s.empty()) \{ //栈不为空  
> 遍历顶点数组中所有顶点，寻找top元素的邻接点  
> s.top();//得到栈顶元素  
> 可以进行遍历的两个条件  
> 1. !visited\[i\]：没有被访问过  
> 2. g.edge\[top\]\[i\] > 0：顶点与元素之间有边相连  
> 将该节点标记为遍历过  
> 输出  
> 将该元素压栈  
> s.pop();//与栈顶相邻的顶点全部遍历完成时，栈顶元素出栈  
> 销毁访问标记数组visited  
> \}

void DFS(Graph& g)
    {
    	bool* visited = new bool[g.vertexNum];
    	// init
    	for (int i = 0; i < g.vertexNum; ++i)
    	{
    		visited[i] = false;
    	}
    
    	// 从顶点数组中的第一个开始访问
    	stack<int> st;	// int - 顶点数组的下标
    	visited[0] = true;
    	cout << g.vertex[0] << " ";
    	st.push(0);
    
    	while (!st.empty())
    	{
    		// 遍历所有的顶点, 找邻接点 - 栈顶元素对应的邻接点
    		for (int i = 0; i < g.vertexNum; ++i)
    		{
    			// 栈顶元素在顶点数组中的位置
    			int top = st.top();
    			//1.没有被访问过：!visited[i]：以防止“走回头路”
    			//2.在同一条边上：g.edge[top][i] > 0：即以边建立关联的两个节点。·
    			if (!visited[i] && g.edge[top][i] > 0)
    			{
    				// 遍历该顶点
    				visited[i] = true;
    				cout << g.vertex[i] << " ";
    				// 邻接点压栈
    				st.push(i);
    			}
    		}
    		// 栈顶的顶点与其余的顶点组成的边全部判断了一遍
    		st.pop();
    	}
    	delete[] visited;
    }

### 二. 深度优先遍历(Breadth-First Search) ###

从给出节点开始，遍历所有与之有边相连的节点，直到对此类节点全部完成访问。使用了队列进行操作，因为其先进先出的特性，对于首先进入的节点，遍历处所有具有关联关系的节点后才会弹出队列，从而开始遍历第二个加入队列的节点。

因为基本过程与广度优先遍历基本相似，所以就不多作赘述，直接给出以下代码：

void BFS(Graph& g)
    {
    	// 保证顶点不被重复遍历
    	bool* visited = new bool[g.vertexNum];
    	// init
    	for (int i = 0; i < g.vertexNum; ++i)
    	{
    		visited[i] = false;
    	}
    
    	// 找一个顶点, 开始访问 - 0
    	queue<int> q;	// 存储顶点的下标
    	visited[0] = true;
    	cout << g.vertex[0] << " ";
    	q.push(0);
    
    	// 如果队列为空, 遍历完成
    	while (!q.empty())
    	{
    		// 队头顶点的下标值拿出来
    		int front = q.front();
    		// 遍历所有的顶点, 找邻接点
    		for (int i = 0; i < g.vertexNum; ++i)
    		{
    			// 如果没被访问, 并且两顶点互为邻接点
    			if (!visited[i] && g.edge[front][i] > 0)
    			{
    				// 访问,并且入队列
    				visited[i] = true;
    				cout << g.vertex[i] << " ";
    				q.push(i);
    			}
    		}
    		// 所有的邻接点都访问完成,出队列
    		q.pop();
    	}
    	delete[] visited;
    }

### 三. 时间复杂度问题 ###