非递归求两点之间的路径（无向图）

短命女 2022-05-30 12:09 180阅读 0赞

// dfs.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    #include <iostream>  
    #include <stack>  
    #include <map>
    #include <vector>
    using namespace std; 
    
    #define NotFound  -1  
    #define StartNode 0  
    #define EndNode 4
    map<int,map<int,int>> visited;
    map<int,vector<int>> ajdTable;
    int isInStack[5];
    
    
    //不在栈中且路径没有访问过
    int getNextPoint(int point){
    	vector<int>::iterator it;
    	for ( it=ajdTable[point].begin() ; it != ajdTable[point].end(); it++ ){
    		if ((visited[point][*it]!=1) && (*it == EndNode))
    			return *it;
    
    		if ((visited[point][*it]!=1) && (isInStack[*it]!=1))
    			return *it;
    	}
    	return NotFound;
    }
    
    void setNoVisted(int point){
    	vector<int>::iterator it;
    	for ( it=ajdTable[point].begin() ; it != ajdTable[point].end(); it++ ){
    		visited[point][*it] = 0;
    	}
    }
    
    
    void dfs_stack(int start, int end, int n){
    	int s_top,n_point;  
    
    	for(int i = 0;i < n; i++){   
    		isInStack[i] = 0;
    	}  
     
    	cout<<"begin to find: " << endl;  
    	stack <int> s; 
    	stack<int> s_tmp;
    	s.push(start);
    	isInStack[start] = 1;  
    
    
    	while(!s.empty()){
    		s_top = s.top();
    
    		n_point = getNextPoint(s_top);
    		if (n_point == end)
    		{
    			//输出栈中元素
    			s_tmp = s;
    			cout <<"route: " <<  n_point << " ";
    			while (!s_tmp.empty())
    			{
    				cout << s_tmp.top() << " ";
    				s_tmp.pop();
    			}
    			cout << endl;
    
    			visited[s_top][n_point] = 1;
    			//下一个邻接点
    			n_point = getNextPoint(s_top);
    			if(-1 == n_point)
    			{
    				s.pop();
    				cout<<"pop :"<< s_top << endl; 
    				setNoVisted(s_top);
    				isInStack[s_top] = 0;
    			}else{
    				s.push(n_point); 
    				cout<<"push:"<< n_point << endl; 
    				isInStack[n_point] = 1;
    				visited[s_top][n_point] = 1;
    			}
    
    		}else if(-1 != n_point){
    			s.push(n_point); 
    			cout<<"push:"<< n_point << endl; 
    			isInStack[n_point] = 1;
    			visited[s_top][n_point] = 1;
    		}else{
    			s.pop();
    			cout<<"pop :"<< s_top << endl; 
    			setNoVisted(s_top);
    			isInStack[s_top] = 0;
    		}
    	}
    
    }
    
    //寻找从起点0到终点4的所有路径
    int _tmain(int argc, _TCHAR* argv[])
    {
    	visited[0][1] = 0;
        visited[1][0] = 0;
    	visited[0][2] = 0;
    	visited[2][0] = 0;
    	visited[1][4] = 0;
    	visited[4][1] = 0;
    	visited[3][4] = 0;
    	visited[4][3] = 0;
    	visited[3][2] = 0;
    	visited[2][3] = 0;
    	visited[0][3] = 0;
    	visited[3][0] = 0;
    
    	vector<int> tempvector;
       //0
    	tempvector.push_back(1);
    	tempvector.push_back(2);
    	tempvector.push_back(3);
    	ajdTable[0] = tempvector;
    	tempvector.clear();
       //1
    	tempvector.push_back(0);
    	tempvector.push_back(4);
    	ajdTable[1] = tempvector;
    	tempvector.clear();
    	//2
    	tempvector.push_back(0);
    	tempvector.push_back(3);
    	ajdTable[2] = tempvector;
    	tempvector.clear();
    	//3
    	tempvector.push_back(0);
    	tempvector.push_back(2);
    	tempvector.push_back(4);
    	ajdTable[3] = tempvector;
    	tempvector.clear();
    	//4
    	tempvector.push_back(1);
    	tempvector.push_back(3);
    	ajdTable[4] = tempvector;
    	tempvector.clear();
    
    	dfs_stack(StartNode, EndNode, (int)ajdTable.size());  
    	return 0;
    }