C++計算圖任意兩點間的所有路徑
基于連通圖，鄰接矩陣實現(xiàn)的圖，非遞歸實現(xiàn)。
算法思想：
設置兩個標志位，①該頂點是否入棧，②與該頂點相鄰的頂點是否已經(jīng)訪問。
A 將始點標志位①置1，將其入棧
B 查看棧頂節(jié)點V在圖中，有沒有可以到達、且沒有入棧、且沒有從這個節(jié)點V出發(fā)訪問過的節(jié)點
C 如果有，則將找到的這個節(jié)點入棧，這個頂點的標志位①置1，V的對應的此頂點的標志位②置1
D 如果沒有，V出棧，并且將與v相鄰的全部結點設為未訪問，即全部的標志位②置0
E 當棧頂元素為終點時，設置終點沒有被訪問過，即①置0，打印棧中元素，彈出棧頂節(jié)點
F 重復執(zhí)行B – E,直到棧中元素為空
先舉一個例子吧
假設簡單連通圖如圖1所示。假設我們要找出結點3到結點6的所有路徑，那么，我們就設結點3為起點，結點6為終點。找到結點3到結點6的所有路徑步驟如下：
1、 我們建立一個存儲結點的棧結構，將起點3入棧，將結點3標記為入棧狀態(tài)；
2、 從結點3出發(fā)，找到結點3的第一個非入棧沒有訪問過的鄰結點1，將結點1標記為入棧狀態(tài)，并且將3到1標記為已訪問；
3、 從結點1出發(fā)，找到結點1的第一個非入棧沒有訪問過的鄰結點0，將結點0標記為入棧狀態(tài)，并且將1到0標記為已訪問；
4、 從結點0出發(fā)，找到結點0的第一個非入棧沒有訪問過的鄰結點2，將結點2標記為入棧狀態(tài)，并且將0到2標記為已訪問；
5、 從結點2出發(fā)，找到結點2的第一個非入棧沒有訪問過的鄰結點5，將結點5標記為入棧狀態(tài)，并且將2到5標記為已訪問；
6、 從結點5出發(fā)，找到結點5的第一個非入棧沒有訪問過的鄰結點6，將結點6標記為入棧狀態(tài)，并且將5到6標記為已訪問；
7、 棧頂結點6是終點，那么，我們就找到了一條起點到終點的路徑，輸出這條路徑；
8、 從棧頂彈出結點6，將6標記為非入棧狀態(tài)；
9、 現(xiàn)在棧頂結點為5，結點5沒有非入棧并且非訪問的結點，所以從棧頂將結點5彈出，并且將5到6標記為未訪問；
10、 現(xiàn)在棧頂結點為2，結點2的相鄰節(jié)點5已訪問，6滿足非入棧，非訪問，那么我們將結點6入棧；
11、 現(xiàn)在棧頂為結點6，即找到了第二條路徑，輸出整個棧，即為第二條路徑
12、 重復步驟8-11，就可以找到從起點3到終點6的所有路徑；
13、 棧為空，算法結束。
下面講一下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類，便于遍歷全部的結點
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); //清空入棧的標志位
}
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
C++代碼和可執(zhí)行程序在x86和arm上的區(qū)別介紹
這篇文章主要介紹了C++代碼和可執(zhí)行程序在x86和arm上的區(qū)別,X86和ARM是占據(jù)CPU市場的兩大處理器，各有優(yōu)劣，本文給大家詳細介紹了兩者的區(qū)別，需要的朋友可以參考下2022-07-07
這篇文章主要為大家詳細介紹了C++控制臺實現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
本文主要介紹了VisualStudio2022缺少項目模板的解決辦法,如果模板未能在開發(fā)環(huán)境中加載,可通過多種方法查找問題,下面就來介紹一下,感興趣的可以了解一下2024-06-06
言前后最好空一格[編程風格的問題，按你自已的喜好，適合自已就最好]。斷言只是用來檢查程序的邏輯正確性，不能代替條件替換。斷言比printf語句這種形式的打印好使2013-09-09
這篇文章主要介紹了C++成員初始化列表，除了可以使用構造函數(shù)對類成員進行初始化之外，C++還提供了另外一種初始化的方法，叫做成員初始化列表。下面來看看文章的詳細吧,需要的朋友可以參考一下2022-01-01
這篇文章主要介紹了C語言數(shù)據(jù)結構之模式匹配字符串定位問題的相關資料,希望通過本文能幫助到大家，讓大家理解這部分內容，需要的朋友可以參考下2017-10-10
這篇文章主要為大家詳細介紹了C++實現(xiàn)分數(shù)計算器，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要對C++基礎知識實例解析，通過四個簡短的案例，鞏固大家的基礎知識，需要的朋友可以參考下2015-08-08
本篇文章是對生成隨機數(shù)rand函數(shù)的用法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
VTK8.1?在?Qt5.9?環(huán)境下的配置編譯和安裝過程
為了實現(xiàn)realsense的PCL點云顯示，需要VTK支持。由于整個平臺在Qt環(huán)境實現(xiàn)，VTK編譯為Qt插件。整個過程并不復雜，網(wǎng)上的文章大多不全，自己梳理了一下，分享出來,需要的朋友可以參考下2022-07-07