一、题目
如果BFS的输入图是用邻接矩阵表示的,且对该算法加以修改以处理这种输入图表示,那么该算法的运行时间如何?
二、答案与代码
运行时间为O(n^2),处理方法见代码。
1.Mat_Graph.h
#include <iostream> #include <queue> using namespace std; #define N 100 #define WHITE 0 #define GRAY 1 #define BLACK 2 queue<int> Q; class Mat_Graph { public: int n; int color[N+1]; int d[N+1]; int Pie[N+1]; int Map[N+1][N+1]; Mat_Graph(int num):n(num) { memset(Map, 0, sizeof(Map)); } void AddDoubleEdge(int a, int b, int value = 1) { AddSingleEdge(a, b, value); AddSingleEdge(b, a, value); } void AddSingleEdge(int start, int end, int value = 1) { Map[start][end] = value; } void DeleteDoubleEdge(int a, int b) { DeleteSingleEdge(a, b); DeleteSingleEdge(b, a); } void DeleteSingleEdge(int start, int end) { Map[start][end] = 0; } //22.2-3 void BFS(int s); void Print_Path(int s, int v); }; void Mat_Graph::BFS(int s) { int u, v; for(u = 1; u <= n; u++) { color[u] = WHITE; d[u] = 0x7fffffff; Pie[u] = 0; } color[s] = GRAY; d[s] = 0; Pie[s] = 0; while(!Q.empty())Q.pop(); Q.push(s); while(!Q.empty()) { u = Q.front();Q.pop(); for(v = 1; v <= n; v++) { if(Map[u][v] == 0)continue; if(color[v] == WHITE) { color[v] = GRAY; d[v] = d[u] + 1; Pie[v] = u; Q.push(v); } } color[u] = BLACK; } } void Mat_Graph::Print_Path(int s, int v) { BFS(s); if(v == s) cout << s<<' '; else { if(Pie[v] == 0) cout<<"no path from "<<s<<" to "<<v<<" exists."<<endl; else { Print_Path(s, Pie[v]); cout<<v<<' '; } } }
2.main.cpp
#include <iostream> #include "Mat_Graph.h" using namespace std; /* 1 2 1 5 2 6 6 7 6 3 3 7 3 4 7 8 7 4 4 8 */ int main() { Mat_Graph *G = new Mat_Graph(8); int i = 0, a, b; for(i = 1; i <= 10; i++) { cin>>a>>b; G->AddDoubleEdge(a,b); } G->BFS(2); for(i = 1; i <= 8; i++) cout<<G->d[i]<<' '; cout<<endl; int s, v; while(cin>>s>>v) { G->Print_Path(s, v); cout<<endl; } delete G; return 0; }