C++計算圖任意兩點間的所有路徑

更新時間：2017年10月26日 16:47:48 作者：矮油~

這篇文章主要為大家詳細介紹了C++求圖任意兩點間的所有路徑，具有一定的參考價值，感興趣的小伙伴們可以參考一下

基于連通圖，鄰接矩陣實現(xiàn)的圖，非遞歸實現(xiàn)。

算法思想：

設(shè)置兩個標(biāo)志位，①該頂點是否入棧，②與該頂點相鄰的頂點是否已經(jīng)訪問。

A 將始點標(biāo)志位①置1，將其入棧

B 查看棧頂節(jié)點V在圖中，有沒有可以到達、且沒有入棧、且沒有從這個節(jié)點V出發(fā)訪問過的節(jié)點

C 如果有，則將找到的這個節(jié)點入棧，這個頂點的標(biāo)志位①置1，V的對應(yīng)的此頂點的標(biāo)志位②置1

D 如果沒有，V出棧，并且將與v相鄰的全部結(jié)點設(shè)為未訪問，即全部的標(biāo)志位②置0

E 當(dāng)棧頂元素為終點時，設(shè)置終點沒有被訪問過，即①置0，打印棧中元素，彈出棧頂節(jié)點

F 重復(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標(biāo)記為入棧狀態(tài)；
2、從結(jié)點3出發(fā)，找到結(jié)點3的第一個非入棧沒有訪問過的鄰結(jié)點1，將結(jié)點1標(biāo)記為入棧狀態(tài)，并且將3到1標(biāo)記為已訪問；
3、從結(jié)點1出發(fā)，找到結(jié)點1的第一個非入棧沒有訪問過的鄰結(jié)點0，將結(jié)點0標(biāo)記為入棧狀態(tài)，并且將1到0標(biāo)記為已訪問；
4、從結(jié)點0出發(fā)，找到結(jié)點0的第一個非入棧沒有訪問過的鄰結(jié)點2，將結(jié)點2標(biāo)記為入棧狀態(tài)，并且將0到2標(biāo)記為已訪問；
5、從結(jié)點2出發(fā)，找到結(jié)點2的第一個非入棧沒有訪問過的鄰結(jié)點5，將結(jié)點5標(biāo)記為入棧狀態(tài)，并且將2到5標(biāo)記為已訪問；
6、從結(jié)點5出發(fā)，找到結(jié)點5的第一個非入棧沒有訪問過的鄰結(jié)點6，將結(jié)點6標(biāo)記為入棧狀態(tài)，并且將5到6標(biāo)記為已訪問；
7、棧頂結(jié)點6是終點，那么，我們就找到了一條起點到終點的路徑，輸出這條路徑；
8、從棧頂彈出結(jié)點6，將6標(biāo)記為非入棧狀態(tài)；
9、現(xiàn)在棧頂結(jié)點為5，結(jié)點5沒有非入棧并且非訪問的結(jié)點，所以從棧頂將結(jié)點5彈出，并且將5到6標(biāo)記為未訪問；
10、        現(xiàn)在棧頂結(jié)點為2，結(jié)點2的相鄰節(jié)點5已訪問，6滿足非入棧，非訪問，那么我們將結(jié)點6入棧；
11、        現(xiàn)在棧頂為結(jié)點6，即找到了第二條路徑，輸出整個棧，即為第二條路徑
12、        重復(fù)步驟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(); //與該頂點相鄰的頂點全被標(biāo)記為未訪問 
 void setIsin(bool);//標(biāo)記該頂點是否入棧 
 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); //標(biāo)記為已入棧 
int path_num=0; 
while (!stack.isEmpty()) //判斷棧是否空 
{ 
  
 int flag=vertex[stack.peek()].getOne(); //得到相鄰的頂點 
 if (flag==-1) //如果相鄰頂點全部訪問過 
 { 
  int pop=stack.pop(); //棧彈出一個元素 
  vertex[pop].resetFlag(); //該頂點相鄰的頂點標(biāo)記為未訪問 
  vertex[pop].setIsin(false); //該頂點標(biāo)記為未入棧 
  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); //清空入棧的標(biāo)志位 
 } 
  
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: