求大佬解答，這是可以輸出一個不連通圖中兩個環的代碼，但是我想把這兩個環的節點分別存到兩個陣列中，我想的是每次深度優先遍歷過以后會得到一個環中的元素然后存到一個陣列中去，應該怎么做呢？因為我想判斷一個點是不是在某個環上，所以怎么去存盤這兩個環，接下來用于我的判斷呢
#include<fstream>
#include <iostream>
using namespace std;
const int MAX_Vertex_Num = 12;
template<class VexType, class ArcType>
class MGraph
{
public:
void CreateGraph();//創建圖
void CheckCircle();
private:
VexType vexs[MAX_Vertex_Num] = { 0,1,2,3,4,5,6,7,8,9,10,11};//頂點向量
ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //這里把鄰接矩陣型別用模板表示，主要是為了處理有權值的情況，比如：權值可以為小數（代價），也可以為整數
int vexnum=12;//頂點數
int arcnum=12;//邊數
private:
void DFS(int x, bool visited[MAX_Vertex_Num], ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]);
};
template<class VexType, class ArcType>
void MGraph<VexType, ArcType>::CreateGraph()
{
int i, j,k;
cout << "頂點數為:"<<vexnum<<endl;
cout << "邊數為:"<<arcnum<<endl;
//初始化鄰接矩陣
for (int i = 0; i < vexnum; i++)
{
vexs[i] = i;
}
ifstream infile;
infile.open("inputdata.txt");
for (i = 0; i < vexnum; i++)
{
for (j = 0; j < vexnum; j++)
{
arcs[i][j] = 0;
}
}
for (k = 0; k < arcnum; k++)
{
infile >> i >> j;
arcs[i][j] = 1;
arcs[j][i] = 1;
}
infile.close();
}
/*
檢查圖中是不是有環
思想：
如果存在回路，則必存在一個子圖，是一個環路。環路中所有頂點的度>=2。
具體演算法：
1、判斷無向圖是不是有環
第一步：統計各個頂點的度
第二步：洗掉所有度<=1的頂點及相關的邊，并將另外與這些邊相關的其它頂點的度減一。一直到圖中結點的度均>=2
如果最后還有未洗掉頂點，則存在環，否則沒有環。
2、輸出環的個數以及每個環中的結點
第一步：得到度均為2的結點后，使用深度遍歷，得到的連通分量個數為環的個數
第二步：每個連通分量就是一個環，連通分量元素就是環中元素
*/
template<class VexType, class ArcType>
void MGraph<VexType, ArcType>::CheckCircle()
{
//引入一個堆疊，專門存放度為1的結點
int top = -1;//初始化堆疊空間，表明堆疊為空
int stack[MAX_Vertex_Num];
//引入一個陣列，存放每一個頂點的度
int degree[MAX_Vertex_Num] = { 0 };
////引入一個臨時的鄰接矩陣，完成之后的處理
//ArcType arcsTemp[MAX_Vertex_Num][MAX_Vertex_Num];
//for (int i = 0; i < vexnum; i++)
//{
// for (int j = 0; j < vexnum; j++)
// {
// arcsTemp[i][j] = arcs[i][j];//臨時的鄰接矩陣跟原矩陣一樣
// }
//}
//統計每個結點的度，并為陣列degree賦值
for (int i = 0; i < vexnum; i++)
{
int count = 0;
for (int j = 0; j < vexnum; j++)
{
if (arcs[i][j] == 1)
{
count++;
}
}
degree[i] = count;
}
//度為1的結點放入堆疊中
for (int i = 0; i < vexnum; i++)
{
if (degree[i] == 1)
{
stack[++top] = i;
}
}
//處理陣列degree中度為1的結點
while (top > -1)
{
int x = stack[top--];
//處理度為1的結點。把與該結點的邊全部刪去
for (int j = 0; j < vexnum; j++)
{
if (arcs[x][j] == 1)//處理行
{
arcs[x][j] = 0;
degree[x]--;//刪去一條邊時，起始頂點和終止頂點的度都減一,由于x是剛出堆疊，--后度為0
}
if (arcs[j][x] == 1)//處理列--無向圖是對稱的，處理行的時候，列也要處理
{
arcs[j][x] = 0;
degree[j]--;
if (degree[j] == 1)
{
stack[++top] = j;
}
}
}
}
//此時鄰接矩陣arcsTemp均為度為2的結點--可用深度遍歷得到每個環中的結點
bool visited[MAX_Vertex_Num] = { false };
int num = 0;
for (int i = 0; i < vexnum; i++)
{
if (visited[i] == false && degree[i] != 0)
{
num++;
cout << endl << "第" << num << "個環中結點為:" << endl;
visited[i] = true;
DFS(i, visited, arcs);
}
}
if (num == 0)
{
cout << "圖中不存在環!" << endl;
}
else
{
cout << endl << "圖中存在" << num << "個環" << endl;
}
}
template<class VexType, class ArcType>
void MGraph<VexType, ArcType>::DFS(int x, bool visited[MAX_Vertex_Num], ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num])
{
cout << vexs[x]<<" ";
for (int j = 0; j < vexnum; j++)
{
if (arcs[x][j] == 1 && visited[j] == false)//此點如果有鄰接點還未訪問那就訪問它，遞回呼叫，深度優先遍歷
{
visited[j] = true;
DFS(j, visited, arcs);
}
}
}
int main()
{
MGraph<int, int> G;
G.CreateGraph();
//cout<<G;
G.CheckCircle();
system("pause");
return 1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/226555.html
標籤：新手樂園