利用队列实现图的深度优先遍历

void DFS_queue(Vertex & TestVertex)
{
	queue<int> Q1;	//创建一个队列来存储节点对应在head的位置
	vector<bool> V1;	//创建一个数组来表示该节点是否被遍历过
	V1.resize(MAXNODE);
	for (int i = 0; i < MAXNODE; i++)//初始化所有节点没有被访问过
	{
		V1[i] = false;
	}
	Q1.push(0);
	int location;
	NODE* NodeMove;
	while (!Q1.empty())
	{
		location = Q1.front();//获取队列的第一个数据值
		NodeMove = TestVertex.head[location].next;
		while (NodeMove != NULL)
		{
			Q1.push(NodeMove->pos);
			NodeMove = NodeMove->next;
		}
		//将第一个出队,如果没有输出过就输出,输出过就直接出队
		if (V1[location] == false)
		{
			cout << " " << TestVertex.head[location].Name;
			V1[location] = true;
			Q1.pop();
		}
		else
		{
			Q1.pop();
		}
	}
}

  

上一篇:剑指offer13--调整数组使奇数在偶数前面


下一篇:Codeforces1477B-Nezzar and Binary String