求两点之间的所有路径（广度优先与回溯法结合）

本程序很好的解决了两点之间的所有路径问题，无向图、有向图均可。采用广度优先算法和回溯法的结合，将最终结果存放在一个动态二维向量中。并将其打印出来（打印出顺序经过的结点）。运行环境为visual studio 2005或visual studio 2008 ，VC 6.0不行。本人QQ：894738423

#include 
#include < vector >
#include 
using namespace std;

vector> search（ unsignedunsigned ）;
bool Circle（intvector）;

int main（）
{   
	vector>  AllPath;
	unsigned v0v1;
	cin>>v0>>v1;
	AllPath=search（v0v1）;
	cout<<“--------------“;
	cout<<“AllPath:“<	for（unsigned i=0;i	{for（unsigned k=0;k	cout<	cout<	cout<<“---------------“;
	return 0;
}
vector> search（unsigned v0unsigned v1）
{
   	int Adj[6][6]={
		{111111}
		{111111}
		{111111}
		{111111}
		{111111}
		{111111}
	};
	vector temp;
	vector> ADL;//邻接表
	unsigned num=6;
	unsigned ikj;
	for（i=0;i	{
		for（j=0;j		{
			if（Adj[i][j]!=INT_MAX && Adj[i][j]!=0）
		    temp.push_back（j）;
	        
		}
		ADL.push_back（temp）; 
	        temp.clear（）;
    }
    vector>  AllPath;
	vector path;
	vector>  stack; //创建临时的二维栈
	path.push_back（v0）;
	stack.push_back（path）;
	stack.push_back（ADL[v0]）;
	while（ stack.size（） !=1 ）
	{
		int pop=stack[stack.size（）-1].back（）;    
		path.push_back（pop）; 
		if（Circle（poppath））
		{
			path.pop_back（）;
			stack[stack.size（）-1].pop_back（）;  
		}
		else
			if（ pop == v1 ）
			{
				AllPath.push_back（path）;
				path.pop_back（）;
				stack[stack.size（）-1].pop_back（）;
			}
			else
			{
				stack.push_back（ADL[pop]）;
            }

			while（stack[stack.size（）-1].size（）==0&&stack.size（） !=1）
		    {
			 stack.pop_back（）;
			 stack[stack.size（）-1].pop_back（）;
			 path.pop_back（）;
		    }
		}
	
	return AllPath;
}
bool Circle（int popvector path）
{
    for（unsigned i=0;i		if（pop==path[i]）
			return true;
	return false;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1870  2009-06-04 22:50  AllPath.cpp

----------- ---------  ---------- -----  ----

                 1870                    1