Shigure_Q 2016-12-03 16:18 采纳率: 50%
浏览 1204
已结题

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

如题,代码如下:
#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条回答

  • threenewbee 2016-12-03 16:30
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB怎么通过柱坐标变换画开口是圆形的旋转抛物面?
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿