深搜（非递归）实现获取两点之间的路径

曾经终败给现在 2022-05-30 12:08 184阅读 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; 
    	s.push(start);
    	isInStack[start] = 1;  
    
    
    	while(!s.empty()){
    		s_top = s.top();
    
    		n_point = getNextPoint(s_top);
    		if (n_point == end)
    		{
    			cout <<"route: ";
    			for(int i = 0;i < n; i++){   
    				if (isInStack[i] == 1)
    				{
    					cout << i << " ";
    				}
    			} 
    			cout << n_point << 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;
    }