基于連通圖，鄰接矩陣實現(xiàn)的圖，非遞歸實現(xiàn)。
算法思想：
設(shè)置兩個標志位，①該頂點是否入棧，②與該頂點相鄰的頂點是否已經(jīng)訪問。
A 將始點標志位①置1，將其入棧
B 查看棧頂節(jié)點V在圖中，有沒有可以到達、且沒有入棧、且沒有從這個節(jié)點V出發(fā)訪問過的節(jié)點
C 如果有，則將找到的這個節(jié)點入棧，這個頂點的標志位①置1，V的對應(yīng)的此頂點的標志位②置1
D 如果沒有，V出棧，并且將與v相鄰的全部結(jié)點設(shè)為未訪問，即全部的標志位②置0
E 當棧頂元素為終點時，設(shè)置終點沒有被訪問過，即①置0，打印棧中元素，彈出棧頂節(jié)點
F 重復執(zhí)行B – E,直到棧中元素為空
先舉一個例子吧
假設(shè)簡單連通圖如圖1所示。假設(shè)我們要找出結(jié)點3到結(jié)點6的所有路徑，那么，我們就設(shè)結(jié)點3為起點，結(jié)點6為終點。找到結(jié)點3到結(jié)點6的所有路徑步驟如下：
1、 我們建立一個存儲結(jié)點的棧結(jié)構(gòu)，將起點3入棧，將結(jié)點3標記為入棧狀態(tài)；
2、 從結(jié)點3出發(fā)，找到結(jié)點3的第一個非入棧沒有訪問過的鄰結(jié)點1，將結(jié)點1標記為入棧狀態(tài)，并且將3到1標記為已訪問；
3、 從結(jié)點1出發(fā)，找到結(jié)點1的第一個非入棧沒有訪問過的鄰結(jié)點0，將結(jié)點0標記為入棧狀態(tài)，并且將1到0標記為已訪問；
4、 從結(jié)點0出發(fā)，找到結(jié)點0的第一個非入棧沒有訪問過的鄰結(jié)點2，將結(jié)點2標記為入棧狀態(tài)，并且將0到2標記為已訪問；
5、 從結(jié)點2出發(fā)，找到結(jié)點2的第一個非入棧沒有訪問過的鄰結(jié)點5，將結(jié)點5標記為入棧狀態(tài)，并且將2到5標記為已訪問；
6、 從結(jié)點5出發(fā)，找到結(jié)點5的第一個非入棧沒有訪問過的鄰結(jié)點6，將結(jié)點6標記為入棧狀態(tài)，并且將5到6標記為已訪問；
7、 棧頂結(jié)點6是終點，那么，我們就找到了一條起點到終點的路徑，輸出這條路徑；
8、 從棧頂彈出結(jié)點6，將6標記為非入棧狀態(tài)；
9、 現(xiàn)在棧頂結(jié)點為5，結(jié)點5沒有非入棧并且非訪問的結(jié)點，所以從棧頂將結(jié)點5彈出，并且將5到6標記為未訪問；
10、 現(xiàn)在棧頂結(jié)點為2，結(jié)點2的相鄰節(jié)點5已訪問，6滿足非入棧，非訪問，那么我們將結(jié)點6入棧；
11、 現(xiàn)在棧頂為結(jié)點6，即找到了第二條路徑，輸出整個棧，即為第二條路徑
12、 重復步驟8-11，就可以找到從起點3到終點6的所有路徑；
13、 棧為空，算法結(jié)束。
下面講一下C++代碼實現(xiàn)
圖類，基于鄰接矩陣，不詳細的寫了 ==
class Graph { private: CArray<DataType,DataType> Vertices; int Edge[MaxVertices][MaxVertices]; int numOfEdges; public: Graph(); ~Graph(); void InsertVertex(DataType Vertex); void InsertEdge(int v1,int v2,int weight); int GetWeight(int i,int j); int GetVertices(); DataType GetValue(int i); };首先自己寫一個簡單的“棧類”，由于新增了些方法所以不完全叫棧
template<class T> class Stack { private: int m_size; int m_maxsize; T* data; public: Stack(); ~Stack(); void push(T data); //壓棧 T pop(); //出棧，并返回彈出的元素 T peek(); //查看棧頂元素 bool isEmpty(); //判斷是否空 int getSize(); //得到棧的中元素個數(shù) T* getPath(); //返回棧中所有元素 }; template<class T> Stack<T>::Stack() { m_size=0; m_maxsize=100; data=new T[m_maxsize]; } template<class T> Stack<T>::~Stack() { delete []data; } template<class T> T Stack<T>::pop() { m_size--; return data[m_size]; } template<class T> void Stack<T>::push(T d) { if (m_size==m_maxsize) { m_maxsize=2*m_maxsize; T* new_data=new T[m_maxsize]; for (int i=0;i<m_size;i++) { new_data[i]=data[i]; } delete []data; data=new_data; } data[m_size]=d; m_size++; } template<class T> T Stack<T>::peek() { return data[m_size-1]; } template<class T> bool Stack<T>::isEmpty() { if (m_size==0) { return TRUE; } else { return FALSE; } } template<class T> T* Stack<T>::getPath() { T* path=new T[m_size]; for (int i=0;i<m_size;i++) { path[i]=data[i]; } return path; } template<class T> int Stack<T>::getSize() { return m_size; } Vertex類，便于遍歷全部的結(jié)點
class CVertex { private: int m_num;//保存與該頂點相鄰的頂點個數(shù) int *m_nei; //與該頂點相鄰的頂點序號 int *m_flag; //與該頂點相鄰的頂點是否訪問過 bool isin; //該頂點是否入棧 public: CVertex(); void Initialize(int num,int a[]); int getOne(); //得到一個與該頂點相鄰的頂點 void resetFlag(); //與該頂點相鄰的頂點全被標記為未訪問 void setIsin(bool);//標記該頂點是否入棧 bool isIn(); //判斷該頂點是否入棧 void Reset();//將isin和所有flag置0 ~CVertex(); };CVertex::CVertex() { m_num=SIZE; m_nei=new int[m_num]; m_flag=new int[m_num]; isin=false; for (int i=0;i<m_num;i++) { m_flag[i]=0; } } void CVertex::Initialize(int num,int a[]) { m_num=num; for (int i=0;i<m_num;i++) { m_nei[i]=a[i]; } } CVertex::~CVertex() { delete []m_nei; delete []m_flag; } int CVertex::getOne() { int i=0; for (i=0;i<m_num;i++) { if (m_flag[i]==0) //判斷是否訪問過 { m_flag[i]=1; //表示這個頂點已經(jīng)被訪問，并將其返回 return m_nei[i]; } } return -1; //所有頂點都已訪問過則返回-1 } void CVertex::resetFlag() { for (int i=0;i<m_num;i++) { m_flag[i]=0; } } void CVertex::setIsin(bool a) { isin=a; } bool CVertex::isIn() { return isin; } void CVertex::Reset() { for (int i=0;i<m_num;i++) { m_flag[i]=0; } isin=false; } 初始化頂點類
int a[SIZE],num; for ( i=0;i<SIZE;i++) { num=0; for (int j=0;j<SIZE;j++) { if (m_graph.Edge[i][j]!=MaxWeight&&i!=j) { a[num]=j; num++; } } vertex[i].Initialize(num,a); 算法實現(xiàn)（由于是基于MFC實現(xiàn)，所有下邊的代碼不可以直接使用）
stack.push(selection1); //將起點壓棧 vertex[selection1].setIsin(true); //標記為已入棧 int path_num=0; while (!stack.isEmpty()) //判斷棧是否空 { int flag=vertex[stack.peek()].getOne(); //得到相鄰的頂點 if (flag==-1) //如果相鄰頂點全部訪問過 { int pop=stack.pop(); //棧彈出一個元素 vertex[pop].resetFlag(); //該頂點相鄰的頂點標記為未訪問 vertex[pop].setIsin(false); //該頂點標記為未入棧 continue; //取棧頂?shù)南噜徆?jié)點 } if (vertex[flag].isIn()) //若已經(jīng)在棧中，取下一個頂點 { continue; } if (stack.getSize()>maxver-1) //判斷棧中個數(shù)是否超過了用戶要求的 ，這里是限制了一條路徑節(jié)點的最大個數(shù) { int pop=stack.pop(); vertex[pop].resetFlag(); vertex[pop].setIsin(false); continue; } stack.push(flag); //將該頂點入棧 vertex[flag].setIsin(true); //記為已入棧 if (stack.peek()==selection2) //如果棧頂已經(jīng)為所求，將此路徑記錄 { int *path=stack.getPath(); //保存路徑的代碼省略 int pop=stack.pop(); //將其彈出，繼續(xù)探索 vertex[pop].setIsin(false); //清空入棧的標志位 } }以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網(wǎng)。
新聞熱點
疑難解答
