深度优先搜索和广度优先搜索
屏幕快照 2018-04-26 下午3.06.42.png
#pragma mark - - 地图问题 最短距离
#pragma mark - 深度优先搜索
// 深度优先
-(void)test1 {
/*
e[i][j] 表示i到j的距离 顶点i到顶点i的距离表示为0，
顶点i无法到达顶点j表示为e[i][j]=0
*/
int e[10][10];
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
if (i==j) {
e[i][j]=0;
}else{
e[i][j]=9999;
}
}
}
e[1][2] =2;
e[1][5] =10;
e[2][3] =3;
e[2][5] =7;
e[3][1] =4;
e[3][4] =4;
e[4][5] =5;
e[5][3] =3;
int book[10] ={0}; // 标示该点是否已经在路径中
func1(1, 0, e, book);
NSLog(@"最短距离为:%d",min);
}
int min = 10000;
void func1(int cur, int dis,int e[10][10],int book[]) {
if(dis>min){
return ; // 如果当前已经走过的路大于之前找到的最短路 就没有必要继续尝试下去；
}
// 判断是否到达目标城市
if (cur==5) {
if (dis<min) {
min =dis; // 更新最小值
}else{
return ;
}
}
// 总共5个顶点 按顺序遍历
for (int i=1; i<=5; i++) {
if (e[cur][i]!=9999 && e[cur][i]!=0 && book[i]==0) {
book[i] =1;
func1(i, dis+e[cur][i], e, book);
book[i] =0; //取消对该城市的标记
}
}
}
// 对上面代码进行优化 打印出最短路径
// 用一个栈来存储路径
int min2 =10000;
int que2[10];
int top2=0;
-(void)test2 {
/*
e[i][j] 表示i到j的距离 顶点i到顶点i的距离表示为0，
顶点i无法到达顶点j表示为e[i][j]=0
*/
int e[10][10];
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
if (i==j) {
e[i][j]=0;
}else{
e[i][j]=9999;
}
}
}
e[1][2] =2;
e[1][5] =10;
e[2][3] =3;
e[2][5] =7;
e[3][1] =4;
e[3][4] =4;
e[4][5] =5;
e[5][3] =3;
int book[10] ={0}; // 标示该点是否已经在路径中
// 标记顶点1
book[1]=0;
// 把第一个顶点加入栈 入栈
top2 ++;
que2[top2] = 1;
func2(1, 0, e, book);
NSLog(@"最短距离为:%d",min2);
}
void func2(int cur,int dis,int e[10][10],int book[10]) {
if (dis>min2) {
return ; // 如果当前路径长度大于最小值，就没必要继续尝试下去啦
}
if (cur==5) {
if (dis<min2) {
min2 =dis; // 更新最小值
// 打印 栈数据
printf("路径:");
for (int i=1; i<=top2; i++) {
printf("%3d",que2[i]);
}
printf(" 当前路径的距离为:%3d",dis);
printf("\n");
}else {
return ;
}
}
for (int i=1; i<=5; i++) {
if (e[cur][i]!=9999 && e[cur][i]!=0 && book[i]==0) {
// 标记为1
book[i] =1;
// 入栈
top2 ++;
que2[top2] = i;
// 递归 探索下一个点
func2(i, dis+e[cur][i], e, book);
// 取消当前顶点标记
book[i] =0;
// 出栈
top2--;
}
}
}
#pragma mark - 广度优先搜索
/*
这一题 用广度优先搜索会比较麻烦。广度优先搜索更加适用于所有边的权值相同的情况~
*/
struct note {
int x; // 顶点
int dis; // 到达这个顶点的距离
int f; //由哪个顶点延伸出来的
};
-(void)test3 {
int e[10][10];
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
if (i==j) {
e[i][j]=0;
}else{
e[i][j]=9999;
}
}
}
/*
e[i][j] 表示i到j的距离 顶点i到顶点i的距离表示为0，
顶点i无法到达顶点j表示为e[i][j]=0
*/
e[1][2] =2;
e[1][5] =10;
e[2][3] =3;
e[2][5] =7;
e[3][1] =4;
e[3][4] =4;
e[4][5] =5;
e[5][3] =3;
int min3 =1000;
int mtail=0; // 记录最短距离时 当前节点在队列中位置
// 初始化对列
struct note que3[1000];
int head=1;
int tail=1;
// 将顶点1加入队列
que3[tail].x =1;
que3[tail].dis =0;
que3[tail].f =0;
tail ++;
while (head<tail) {
// 当前点
int cur = que3[head].x;
int dis = que3[head].dis;
if (dis>min3) {
head ++;
}
if (cur==5) {
if (dis<min3) {
min3 =dis;
mtail = head;
}else {
head ++;
}
}
for (int i=1; i<=5; i++) {
if (e[cur][i]!= 9999 && e[cur][i]!=0 ) {
// 入队
que3[tail].x= i;
que3[tail].f=head;
que3[tail].dis = que3[head].dis + e[cur][I];
tail ++;
}
}
head ++;
}
NSLog(@"最短距离:%d",min3);
// 打印最短路径
printf("最短路径:");
int lastIndex =mtail;
while (lastIndex!=0) {
printf("%3d",que3[lastIndex].x);
lastIndex =que3[lastIndex].f;
}
printf("\n");
}
屏幕快照 2018-04-26 下午3.06.24.png
#pragma mark - - 最少转机 - 图的广度优先遍历
#pragma mark - 广度优先遍历
struct note2 {
int x; // 顶点
int f; // 当前节点是由哪个节点扩展出来的
int s; //步数
};
-(void)test4 {
int e[10][10];
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
if (i==j) {
e[i][j]=0;
}else{
e[i][j]=9999;
}
}
}
e[1][2] =1;
e[2][1] =1;
e[1][3] =1;
e[3][1] =1;
e[2][3] =1;
e[3][2] =1;
e[2][4] =1;
e[4][2] =1;
e[3][4] =1;
e[4][3] =1;
e[3][5] =1;
e[5][3] =1;
e[4][5] =1;
e[5][4] =1;
int book[10]={0};
// 初始化 队列
struct note2 que4[400];
int head=1;
int tail=1;
// 入队
que4[tail].x =1;
que4[tail].f =0;
que4[tail].s =0;
tail ++;
book[1] =1;
int flag=0;
while (head<tail) {
int cur = que4[head].x;
for (int i=1; i<=5; i++) {
if (e[cur][i]==1&&book[i]==0) {
book[i]=1;
// 入队
que4[tail].x =i;
que4[tail].f =head;
que4[tail].s =que4[head].s+1;
tail ++;
if (i==5) {
flag=1;
break ;
}
}
}
if (flag==1) {
break;
}
head ++;
}
NSLog(@"需要转机%d次",que4[tail-1].s);
// 打印转机顺序
printf("转机顺序:");
int lastIndex =tail-1;
while (lastIndex!=0) {
printf("%3d",que4[lastIndex].x);
lastIndex =que4[lastIndex].f;
}
printf("\n");
}
#pragma mark - 深度优先遍历
int min5=1000;
-(void)test5 {
int e[10][10];
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
if (i==j) {
e[i][j]=0;
}else{
e[i][j]=9999;
}
}
}
e[1][2] =1;
e[2][1] =1;
e[1][3] =1;
e[3][1] =1;
e[2][3] =1;
e[3][2] =1;
e[2][4] =1;
e[4][2] =1;
e[3][4] =1;
e[4][3] =1;
e[3][5] =1;
e[5][3] =1;
e[4][5] =1;
e[5][4] =1;
int book[10]={0};
book[1] =1;
func5(1, e, book,0);
NSLog(@"需要转机:%d次",min5);
}
void func5(int cur,int e[10][10],int book[],int step) {
if (step>min5) {
return ;
}
if (cur== 5) {
if (step<min5) {
min5 =step;
}else {
return ;
}
}
for (int i=1; i<=5; i++) {
if (e[cur][i] ==1 && book[i] ==0) {
book[i]=1;
func5(i, e, book,step+1);
book[i]=0;
}
}
}
