在主函數(shù)寫個(gè)小測試是沒問題的呀。下面是源代碼：#include<iostream>using namespace std;#include<queue>class Graph{public: Graph(int v)//創(chuàng)建一個(gè)包含v個(gè)頂點(diǎn)但不包含邊的圖 { this->adjacent = new queue<int>[v]; this->V = v; this->E = 0; } int Vnum()//獲取頂點(diǎn)的數(shù)量 { return this->V; } int Enum()//獲取邊的數(shù)量 { return this->E; } void addEdge(int v, int w)//向圖中增加一條邊 v-w { this->adjacent[v].push(w); this->adjacent[w].push(v); this->E++; } queue<int> adj(int v)//獲取和頂點(diǎn)v相鄰的所有頂點(diǎn) { return this->adjacent[v]; }private: int V;//頂點(diǎn)數(shù)量 int E;//頂點(diǎn)邊數(shù)量 queue<int> *adjacent;};class DepthFirstSearch{public: DepthFirstSearch(Graph G, int s) {//構(gòu)件深度優(yōu)先搜索對象，利用深度優(yōu)先搜索找出G圖中s頂點(diǎn)的所有相同頂點(diǎn) this->marked = new bool[G.Vnum()]; for (int i = 0; i < G.Vnum(); ++i) { marked[i] = false; } this->N = 0; dfs(G, s); } void dfs(Graph G, int v)//利用深度優(yōu)先搜索找出G中v頂點(diǎn)的所有相通頂點(diǎn) { marked[v] = true; int w = G.adj(v).front(); while(!G.adj(v).empty())//找到v隊(duì)列里的內(nèi)容 { if (!marked[w]) { dfs(G, w); } cout << "隊(duì)列大小："<<G.adj(v).size() << endl; G.adj(v).pop(); cout << "隊(duì)列刪除后的大?。?quot;<<G.adj(v).size() << endl; if (G.adj(v).empty() == 1) { break; } w = G.adj(v).front(); } this ->N++;//N加1 的位置放在當(dāng)前節(jié)點(diǎn)變true的時(shí)候 } bool mark(int w)//判斷w與s是否相通 { return marked[w]; } int count() { return N; }private: bool* marked;//索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索 int N;//記錄有多少個(gè)頂點(diǎn)與s頂點(diǎn)相同};void main(){ Graph g(13); g.addEdge(0, 6); g.addEdge(0, 2); g.addEdge(0, 1); g.addEdge(0, 6); g.addEdge(5, 3); g.addEdge(5, 4); g.addEdge(3, 4); g.addEdge(4, 6); g.addEdge(7, 8); g.addEdge(9, 10); g.addEdge(9, 12); g.addEdge(11, 12); g.addEdge(9, 11); DepthFirstSearch *DFS=new DepthFirstSearch(g, 0); int num= DFS->count(); cout << num << endl; /*queue<int> q; for (int i = 0; i < 5; i++) { q.push(i + 1); } cout << q.size() << endl; cout << q.empty() << endl; for (int i = 0; !q.empty(); i++) { q.pop(); } cout << q.size() << endl; cout << q.empty() << endl;*/ system("pause"); return;}
1 回答
臨摹微笑
TA貢獻(xiàn)1982條經(jīng)驗(yàn) 獲得超2個(gè)贊
問題在于你的queue<int> adj(int v) 函數(shù)返回的是一個(gè)queue的拷貝，而不是queue本身。
改成
queue <int>& adj(int v) //獲取和頂點(diǎn)v相鄰的所有頂點(diǎn)
{
return adjacent[v];
}
全部源碼如下：
#include<iostream>
#include<queue>
using namespace std;
class Graph {
public:
Graph(int v) //創(chuàng)建一個(gè)包含v個(gè)頂點(diǎn)但不包含邊的圖
{
this -> adjacent = new queue < int > [v];
this -> V = v;
this -> E = 0;
}
int Vnum() //獲取頂點(diǎn)的數(shù)量
{
return this -> V;
}
int Enum() //獲取邊的數(shù)量
{
return this -> E;
}
void addEdge(int v, int w)
//向圖中增加一條邊 v-w
{
this -> adjacent[v].push(w);
this -> adjacent[w].push(v);
this -> E++;
}
queue <int>& adj(int v) //獲取和頂點(diǎn)v相鄰的所有頂點(diǎn)
{
return adjacent[v];
}
private:
int V; //頂點(diǎn)數(shù)量
int E; //頂點(diǎn)邊數(shù)量
queue < int > * adjacent;
};
class DepthFirstSearch {
public:
DepthFirstSearch(Graph G, int s) { //構(gòu)件深度優(yōu)先搜索對象，利用深度優(yōu)先搜索找出G圖中s頂點(diǎn)的所有相同頂點(diǎn)
this -> marked = new bool[G.Vnum()];
for (int i = 0; i < G.Vnum();
++i) {
marked[i] = false;
}
this -> N = 0;
dfs(G, s);
}
void dfs(Graph G, int v) //利用深度優(yōu)先搜索找出G中v頂點(diǎn)的所有相通頂點(diǎn)
{
marked[v] = true;
int w = G.adj(v).front();
while (!G.adj(v).empty()) //找到v隊(duì)列里的內(nèi)容
{
if (!marked[w]) {
dfs(G, w);
}
cout << "隊(duì)列大小：" << G.adj(v).size() << endl;
G.adj(v).pop();
cout << "隊(duì)列刪除后的大?。?quot; << G.adj(v).size() << endl;
if (G.adj(v).empty() == 1) {
break;
}
w = G.adj(v).front();
}
this -> N++;
//N加1 的位置放在當(dāng)前節(jié)點(diǎn)變true的時(shí)候
}
bool mark(int w) //判斷w與s是否相通
{
return marked[w];
}
int count() {
return N;
}
private: bool * marked; //索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索
int N; //記錄有多少個(gè)頂點(diǎn)與s頂點(diǎn)相同
};
int main() {
Graph g(13);
g.addEdge(0, 6);
g.addEdge(0, 2);
g.addEdge(0, 1);
g.addEdge(0, 6);
g.addEdge(5, 3);
g.addEdge(5, 4);
g.addEdge(3, 4);
g.addEdge(4, 6);
g.addEdge(7, 8);
g.addEdge(9, 10);
g.addEdge(9, 12);
g.addEdge(11, 12);
g.addEdge(9, 11);
DepthFirstSearch * DFS = new DepthFirstSearch(g, 0);
int num = DFS -> count();
cout << num << endl;
return 0;
}
- 1 回答
- 0 關(guān)注
- 103 瀏覽
添加回答
舉報(bào)
0/150
提交
取消