个人对回溯有两种理解。
第一种理解：回溯就是以非递归实现的深搜，这样的话，回溯就属于深搜。
第二种理解：回溯过程，是深搜过程中的一个子过程。
例如：
void Dfs(int t)
{
……
if (Ok()) //可行性判断
{
Change_togo() //搜索前的标记及修改
Dfs(i+1)//深搜下一层
Change_back() //将标记和修改的值还原
}
}
在这个深搜过程中，Change_back()这个还原的子过程，就可以称为回溯过程。
一般的深搜都带回溯,但是没有回溯的深搜都是好深搜（一次就做完了，复杂度大大的低）
这是用邻接表创建的一个图实现了广度和深度遍历
希望能帮助你
#include <iostream>
using namespace std
#define MaxSize 50
struct ArcNode // 保存结点后面的所连边对应的点
{
int adjvex
struct ArcNode * nextarc
}
// 用来存放一个节点的结构体,存放首节点,后面定义的是一个结构体数组
struct Vnode
{
int data
struct ArcNode * firstarc
}
int m,n,v
void creatgraph(struct Vnode A[MaxSize])// 创建图
void dfs(struct Vnode A[MaxSize])// 深搜
void bfs(struct Vnode A[MaxSize])// 广搜
int main()
{
struct Vnode AdjList[MaxSize]
int cord
do
{
cout<<" 主菜单"<<endl
cout<<" 1 建立无向图的邻接表"<<endl
cout<<" 2 按深度遍历图"<<endl
cout<<" 3 按广度遍历图"<<endl
cout<<" 4 结束程序运行"<<endl
cout<<"------------------------------"<<endl
cout<<" 请输入你的选择1 ,2 ,3 ,4:"<<endl
cin>>cord
switch(cord)
{
case 1:creatgraph(AdjList)break
case 2:dfs(AdjList)break
case 3:bfs(AdjList)break
case 4:exit(0)
}
}while(cord <= 4)
return 0
}
void creatgraph(struct Vnode A[MaxSize]) //创建图
{
int i,j,k
struct ArcNode *p
cout<<" 输入边和点的个数:"<<endl
cin>>m>>n// m代表边的个数 ，n代表顶点个数
for(k=0k<nk++) // 首先对邻接表的所有顶点初始化
{
A[k].data = k+1
A[k].firstarc = NULL
}
for (k=0k<mk++) // 输入边,并插入到邻接表
{
cout<<" input arc:"<<endl
cin>>i>>j// 这代表一条无向边,顶点i与顶点j相连
p = (struct ArcNode *)malloc(sizeof(struct ArcNode))
p->adjvex = j
p->nextarc = A[i-1].firstarc
A[i-1].firstarc=p
p = (struct ArcNode *)malloc(sizeof(struct ArcNode))
p->adjvex = i
p->nextarc = A[j-1].firstarc
A[j-1].firstarc=p
}
cout<<endl
for(k=0k<nk++)// 输出邻接表
{
cout<<" vex"<<A[k].data<<" arc is:"
p=A[k].firstarc
while(p)
{
cout<<p->adjvex<<" "
p=p->nextarc
}
cout<<endl
}
}
void dfs(struct Vnode A[MaxSize])
{
struct ArcNode *p, *ar[MaxSize]
int x,i,y,top=-1
int visited[MaxSize]
for(i = 0 i <n i++) visited[i] = 0// 这个数组用于代表这个节点是否被遍历过
cout<<"input x of start vex"<<endl
cin>>x// 输入从哪个节点开始遍历
cout<<x
visited[x-1]=1// 首先根节点被发现
p=A[x-1].firstarc// 然后要遍历的是根节点的邻接点
while( (p) || top>=0) // 直到栈为空,并且没有邻接点就退出循环
{
if(!p) // 出栈
{
p = ar[top]
top--
}
y = p->adjvex
if(visited[y-1] == 0)
{
visited[y-1] = 1// 被发现
cout<<" ->"<<y
p = p->nextarc
if(p) {top++ar[top] = p} // 入栈
p=A[y-1].firstarc
}
else
p=p->nextarc
}
}
void bfs(struct Vnode A[MaxSize])
{
struct ArcNode *p
int x,i,y,front=-1,rear=-1,ar[MaxSize],visited[MaxSize]
for(i=0i<ni++) // 这个数组用于代表这个节点是否被遍历过
visited[i]=0
cout<<"input x"<<endl
cin>>x// 代表从哪个节点开始遍历
cout<<x
visited[x-1]=1//代表x的结点被发现
p=A[x-1].firstarc// x被发现之后就遍历x的邻接点
while( (p) || (front!=rear)) // 如果队列为空,并且这个结点没有了邻接点则退出循环
{
if (!p) // 这个当p的邻接点全部入队之后进入这句
{
front++//队列的队首元素的下标往下偏移
y=ar[front]//首先y出队,即去队首元素
p=A[y-1].firstarc//之后就要遍历y的邻接点了
}
y=p->adjvex//取p的数据域
if(visited[y-1] == 0)
{
visited[y-1]=1
cout<<" ->"<<y
rear++//把p的邻接点全部入队,知道遍历到p没有邻接点为止
ar[rear]=y
}
p=p->nextarc
}
}
![Java多线程同步设计中使用Metux[1]](/aiimages/Java%E5%A4%9A%E7%BA%BF%E7%A8%8B%E5%90%8C%E6%AD%A5%E8%AE%BE%E8%AE%A1%E4%B8%AD%E4%BD%BF%E7%94%A8Metux%5B1%5D.png)
