C++图利用深度搜索遍历 10C

#include
#include
using namespace std;

const int MAX = 10000;
bool visited[MAX];

class Graph {
private:
int numVertex, numEdge;
int** matrix;
int* mark;
public:
Graph(int numVert) {
int i;
numVertex = numVert;
numEdge = 0;
mark = new int [numVert];
for(int i = 0; i < numVertex; i++) {
mark[i] = 0;
}
matrix = (int**) new int*[numVertex];
for(int i = 0; i < numVertex; i++) {
matrix[i] = new int[numVertex];
}
for(int i = 0; i < numVertex; i++) {
for(int j = 0; j < numVertex; j++) {
matrix[i][j] = 0;
}
}
}
int First(int v) {
int i;
for(i = 0; i < numVertex; i++) {
if(matrix[v][i] != 0) {
return i;
}
}
return i;
}
int Next(int v1, int v2) {
int i;
for(i = v2 + 1; i < numVertex; i++) {
if(matrix[v1][i] != 0) {
return i;
}
}
return i;
}
int n() {
return numVertex;
}
int e() {
return numEdge;
}
void SetEdge(int v1, int v2, int wgt) {
if(wgt < 0) {
cout << "非法数值" << endl;
}
if(matrix[v1][v2] == 0) {
numEdge++;
}
matrix[v1][v2] = wgt;
}
void DeleteEdge(int v1, int v2) {
if(matrix[v1][v2] != 0) {
numEdge--;
}
matrix[v1][v2] = 0;
}
int Weight(int v1, int v2) {
return matrix[v1][v2];
}
int GetMark(int v) {
return mark[v];
}
void SetMark(int v, int val) {
mark[v] = val;
}
};

void PathAll(Graph* g, int u, int v, int* path, string* str, int& d) {
int w, i;
g -> SetMark(u, 1);
d++;
path[d] = u;
if(u == v && d >= 1) {
cout << "这两个城市之间一条简单路径为：";
for(int i = 0; i <= d; i++) {
cout << str[path[i]] << " ";
}
cout << endl;
}
for(w = g -> First(u); w < g -> n(); w = g -> Next(u, w)) {
if(g -> GetMark(w) == 0) {
PathAll(g, w, v, path, str, d);
}
}
g -> SetMark(u, 0);
d--;
}

int main() {
int n;
string* str;
int* path;
cout << "请输入城市个数：" << endl;
cin >> n;
if(n <= 0) {
cout << "错误" << endl;
}
else {
Graph g(n);
str = new string[n];
path = new int[n];
cout << "请输入城市编号：" << endl;
for(int i = 0; i < n; i++) {
cin >> str[i];
int j = 0;
while(j != i) {
if(str[j++] == str[i]) {
cout << "输入重复，请重新输入" << endl;
i--;
break;
}
}
}
cout << "请输入高速公路（编号 编号 字符），当字符为Q时结束：" << endl;
int V1 = -1, V2 = -1;
char c;
string str1, str2;
while(c != 'Q') {
cin >> str1 >> str2 >> c;
for(int i = 0; i < n; i++) {
if(str1 == str[i]) {
V1 = i;
}
if(str2 == str[i]) {
V2 = i;
}
}
if(V1 != -1 && V2 != -1 && V1 != V2) {
g.SetEdge(V1, V2, 1);
g.SetEdge(V2, V1, 1);
}
else {
cout << "输入错误，请重新输入" << endl;
}
}
cout << "输入需要搜索的两城市编号：" << endl;
cin >> str1 >> str2;
for(int i = 0; i < n; i++) {
if(str1 == str[i]) {
V1 = i;
}
if(str2 == str[i]) {
V2 = i;
}
}
int* num = new int[n];
int d = -1;
PathAll(&g, V1, V2, num, str, d);
if(d == 0) {
cout << "两城市间无简单路径" << endl;
}
}
return 0;
}

2个回答