1、神秘国度
2、实现代码
递归版本：
//神秘国度的爱情故事#include <iostream>using namespace std;#define MVNum 500 //最大顶点数typedef int VerTexType;//假设顶点的数据类型为字符型 typedef int ArcType; //假设边的权值类型为整型 //-------------图的邻接矩阵-----------------typedef struct {VerTexType *vexs = new int[MVNum]; //顶点表ArcType **arcs = new int*[MVNum];//邻接矩阵 int vexnum;//图的当前点数}Graph;void pp(Graph &G) {for (int i = 0; i < MVNum; i++) {G.arcs[i] = new int[MVNum];}}bool *visited = new bool[MVNum]; //访问标志数组，其初值为"false" int isc, isb,tc= 0;//int back;//确定点v在G中的位置int LocateVex(Graph G, VerTexType v) {for (int i = 0; i < G.vexnum; ++i)if (G.vexs[i] == v)return i;return -1;}//采用邻接矩阵表示法，创建无向网Gvoid CreateUDN(Graph &G) {int i, j, k;cout << "请输入神秘国度里村子的个数";cin >> G.vexnum;//输入总顶点数，总边数cout << endl;for (int i = 0; i < G.vexnum; ++i)//初始化点的信息G.vexs[i] = i;for (int i = 0; i < G.vexnum; ++i)//初始化邻接矩阵，边的权值均置为0for (int j = 0; j < G.vexnum; ++j)G.arcs[i][j] = 0;cout << "输入边依附的顶点，如a b" << endl;for (k = 0; k < G.vexnum - 1; ++k) {//构造邻接矩阵 VerTexType v1, v2;cout << "请输入第" << (k + 1) << "条边依附的顶点:";cin >> v1 >> v2;//输入一条边依附的顶点及权值i = LocateVex(G, v1); j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标 G.arcs[j][i] = G.arcs[i][j] = 1;//置<v1, v2>的对称边<v2, v1>的权值为w }}//从第v个顶点出发递归地深度优先遍历图Gvoid DFS(Graph G, int v, int b){visited[v] = true;for (int j = 0; j < G.vexnum; j++){if (G.arcs[v][j] == 1 && visited[j] == false) //这里可以获得V未访问过的邻接点{if (j == b) {isc = 1; }else {DFS(G, j, b); tc = 1; }}}}void DFSTraverse(Graph G, int a, int b, int c) {int v = a;visited[v] = true;for (int j = 0; j < G.vexnum; j++){if (G.arcs[v][j] == 1 && visited[j] == false) //这里可以获得V未访问过的邻接点{if (j == b&&tc==0) {cout << "no" << endl; isb = 1; }else if (!isb){if (j == c) {//back = path[num--];DFS(G, c, b);if (isc) cout << "yes";else cout << "no";}else DFSTraverse(G, j, b, c);}}}}int main() {Graph G;pp(G);CreateUDN(G);for (int v = 0; v < G.vexnum; v++)visited[v] = false; //刚开始都没有被访问过cout << endl;cout << "无向图G创建完成！" << endl << endl;cout << "请分别输入A,B,C村子的编号，用空格隔开" << endl;int a, b, c;cin >> a >> b >> c;DFSTraverse(G, a, b, c);cout << endl;delete[] G.vexs;delete[] visited;for (int i = 0; i < MVNum; i++)delete[] G.arcs[i];system("pause");}
优化后的非递归算法：
#include "pch.h"//神秘国度的爱情故事#include <iostream>using namespace std;#define MVNum 500 //最大顶点数typedef int VerTexType;//假设顶点的数据类型为字符型 typedef int ArcType; //假设边的权值类型为整型 //-------------图的邻接矩阵-----------------typedef struct {VerTexType *vexs = new int[MVNum]; //顶点表ArcType **arcs = new int*[MVNum];//邻接矩阵 int vexnum;//图的当前点数}Graph;void pp(Graph &G) {for (int i = 0; i < MVNum; i++) {G.arcs[i] = new int[MVNum];}}int *stacks = new int[MVNum];bool *visited = new bool[MVNum]; //访问标志数组，其初值为"false" //int num = 0;//int path[50];int back;//确定点v在G中的位置int LocateVex(Graph G, VerTexType v) {for (int i = 0; i < G.vexnum; ++i)if (G.vexs[i] == v)return i;return -1;}//采用邻接矩阵表示法，创建无向网Gvoid CreateUDN(Graph &G) {int i, j, k;cout << "请输入神秘国度里村子的个数";cin >> G.vexnum;//输入总顶点数，总边数cout << endl;for (int i = 0; i < G.vexnum; ++i)//初始化点的信息G.vexs[i] = i;for (int i = 0; i < G.vexnum; ++i)//初始化邻接矩阵，边的权值均置为0for (int j = 0; j < G.vexnum; ++j)G.arcs[i][j] = 0;cout << "输入边依附的顶点，如a b" << endl;for (k = 0; k < G.vexnum - 1; ++k) {//构造邻接矩阵 VerTexType v1, v2;cout << "请输入第" << (k + 1) << "条边依附的顶点:";cin >> v1 >> v2;//输入一条边依附的顶点及权值i = LocateVex(G, v1); j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标 G.arcs[j][i] = G.arcs[i][j] = 1;//置<v1, v2>的对称边<v2, v1>的权值为w }}void DFS_C(Graph &G, int v, int b,int top){int tag = 0;while (top != -1){v = stacks[top];int tmp = 0;if (v == back) break;for (int i = 1; i <= G.vexnum; i++){if (G.arcs[v][i] == 1 && !visited[i]){if (i== b){tag = 1;for (int j = 0; j <=top; j++) cout << stacks[j] << " ";cout << b << endl;cout << "yes" << endl;break;}else{visited[i] = true;stacks[++top] = i;break;}}tmp = i;}if (tmp >= G.vexnum)top--;if (tag== 1) break;}}//从第v个顶点出发递归地深度优先遍历图Gvoid DFS(Graph &G, int v,int b,int c){for (int i = 0; i <= G.vexnum; i++)//数组从0开始遍历visited[i] = false; int top = -1;visited[v] = true;stacks[++top] = v;int tag = 0;while (top!=-1){v = stacks[top];//取栈顶元素 int tmp = 0;for (int i = 1; i <= G.vexnum; i++){if (G.arcs[v][i] == 1 && !visited[i]){if (i == b){tag = 1;cout << "no"; break;}else{visited[i] = true;stacks[++top] = i;if(i == c){DFS_C(G,c,b,top);int j = top--;back = stacks[j];}break;}}tmp = i;} if (tmp >= G.vexnum) top--;if (tag == 1) break;} }int main() {Graph G;pp(G);CreateUDN(G);for (int v = 0; v < G.vexnum; v++)visited[v] = false; //刚开始都没有被访问过cout << endl;cout << "无向图G创建完成！" << endl << endl;cout << "请分别输入A,B,C村子的编号，用空格隔开" << endl;int a, b, c;cin >> a >> b >> c;DFS(G, a, b, c);cout << endl;delete[] G.vexs;delete[] visited;for (int i = 0; i < MVNum; i++)delete[] G.arcs[i];delete[] stacks;system("pause");}
