好贷网好贷款

数据结构——深度优先搜索求点到点的一般路径

发布时间:2016-12-3 3:57:05 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"数据结构——深度优先搜索求点到点的一般路径",主要涉及到数据结构——深度优先搜索求点到点的一般路径方面的内容,对于数据结构——深度优先搜索求点到点的一般路径感兴趣的同学可以参考一下。

#include <iostream> using namespace std; #include <stdio.h> #include <stdlib.h> #define OK 1 #define NULL 0 #define MAX_VERTEX_NUM 20 // 最大顶点数 typedef char VertexType; typedef int VRType; typedef int InforType; typedef struct ArcNode { int adjvex; //该边所指的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针 //int weight; //边的权 }ArcNode; //表的结点 typedef struct VNode { VertexType data; //顶点信息(如数据等) ArcNode *firstarc; //指向第一条依附该顶点的边的弧指针 }VNode, AdjList[MAX_VERTEX_NUM]; //头结点 typedef struct ALGraph { AdjList vertices; int visited[MAX_VERTEX_NUM]; //访问标志数组 int vexnum, arcnum; //图的当前顶点数和弧数 }ALGraph; //初始化图 void init_ALGraph(ALGraph &g) { for(int i=0;i<MAX_VERTEX_NUM;i++) g.visited[i]=0; //访问标志数组置0,表示没有被访问 g.vexnum=0; g.arcnum=0; } //返回顶点v在顶点向量中的位置 int LocateVex(ALGraph &G, char v) { int i; for(i = 0; v != G.vertices[i].data && i < G.vexnum; i++) ; return i; } //增加节点 void add_vex(ALGraph &G) { cout<<"输入无向图顶点数: "<<endl; cin>>G.vexnum; //getchar(); //吃回车 cout<<"输入顶点信息:"<<endl; for(int i = 0; i < G.vexnum; i++) { cin>>G.vertices[i].data; //构造顶点向量 G.vertices[i].firstarc = NULL; //getchar(); } } //增加边 void add_arc(ALGraph &G) { ArcNode *s, *t; ArcNode *p; cout<<"输入无向图边数: "<<endl; cin>>G.arcnum; char v1, v2; cout<<"输入边信息:"<<endl; for(int k = 0; k < G.arcnum; k++) { cin>>v1>>v2; int i = LocateVex(G, v1); int j = LocateVex(G, v2); //确定v1 , v2在G中的位置 s = (ArcNode*) malloc (sizeof(ArcNode)); t = (ArcNode*) malloc (sizeof(ArcNode)); s->adjvex = j; //该边所指向的顶点的位置为j s->nextarc = NULL; if(!G.vertices[i].firstarc) { G.vertices[i].firstarc=s; } else { for(p = G.vertices[i].firstarc; p->nextarc; p = p->nextarc) ; p->nextarc=s; } t->adjvex = i; //该边所指向的顶点的位置为j t->nextarc = NULL; if(!G.vertices[j].firstarc) { G.vertices[j].firstarc=t; } else { for(p = G.vertices[j].firstarc; p->nextarc; p = p->nextarc) ; p->nextarc=t; } } } //构造邻接链表 void CreateUDN(ALGraph &G) { add_vex(G); //增加节点 add_arc(G); //增加边 } void PrintAdjList(ALGraph &G) { int i; ArcNode *p; cout<<"编号 顶点 邻点编号"<<endl; for(i = 0; i < G.vexnum; i++) { cout<<" "<<i<<" "<<G.vertices[i].data<<" "; for(p = G.vertices[i].firstarc; p; p = p->nextarc) cout<<p->adjvex<<" "; cout<<endl; } } void Visit(ALGraph &g,int i) { cout<<g.vertices[i].data<<" "; g.visited[i]=1; } //深度优先搜索 void DFSTraverse(ALGraph &g,int i) //从第i个顶点开始搜索 { Visit(g,i); ArcNode *p; for(p = g.vertices[i].firstarc; p; p = p->nextarc) if( !g.visited[p->adjvex] ) DFSTraverse(g,p->adjvex); } void DFSearch(ALGraph &g, int i, int s, char path[]) { ArcNode *p; g.visited[i]=1; static int found=0; static int rear=0; //路径数组的尾指针 path[rear++]=g.vertices[i].data; path[rear]='\0'; //注意将最后一位设为'\0' for(p = g.vertices[i].firstarc; p && !found; p = p->nextarc) if(s == p->adjvex) //找到目标节点 { found=1; //found置为1,退出 path[rear++]=g.vertices[p->adjvex].data; path[rear]='\0'; } else if(!g.visited[p->adjvex]) { DFSearch(g,p->adjvex,s,path); } if(!found) //如果该节点的所有邻接点都不是目标节点,并且邻接点的邻接点也不是目标节点,那么它就不是路径上的。退出路径 path[--rear]='\0'; } //求两点之间的一般路径 void Path(ALGraph &g, char ch1, char ch2, char path[]) { int i = LocateVex(g, ch1); int s = LocateVex(g, ch2); DFSearch(g,i,s,path); } int main() { ALGraph G; init_ALGraph(G); //初始化图 CreateUDN(G); //创建图 PrintAdjList(G); //打印图 //DFSTraverse(G,0); //深度优先搜索 //求两点之间的一般路径 char ch1,ch2; char *path; //存放路径 path=(char *)malloc(MAX_VERTEX_NUM*sizeof(char)); cout<<"please input two points:"<<endl; cin>>ch1>>ch2; Path(G,ch1,ch2,path); int i=0; while(path[i]) cout<<path[i++]; //输出路径 return 0; }

上一篇:C++ 中的原子性操作
下一篇:数据结构——图的邻接矩阵的广度优先级搜索

相关文章

相关评论