数据结构 || 图深度优先搜索遍历以及求两点间的简单路径
本文图的存储结构是基于无向图的邻接多重表实现的
图的深度优先搜索的递归遍历
void DFS(AMLGraph G, int i) {
cout << G.adjmulist[i].data << endl;
visit[i] = visited;
for (int w = FirstAdjVex(G, i); w >= 0; w = NextAdjVex(G,i,w)) {
//cout << w << endl;
if (visit[w] == unvisited) {
DFS(G, w);
}
}
}
void DFSTraverse(AMLGraph G) {
for (int i = 0; i < G.vexnum; i++) {
visit[i] = unvisited;
}
for (int i = 0; i < G.vexnum; i++) {
if (visit[i] == unvisited) {
DFS(G, i);
}
}
}
图的深度优先搜索的非递归遍历
void DFStack(AMLGraph G) {
stack<int> a;
for (int i = 0; i < G.vexnum; i++) {
visit[i] = unvisited;
}
for (int i = 0; i < G.vexnum; i++) {
if (visit[i] == unvisited) {
visit[i] = visited;
cout << G.adjmulist[i].data << endl;
a.push(i);
while (!a.empty()) {
int v = a.top();
bool find = false;
for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G,v,w)) {
if (visit[w] == unvisited) {
a.push(w);
visit[w] = visited;
cout << G.adjmulist[w].data << endl;
find = true;
break;
}
}
if (find == false) {
a.pop();
}
}
}
}
}
图的深度优先搜索实现查找两点间的简单路径
int DFSPath(AMLGraph G, string v1, string v2) {
int i1 = LocateVex(G.adjmulist, G.vexnum, v1);
int i2 = LocateVex(G.adjmulist, G.vexnum, v2);
stack<int> a;
list<int> b;
for (int i = 0; i < G.vexnum; i++) {
visit[i] = unvisited;
}
visit[i1] = visited;
a.push(i1);
b.push_back(i1);
if (i1 == i2) {
cout << v1 << endl;
return 1;
}
while (!a.empty()) {
int v = a.top();
bool adjem = false;
for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
if (visit[w] == unvisited) {
a.push(w);
b.push_back(w);
visit[w] = visited;
if (w == i2) {
for (auto iter = b.begin(); iter != b.end(); iter++) {
if (iter == b.begin())
cout << G.adjmulist[(*iter)].data;
else
cout << "->" << G.adjmulist[(*iter)].data;
}
cout << endl;
return 1;
}
adjem = true;
break;
}
}
if (adjem == false) {
a.pop();
b.pop_back();
}
}
cout << "Not Find!" << endl;
return 0;
}
最后附上完整代码:
//无向图的邻接多重表
//深度优先搜索的递归以及非递归实现
//从一节点出发到另一个节点的简单路径
#include <iostream>
#include <stack>
#include <list>
using namespace std;
#define MAX_VERTEX_NUM 20
enum VisitIf {unvisited, visited};
VisitIf visit[MAX_VERTEX_NUM];
class EBox {
public:
VisitIf mark; //访问标记
int ivex, jvex; //该边依附的两个顶点位置
EBox *ilink, *jlink; //分别指向依附这两个顶点的下一条边
};
class VexBox {
public:
string data;
EBox *firstedge; //指向第一条依附该顶点的边
};
class AMLGraph {
public:
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum, edgenum; //无向图的当前顶点数和边数
};
int LocateVex(VexBox adj[], int num, string v) {
for (int i = 0; i < num; i++) {
if (adj[i].data == v) {
return i;
}
}
}
void CreateGraph(AMLGraph *G) {
cout << "请输入顶点数和弧数: " << endl;
cin >> G->vexnum >> G->edgenum;
cout << "请输入顶点: " << endl;
for (int i = 0; i < G->vexnum; i++) {
cin >> G->adjmulist[i].data;
G->adjmulist[i].firstedge = NULL;
}
for (int i = 0; i < G->edgenum; i++) {
cout << "请输入边的两个顶点: " << endl;
string v1, v2;
cin >> v1 >> v2;
int i1 = LocateVex(G->adjmulist, G->vexnum, v1);
int i2 = LocateVex(G->adjmulist, G->vexnum, v2);
//cout << i1 << "...." << i2 << endl;
EBox *p = new EBox;
p->mark = unvisited;
p->ivex = i1;
p->jvex = i2;
p->ilink = G->adjmulist[i1].firstedge;
p->jlink = G->adjmulist[i2].firstedge;
G->adjmulist[i1].firstedge = p;
G->adjmulist[i2].firstedge = p;
}
}
int FirstAdjVex(AMLGraph G, int v) {
int i = v;
if (G.adjmulist[i].firstedge) {
if (G.adjmulist[i].firstedge->ivex == i) {
return G.adjmulist[i].firstedge->jvex;
}
else {
return G.adjmulist[i].firstedge->ivex;
}
}
else
return -1;
}
//v是G中的某个顶点,w是v的邻接顶点
//返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点,则返回空
int NextAdjVex(AMLGraph G, int v, int w) {
int i1 = v;
int i2 = w;
EBox *p = G.adjmulist[i1].firstedge;
while (p) {
if (p->ivex == i1 && p->jvex != i2) {
p = p->ilink;
}
else {
if (p->ivex != i2 && p->jvex == i1) {
p = p->jlink;
}
else {
break;
}
}
}
if (p && p->ivex == i1 && p->jvex == i2) {
p = p->ilink;
if (p&&p->ivex == i1) {
return p->jvex;
}
else if (p&&p->jvex == i1)
return p->ivex;
}
if (p && p->ivex == i2 && p->jvex == i1) {
p = p->jlink;
if (p&&p->ivex == i1) {
return p->jvex;
}
else if (p&&p->jvex == i1)
return p->ivex;
}
return -1;
}
void DFS(AMLGraph G, int i) {
cout << G.adjmulist[i].data << endl;
visit[i] = visited;
for (int w = FirstAdjVex(G, i); w >= 0; w = NextAdjVex(G,i,w)) {
//cout << w << endl;
if (visit[w] == unvisited) {
DFS(G, w);
}
}
}
void DFSTraverse(AMLGraph G) {
for (int i = 0; i < G.vexnum; i++) {
visit[i] = unvisited;
}
for (int i = 0; i < G.vexnum; i++) {
if (visit[i] == unvisited) {
DFS(G, i);
}
}
}
void DFStack(AMLGraph G) {
stack<int> a;
for (int i = 0; i < G.vexnum; i++) {
visit[i] = unvisited;
}
for (int i = 0; i < G.vexnum; i++) {
if (visit[i] == unvisited) {
visit[i] = visited;
cout << G.adjmulist[i].data << endl;
a.push(i);
while (!a.empty()) {
int v = a.top();
bool find = false;
for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G,v,w)) {
if (visit[w] == unvisited) {
a.push(w);
visit[w] = visited;
cout << G.adjmulist[w].data << endl;
find = true;
break;
}
}
if (find == false) {
a.pop();
}
}
}
}
}
int DFSPath(AMLGraph G, string v1, string v2) {
int i1 = LocateVex(G.adjmulist, G.vexnum, v1);
int i2 = LocateVex(G.adjmulist, G.vexnum, v2);
stack<int> a;
list<int> b;
for (int i = 0; i < G.vexnum; i++) {
visit[i] = unvisited;
}
visit[i1] = visited;
a.push(i1);
b.push_back(i1);
if (i1 == i2) {
cout << v1 << endl;
return 1;
}
while (!a.empty()) {
int v = a.top();
bool adjem = false;
for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
if (visit[w] == unvisited) {
a.push(w);
b.push_back(w);
visit[w] = visited;
if (w == i2) {
for (auto iter = b.begin(); iter != b.end(); iter++) {
if (iter == b.begin())
cout << G.adjmulist[(*iter)].data;
else
cout << "->" << G.adjmulist[(*iter)].data;
}
cout << endl;
return 1;
}
adjem = true;
break;
}
}
if (adjem == false) {
a.pop();
b.pop_back();
}
}
cout << "Not Find!" << endl;
return 0;
}
void PrintGraph(AMLGraph G)
{
EBox *p;
for(int i = 0; i < G.vexnum; ++i)
{
p = G.adjmulist[i].firstedge;
while(p != NULL)
{
if(p->ivex == i) //判断相等才能知道连接上的是ivex还是jvex;
{
cout << G.adjmulist[p->ivex].data << "------" << G.adjmulist[p->jvex].data << endl;
//printf("%d--%d\n", G.adjmulist[p->ivex].data, G.adjmulist[p->jvex].data);
p = p->ilink;
}
else
{
cout << G.adjmulist[p->jvex].data << "------" << G.adjmulist[p->ivex].data << endl;
p = p->jlink;
}
}
}
}
int main () {
AMLGraph g;
CreateGraph(&g);
PrintGraph(g);
while (1) {
string v1, v2;
cout << "请输入你想查询的两点: " << endl;
cin >> v1 >> v2;
DFSPath(g, v1, v2);
}
return 0;
}