C++编写程序 关于【图的遍历】

里面多了查找路径功能。
#define t true
#define f false
#include
struct node//定义一个结构作为节点类型
{
int data;
bool sign;//标志位,用来标示是否遍历过
node *next;
};
node* creategraph()//建立邻接表，完成无向图的输入
{
int l,m,n;
bool g;
cout<<"请输入节点数: ";
cin>>n;
node *adjacencylist=new node[n+1];//动态分配节点数组内存
adjacencylist[0].data=n;//0地址存放的为节点数
adjacencylist[0].next=NULL;
for(int i=1;i<=n;i++)//给各顶点域赋初值
{
adjacencylist[i].data=0;
adjacencylist[i].next=NULL;
adjacencylist[i].sign=f;//表示未遍历
}
cout<<"请依次输入各条边的始点和尾点:（以0表示结束）"< cin>>l;
if(l!=0)//判断输入边是否结束
g=t;
while(g==t)
{
cin>>m;
if((l>0)&&(l<=n)&&(m>0)&&(m<=n))//判断输入顶点是否正确
{
node *p,*q,*top;
p=(node *)new(node);//分配边的一个顶点内存
p->data=m;
p->next=NULL;
if(adjacencylist[l].next==NULL)//为每个节点创建邻接链表
adjacencylist[l].next=p;
else
{
top=adjacencylist[l].next;
while(top->next!=NULL)
top=top->next;
top->next=p;
}
adjacencylist[l].data++;//统计邻接点的个数
q=(node *)new(node);//分配边的另一个顶点内存
q->data=l;
q->next=NULL;
if(adjacencylist[m].next==NULL)//构建邻接表
adjacencylist[m].next=q;
else
{
top=adjacencylist[m].next;
while(top->next!=NULL)
top=top->next;
top->next=q;
}
adjacencylist[m].data++;//统计邻接点的个数
}
else
cout<<"边"< cin>>l;
if(l==0)//边的输入结束
g=f;
}
return adjacencylist;//返回邻接表
};
void DepthFirstSearch(node *list)//深度优先搜索
{
int m,n=list[0].data,k,*a=new int[n];//设置一个数组用于存放节点
node *p;
cout<<"采用深度优先搜索："< cout<<"请输入搜索起始节点：";
cin>>k;
for(int i=0;i {
a[i]=k;
list[k].sign=t;
if(i==n-1)
break;
m=0;
while(list[k].sign==t)
{
p=list[k].next;
while(p!=NULL)//找出list[k]链表中的未遍历节点
{
k=p->data;
p=p->next;
if(list[k].sign==f)
break;
}
m++;
if(list[k].sign!=f)//判断是否是p=NULL跳出while循环的
{
if(i {
cout<<"该图为非连通图!"< break;
}
else
k=a[i-m]; //回溯
}
}
}
for(i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;
cout<<"深度优先搜索遍历顺序为:";
for(i=0;i cout< cout< delete a;//释放动态数组内存
};
void BreadthFirstSearth(node *list)//广度优先搜索
{
int m,r,k,n=list[0].data,*a=new int[n+1];//设置数组存放节点
node *p;
cout<<"采用广度优先搜索："< cout<<"请输入搜索起始节点：";
cin>>k;
a[0]=n;
a[1]=k;
list[k].sign=t;//标识遍历的第一个节点
m=0;
r=1;
while(m!=r)
{
m++;
p=list[a[m]].next;
while(p!=NULL)
{
k=p->data;
if(list[k].sign==f)
{
r++;
a[r]=k;//遍历到的节点存入数组
list[k].sign=t;//标识已经遍历过的节点
}
p=p->next;
}
}
for(int i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;
cout<<"广度优先搜索遍历顺序为: ";
for(i=1;i<=n;i++)//输出遍历
cout< cout< delete a;//释放动态数组内存
};
void PathSearth(node *list)//路径搜索
{
int *a,c,d,m,k,n=list[0].data;
cout<<"请输入起始点：";
cin>>k;
cout<<"请输入尾节点：";
cin>>c;
cout<<"请输入要找的路径长度：";
cin>>d;
d=d+1;
if(d>n)
cout<<"不存在这样的简单路径！"< else
{
a=new int[d];//动态分配数组内存存放路径上的节点
for(int i=0;i a[i]=0;
a[0]=k;
node *p;
int x;
list[a[0]].sign=t;
i=1;
while(a[d-1]!=c)
{
while(i {
x=1;
p=list[a[i-1]].next;
while(p!=NULL)
{
m=p->data;
if(i==d-1&&m==a[0]&&a[0]==c)//路径存在且为回路
{
cout<<"该路径为一条回路！"< a[i]=m;
i++;
break;
}
if(list[m].sign==f)
{
if(a[i]!=0)
{
if(x==0)//是否为已经判断过的错误路径
{
a[i]=m;
list[a[i]].sign=t;//标识走过节点
i++;
break;
}
if(a[i]==m)//设置错误路径标识
x=0;
}
else
{
a[i]=m;
list[a[i]].sign=t;//标识走过节点
i++;
break;
}
}
p=p->next;
}
if(p==NULL)
{
a[i]=0;
i--;//由此节点往下的路径不存在,回溯
list[a[i]].sign=f; //还原标识符
}
if(i==0)//无法回溯,路径不存在,跳出循环
{
cout<<"不存在这样的简单路径！"< break;
}
}
if(i==0)//无法回溯,路径不存在,跳出循环
break;
if(a[d-1]!=c)//路径不是所要找的
{
i--; //回溯
if(i>=0)
list[a[i]].sign=f;//还原标识符
}
}
if(a[d-1]==c)//判断路径是否找到并输出
{
cout<<"从节点"< for(i=0;i cout< ";
cout< }
delete a;
}
for(int i=1;i<=n;i++)//恢复原邻接表
list[i].sign=f;
};
void AdjacencyListDelete(node *list)//释放邻接表的空间
{
node *p,*q;
int n=list[0].data;
for(int i=1;i<=n;i++)
{
p=list[i].next;
while(p!=NULL)
{
q=p->next;
delete p;//释放链表节点空间
p=q;
}
}
delete list;//释放邻接表空间
};
void main()
{
node *list;
list=creategraph();//以邻接表的形式建立一个无向图
char a,b;
cout<<"请选择遍历方法：（d:深度优先搜索;b:广度优先搜索）";
for(int i=1;i<2;i++)
{
cin>>a;
switch(a)
{
case 'd':
case 'D': DepthFirstSearch(list);
cout<<"是否采用广度优先搜索重新遍历？（y:是;n:否）";
cin>>b;
if((b=='y')||(b=='Y'))
BreadthFirstSearth(list);
break;
case 'b':
case 'B': BreadthFirstSearth(list);
cout<<"是否采用深度优先搜索重新遍历？（y:是;n:否）";
cin>>b;
if((b=='y')||(b=='Y'))
DepthFirstSearch(list);
break;
default: cout<<"输入错误！请重新输入！"< i--;
}
}
while(1)
{
cout<<"是否搜索路径？（y:是;n:否）";
cin>>a;
if((a=='y')||(a=='Y'))
PathSearth(list);
else if((a=='n')||(a=='N'))
break;
else
cout<<"输入错误！"< }
AdjacencyListDelete(list);//释放邻接表空间
}

以下程序均运行通过：
图的广度优先遍历
/*******************************************/
/* 图形的广度优先搜寻法 */
/*******************************************/
#include
#include
#define MAXQUEUE 10 /* 队列的最大容量 */
struct node /* 图的顶点结构定义 */
{
int vertex;
struct node *nextnode;
};
typedef struct node *graph; /* 图的结构指针 */
struct node head[9]; /* 图的顶点数组 */
int visited[9]; /* 遍历标记数组 */
int queue[MAXQUEUE]; /* 定义序列数组 */
int front = -1; /* 序列前端 */
int rear = -1; /* 序列后端 */
/***********************二维数组向邻接表的转化****************************/
void creategraph(int node[20][2],int num)
{
graph newnode; /* 顶点指针 */
graph ptr;
int from; /* 边起点 */
int to; /* 边终点 */
int i;
for ( i = 0; i < num; i++ ) /* 第i条边的信息处理 */
{
from = node[i][0]; /* 边的起点 */
to = node[i][1]; /* 边的终点 */
/* 建立新顶点 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 顶点内容 */
newnode->nextnode = NULL; /* 设定指针初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入第i个节点的链表尾部 */
}
}
/************************ 数值入队列************************************/
int enqueue(int value)
{
if ( rear >= MAXQUEUE ) /* 检查伫列是否全满 */
return -1; /* 无法存入 */
rear++; /* 后端指标往前移 */
queue[rear] = value; /* 存入伫列 */
}
/************************* 数值出队列*********************************/
int dequeue()
{
if ( front == rear ) /* 队列是否为空 */
return -1; /* 为空，无法取出 */
front++; /* 前端指标往前移 */
return queue[front]; /* 从队列中取出信息 */
}
/*********************** 图形的广度优先遍历************************/
void bfs(int current)
{
graph ptr;
/* 处理第一个顶点 */
enqueue(current); /* 将顶点存入队列 */
visited[current] = 1; /* 已遍历过记录标志置疑1*/
printf(" Vertex[%d]\n",current); /* 打印输出遍历顶点值 */
while ( front != rear ) /* 队列是否为空 */
{
current = dequeue(); /* 将顶点从队列列取出 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /*顶点没有遍历过*/
{
enqueue(ptr->vertex); /* 奖定点放入队列 */
visited[ptr->vertex] = 1; /* 置遍历标记为1 */

printf(" Vertex[%d]\n&q