用C++实现寻找迷宫里最短路线 用C++创建一个图，并寻找最短路径
我是公司的网，上不了QQ抱歉。
有什么疑问发到百度我的消息里
都是数据结构的问题
我找到了，贴过来:
#include<iostream.h>
#include <stdlib.h>
#include<iomanip.h>
#define STACK_INIT_SIZE 100 //初始栈大小
#define STACKINCREAMENT 10 //添加栈的长度
#define SIZE_OF_MAPH 20 //迷宫高度
#define SIZE_OF_MAPW 20 //迷宫长度
////////////////////////////////////////////////////////////////////////////////
// 结构体名称：MazeCell
// 功能：用来描述迷宫组成单元的信息
// 成员：Pass: 当Pass为1时，表示导通块；为0则表示障碍块；
// Footprint: 当 Footprint为1时，表示留下足迹，反之，表示未经此地。
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
int Pass;
bool Footprint;
}MazeCell;
////////////////////////////////////////////////////////////////////////////////
// 结构体名称：SElemType
// 功能： 此为栈的元素，用来表示当前位置，（栈用来描述当前路径）
// 成员： ord: 通道块的序号
// x : 当前位置的横坐标
// y : 当前位置的纵坐标
// di : 搜索方向 1向东，2向南，3向西，4向北
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
int ord;
int x;
int y;
int di;
}SElemType;
////////////////////////////////////////////////////////////////////////////////
// 结构体名称： SqTack
// 功能： 此为栈，用来记录当前路径
// 成员： *base 栈底指针，指向起点
// *top 栈顶指针，指向路径的末点
// stacksize 栈的容量
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
////////////////////////////////////////////////////////////////////////////////
// 结构体名称： Seat
// 功能： 用来记录迷宫坐标，此结构体为中间变量，纯粹为方便编程而建立
// 成员： x: 用来记录横坐标
// y: 用来记录纵坐标
////////////////////////////////////////////////////////////////////////////////
typedef struct
{
int x;
int y;
}Seat;
////////////////////////////////////////////////////////////////////////////////
// 函数名称： InitStack
// 功能： 此函数用于初始化一个栈，即在类存中找一块大小为STACK_INIT_SIZE个栈
// 元素的空间,将其首址赋给栈底指针，此时栈顶指针与栈底指针重合。栈的容
// 量为 STACK_INIT_SIZE。操作成功则函数返回1，若类存空间不足，函数返回
// 0，表示初始化失败。
// 函数参数： SqStack &S
// 函数返回值类型： bool
////////////////////////////////////////////////////////////////////////////////
bool InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
{
return 0;
}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 0;
}
////////////////////////////////////////////////////////////////////////////////
// 函数名称： BuideMaze
// 功能： 此函数的功能是用于根据用户要求建立一个迷宫地图，将用户输入的整形数组
// 形状给迷宫数组
//
// 函数参数： MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP]
// Seat &start 起点坐标
// Seat &end 终点坐标
// 函数返回值类型： bool 建立成功则返回1，反之返回0。
////////////////////////////////////////////////////////////////////////////////
void BuideMaze(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],int ma[SIZE_OF_MAPH][SIZE_OF_MAPW])
{
for(int i=0;i<SIZE_OF_MAPH;i++)
{
for(int j=0;j<SIZE_OF_MAPW;j++)
{
Map[i][j].Pass=ma[i][j];
Map[i][j].Footprint=0;
}
}
}
////////////////////////////////////////////////////////////////////////////////
// 函数名称： Pass
// 功能： 此函数用于判断当前点是否可通，如果可通则返回1，反之返回0。
// 所谓可通是指当前位置为导通块并且当前位置没有留下脚印。
// 函数参数： Seat curpos 当前块的坐标
// MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP] 迷宫地图
// 函数返回值类型： bool 若当前块可通则返回1，反之则返回0。
////////////////////////////////////////////////////////////////////////////////
bool Pass(Seat curpos,MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW])
{
if(Map[curpos.x][curpos.y].Pass==0)
{
return 0;
}
else if(Map[curpos.x][curpos.y].Footprint==1)
{
return 0;
}
else
{
return 1;
}
}
////////////////////////////////////////////////////////////////////////////////
// 函数名称： FootPrint
// 功能： 此函数用于在当前路径下留下脚印。
// 函数参数： Seat curpos 当前坐标
// MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP] 迷宫地图
// 函数返回值类型： 无
////////////////////////////////////////////////////////////////////////////////
void FootPrint(Seat curpos,MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW])
{
Map[curpos.x][curpos.y].Footprint=1;
}
bool Push(SqStack &S,SElemType e)//栈插入函数
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(SElemType));
if(!S.base)
{
return 0;
}
S.top=S.base+S.stacksize;
S.stacksize=S.stacksize+STACKINCREAMENT;
}
*S.top++=e;
return 1;
}
bool Pop(SqStack &S,SElemType &e)//栈取出最上面的元素，将值给e
{
if(S.base==S.top)return false;
S.top--;
e=*S.top;
return true;
}
////////////////////////////////////////////////////////////////////////////////
// 函数名称： NextPos
// 功能： 此函数用于将坐标为x,y位置的di方向位置切换为当前位置。
// 函数参数： Seat curpos 当前坐标
// int di 方向
// int x,y 坐标
// 函数返回值类型： 无
////////////////////////////////////////////////////////////////////////////////
void NextPos(int x,int y,Seat &curpos,int di)
{
if(di==1)
{
curpos.y=y+1;
curpos.x=x;
}
else if(di==2)
{
curpos.x=x+1;
curpos.y=y;
}
else if(di==3)
{
curpos.y=y-1;
curpos.x=x;
}
else if(di==4)
{
curpos.x=x-1;
curpos.y=y;
}
}
///////////////////////////////////////////////////////////////////////////
// 函数名称： PutIn
// 功能： 向数组里输入元素
// 函数参数： int map[] 将得到的数组给map
// int Wei 迷宫的长度
// int Hig 迷宫的高度
// 函数返回值类型： 无
///////////////////////////////////////////////////////////////////////////
void PutIn(int map[],int &Wei,int &Hig)
{
int w,h;
cout<<"如果您想输入的迷宫大于所规定的大小，您只需修改SIZE_OF_MAPH和SIZE_OF_MAP"<<endl;
cout<<"请输入迷宫的长度(长度小于等于"<<SIZE_OF_MAPW-2<<")：";
cin>>w;
cout<<"请输入迷宫的高度(高度小于等于"<<SIZE_OF_MAPW-2<<")：";
cin>>h;
cout<<"1表示导通块；0表示障碍块"<<endl;
Wei=w;
Hig=h;
for(int i=0;i<SIZE_OF_MAPH;i++)
for(int j=0;j<SIZE_OF_MAPW;j++)
*(map+i*SIZE_OF_MAPW+j)=0;
for(int is=1;is<h+1;is++)
{
cout<<"请输入第"<<is<<"行:";
for(int js=1;js<w+1;js++)
{
int point;
cin>>point;
*(map+is*SIZE_OF_MAPW+js)=point;
}
cout<<endl;
}
}
///////////////////////////////////////////////////////////////////////////
// 函数名称： Display
// 功能： 用于显示栈中所有元素
// 函数参数： 无
// 函数返回值类型： 无
///////////////////////////////////////////////////////////////////////////
void Display(SqStack S)
{
int i=1;
SElemType *p;
p=S.base;
cout<<"从base到top:"<<endl;
cout<<"di搜索方向:di=1向东，di=2向南，di=3向西，di=4向北"<<endl;
while(p!=S.top) //从base到top打印元素
{
cout<<"第"<<i<<"步: ";
cout<<"("<<(*p).y;
cout<<","<<(*p).x;
cout<<","<<(*p).di<<")"<<endl;
p++;
i++;
}
}
void DisplayMaze(int ma[SIZE_OF_MAPH][SIZE_OF_MAPW],int w,int h)
{
cout<<"迷宫为(1代表可以通过；0代表不可以通过): "<<endl;
for(int i=0;i<h+2;i++)
{
for(int j=0;j<w+2;j++)
{
cout<<ma[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
///////////////////////////////////////////////////////////////////////////
// 函数名称： MazePath
// 功能： 组织所有子函数，求解迷宫
// 函数参数： 无
// 函数返回值类型： int 迷宫有解则返回1，反之则返回0；
////////////////////////////////////////////////////////////////////////////
int MazePath(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],Seat start,Seat end)
{
SElemType e;
SqStack S; //定义一个栈
InitStack(S); //初始化栈
Seat curpos; //定义当前位置
int curstep; //计步器
curstep=1; //计步器计1
curpos.x=start.x; //
curpos.y=start.y; //当前位置设为起点
cout<<"起点是:"<<start.y<<" "<<start.x<<endl;
cout<<"终点是:"<<end.y<<" "<<end.x<<endl;
///////////////////////////////////////////////////////////////////////////
//
// 下面的循环是求解迷宫的核心程序
////////////////////////////////////////////////////////////////////////////
do
{
if(Pass(curpos,Map)) //如果当前块可通，则进行如下操作
{
FootPrint(curpos,Map); //留下脚印
e.ord=curstep; //记下计步器
e.x=curpos.x; //记下行数
e.y=curpos.y; //记下列数
e.di=1; //设一个方向为东方
Push(S,e); //压栈操作，将当前位置纳入当前路径
if(curpos.x==end.x&&curpos.y==end.y) //如果当前块为终点，进行如下操作
{ //
cout<<"ok!"; //
Display(S); //调用显示栈的子程序显示结果
return 1; //函数返回1
} //
else //如果当前位置不是终点，进行如下操作
{ //
NextPos(curpos.x,curpos.y,curpos,1); //切换东方向的位置为当前位置
curstep++; //计步器自增1
}
}//if
else
{
if(S.base!=S.top) //如果当前块不通，且栈不为空（说明还有解）
{
Pop(S,e); //将栈顶元素弹出进行观察
while(e.di==4&&(S.top-S.base)) //如果栈顶元素四方均不通
{
Pop(S,e); //弹出下一个栈顶元素进行观察
}//while
if(e.di<4) //如果栈顶元素还有其他方向没有走过
{ //
e.di++; //切换下一个方向为当前方向
Push(S,e); //压入栈
NextPos(e.x,e.y,curpos,e.di); //切换下一个方向位置为当前位置
}//if
}//if
}//else
}while(S.base!=S.top); //只要栈不空则说明有解，重复循环
cout<<"没找到路径"<<endl;
}
////////////////////////////////////////////////////////////////////////////////
// 函数名称： main
// 功能： 组织所有子函数，求解迷宫
// 函数参数： 无
// 函数返回值类型： bool 迷宫有解则返回1，反之则返回0；
//
////////////////////////////////////////////////////////////////////////////////
void main()
{
MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW]; //定义一个迷宫数组
/*int migong[SIZE_OF_MAPH][SIZE_OF_MAPW]= {
{ 0,0,0,0,0,0,0,0,0,0},
{ 0,1,1,0,0,0,0,0,0,0}, //1
{ 0,0,1,1,1,0,1,1,1,0}, //2
{ 0,0,1,0,1,1,1,0,1,0}, //3
{ 0,0,1,0,0,0,0,0,1,0}, //4
{ 0,0,1,0,1,1,1,0,0,0}, //5
{ 0,0,1,1,1,0,1,1,1,0}, //6
{ 0,0,0,0,0,0,0,0,0,0},
}; //以数组表示的迷宫*/
int w,h;
int migong[SIZE_OF_MAPH][SIZE_OF_MAPW];
PutIn(migong[0],w,h);
BuideMaze(Map,migong); //调用建立迷宫的子函数
DisplayMaze(migong,w,h); //显示迷宫的形状
Seat start,end; //定义当前位置，起点位置，终点位置的结构体
/*start.x=1; //起点
start.y=1; //
end.x=2; //终点
end.y=2; //*/
cout<<"起点横坐标:";
cin>>start.y;
cout<<"起点纵坐标:";
cin>>start.x;
cout<<"终点横坐标:";
cin>>end.y;
cout<<"终点纵坐标:";
cin>>end.x;
MazePath(Map,start,end);
}
程序大部分分成函数了，你只要把函数的功能弄清楚了，就差不多了
祝你成功！我当时弄了3天才写出来的
我这几天刚写了一个，应该可以运行的。/*
栈的头文件
*/
#include<iostream.h>
#include<process.h>
template<class T>
class Stack
{
private:
int MaxNum; //栈的最大空间
int top; //栈顶
T *s; //栈的元素
public:
//构造函数及析构函数
Stack(int n)
{
if(n<1)
{
cout<<"构造函数非法"<<endl;
exit(0);
}
MaxNum=n;
top=-1;
s=new T [MaxNum];
if(!s)
{
exit(0);
}
}
~Stack()
{
delete []s;
}
bool IsFull()
{
/*
判断栈是否为满
*/
if(top==MaxNum-1)
return true;
else return false;
}
bool IsEmpty()
{
/*
判断栈是否为空
*/
if(top==-1)
return true;
else return false;
}
void Push(T x)
{
/*
将元素x压入栈pS中
*/
if(IsFull())
{
cout<<"栈满了"<<endl;
exit(0);
}
s[++top]=x;
}
T Pop()
{
/*
弹出栈顶元素
*/
if(IsEmpty())
{
cout<<"栈空!"<<endl;
exit(0);
}
return s[top--];
}
};
#include"stack.h"
#include<iostream.h>
#define MAXLEN 10
struct PostType
{
int r; //行
int c; //列
};
struct SElemType
{
PostType seat;
int di; //方向
};
struct MazeType
{
int r;
int c;
char adr[MAXLEN][MAXLEN]; //''表示未走过且可以走的,'*'表示已走过的
}; //10*10的迷宫类型
bool Pass(MazeType maze,PostType pos)
{
/*
判断当前扫描的坐标是否可以通过
*/
if(maze[pos.r][pos.c]=='')
return true;
else return false;
}
void FootPrint(MazeType &maze,PostType pos)
{
/*
将当前坐标标上足迹'*'表示已走过的
*/
maze[pos.r][pos.c]='*';
}
void NextPos(PostType &pos, int i)
{
/*
根据i修改当前坐标即求下一个坐标
*/
//1.2.3.4分别表示东,南,西,北方向
switch(i)
{
case 1 : pos.c+=1; break;
case 2 : pos.r+=1; break;
case 3 : pos.c-=1; break;
case 4 : pos.r-=1; break;
default: exit(1);
}
}
void MarkPrint(MazeType &maze,PostType pos)
{
/*
将pos标记未无法走过的，且已试过的路径
*/
maze[pos.r][pos.c]='@';
}
bool MazePath(MazeType &maze,PostType start,PostType end)
{
/*
从start到end找一条路径
*/
PostType curpos; //当前扫描的点
SElemType e;
int di;
Stack<SElemType>S(200);
curpos=start;
//始终从东开始扫描
do
{
if(Pass(maze,curpos)) //看当前点是否可以通过
{
//进栈，不能通过不能进栈
e.seat=curpos;
e.di=1;
S.Push(e);
//并且标记已走过该路径
FootPrint(maze,curpos);
//检查是否到达终点
if((curpos.r==end.r)&&(curpos.c==curpos.c))
{
/*
打印路径即可
*/
while(!S.IsEmpty())
{
e=S.Pop();
cout<<e<<endl;
}
return true;
}
else
{
NextPos(curpos,1); //始终从东扫描
}
} //end if
else //无法通过
{
/*
退栈，当前点由前一个点产生，所以需要修改它的上一个点的方向，如果上一个点的任何方向产生的点
都无法通过，则不必将上一个点再次进栈，如果可以通过，只需再次进栈
*/
e=S.Pop();
while(!S.IsEmpty()&&(e.di==4))
{
MakePrint(maze,e.seat); //标记已走过但出栈的点
e=S.Pop();
}
if(!S.IsEmpty()&&e.di<4) //可以修改方向
{
curpos=e.seat;
e.di++;
//栈顶的点再次进栈
S.Push(e);
//还必须再次求其下一个点
NextPos(curpos,1);
}
} //end else
}while(!S.IsEmpty());
return false;
}
其实应该 广搜 但基于迷宫不大 深搜也可以
至于你说的用链表储存，那一定是广搜的方法
可那样实现起来有点麻烦，基于简单的原则，用数组模拟就足够了
我比较喜欢深搜，这里可以加上A*算法，效果很不错。
但基于简单的原则，A*也省略了。。。。。
以下是经过重重省略的代码(而且未经编译,仅给主要过程):
bool deepFirstSearch(int x,int y,int s[22][22],int path,int deep){
if (deep<path || s[x][y]==1) return false;
if (x==1 && y==1) return true;
if(deepFirstSearch(x+1,y,s,path+1,deep))return true;
if(deepFirstSearch(x-1,y,s,path+1,deep))return true;
if(deepFirstSearch(x,y+1,s,path+1,deep))return true;
if(deepFirstSearch(x,y-1,s,path+1,deep))return true;
return fasle;
}
int main(){
for(deep=1;!deepFirstSearch(x,y,s,0,deep);deep++);
cout<<deep<<endl;
}
这个就是传闻中的 A 算法，也叫迭代加深，是一种深搜模拟广搜的算法
真怀念呀，最近写这个A也是几年前了，那时候刚开始接触编程
再多加一句，那迷宫的边界都要给赋值成1呀，相当于外墙
广度优先遍历即可
数据结构算法 用C++ 迷宫最短路径~
一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现
用的是深度优先的算法，可以寻找到走出迷宫的路径
但本题要求求出最短的路径，这就要使用广度优先的算法
一般在程序中需要用到先进先出的队列数据结构
下面是程序的代码，主要原理是用到
quei，quej和prep三个数组来构成队列
分别储存路径的行，列坐标和上一个节点在队列中的位置
大致算法如下，右三个嵌套的循环实现
首先是第一个节点进入队列
当队列不空（循环1）
｛
遍历队列中每节点(循环2）
｛
将八个方向能够走的节点加入队列（循环3）
｝
旧的节点出列
｝
#include#include using namespace std; #define MAXNUM 50void main() {int m,n,i,j,x;cout>m>>n;int maze[MAXNUM][MAXNUM];srand((int)time(NULL));for(i=0;i700){maze[i][j]=1;} //控制矩阵中1的个数，太多1迷宫很容易走不通else{maze[i][j]=0;}}cout<<maze[i][j]<<' ';}cout<<endl;}//以上是输入和迷宫生成，一下是走迷宫 int move[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};int *quei=new int[m*n];//储存行坐标队列int *quej=new int[m*n];//储存列坐标队列int *prep=new int[m*n];//储存之前一步在队列中的位置int head,rear,length;//队列头，队列尾，队列长度head=0;rear=1;length=1;quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置进队列int pos;//当前节点在队列中的位置，int ii,jj,ni,nj;//当前节点的坐标，新节点的坐标int dir;//移动方向if(maze[1][1]==1)length=0;//第一点就不能通过else maze[1][1]=1;while(length)//队列非空继续{for(pos=head;pos<head+length;pos++)//寻找这一层所有节点{ii=quei[pos];jj=quej[pos];//当前位置坐标if(ii==m&&jj==n)break;for(dir=0;dir<8;dir++)//寻找8个方向{ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐标if(maze[ni][nj]==0)//如果没有走过{quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新节点入队rear=rear+1;maze[ni][nj]=1;//标记已经走过}}}if(ii==m&&jj==n)break;head=head+length;length=rear-head;//这一层节点出列}if(ii==m&&jj==n){while(pos!=-1){cout<<'('<<quei[pos]<<','<<quej[pos]<<')';pos=prep[pos];if (pos!=-1)cout<<',';}}else{cout<<"THERE IS NO PATH."<<endl;}delete []quei;delete []quej;delete []prep;}
下面这个是我以前做的，你可以参考一下。
用VC++建一个工程，根据你的需要，修改邻接矩阵就可以了；源代码如下：
// Stack.h: interface for the Stack class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_STACK_H__289E76B1_034C_4426_AE27_6ADCC13EDBCD__INCLUDED_)
#define AFX_STACK_H__289E76B1_034C_4426_AE27_6ADCC13EDBCD__INCLUDED_
#include
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#define MaxSize 1024
template class Stack{//堆栈类
private:
Type data[MaxSize];
int top;
public:
Stack(){ //初始化栈
top = -1;
}
virtual~Stack();
bool IsEmpty(); //判断栈为空
bool IsFull(); //判断栈为满
int GetTop(); //取top的位置
void Push(Type);//进栈
Type Pop(); //退栈
};
template Stack::~Stack(){
}
template bool Stack::IsEmpty(){
return(top == -1);
}
template bool Stack::IsFull(){
return(top == MaxSize-1);
}
template int Stack::GetTop(){
return top;
}
template void Stack::Push(Type item){
if(IsFull())
cout<<"栈满!
";
else{
top++;
data[top] = item;
}
}
template Type Stack::Pop(){
if(IsEmpty()){
cout<<"栈空!
";
return NULL;
}
else{
Type item;
item = data[top];
top--;
return item;
}
}
#endif // !defined(AFX_STACK_H__289E76B1_034C_4426_AE27_6ADCC13EDBCD__INCLUDED_)
// AdjMatrix.h: interface for the AdjMatrix class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_ADJMATRIX_H__220DF675_DDB5_4E64_BD89_CDDA2C1F7804__INCLUDED_)
#define AFX_ADJMATRIX_H__220DF675_DDB5_4E64_BD89_CDDA2C1F7804__INCLUDED_
#include
#include
#include "Stack.h"
#define INT_MAX 0x7FFFFFFF
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
template
void Make2DArray(Type ** & x,int rows,int cols){//创建二维数组x
x = new Type *[rows];//创建行指针
for(int i = 0;i < rows;i++)//为每一行分配空间
x[i] = new Type[cols];
}
template
void Delete2DArray(Type ** & x,int rows){//删除二维数组x
for(int i = 0;i < rows;i++)//释放为每一行所分配的空间
delete[]x[i];
delete[]x;//删除行指针
x = NULL;
}
class AdjMatrix{//方阵类
double **a;//数据缓存区
public:
AdjMatrix(double **b = NULL,int dimention = 0){//初始化方阵
Make2DArray(a,dimention+1,dimention+1);
a[0][0] = dimention;
for(int i = 1,j = 1;i <= dimention,j <= dimention;i++,j++){
a[i][0] = 0;
a[0][j] = 0;
}
if(b)
for(int i1 = 1;i1 <= dimention;i1++)
for(int j1 = 1;j1 <= dimention;j1++)
a[i1][j1] = b[i1-1][j1-1];
}
virtual ~AdjMatrix();//析构函数
AdjMatrix & operator = (const AdjMatrix &);//重载赋值运算符=
void Trs(AdjMatrix &);//矩阵转置:B=trs(*this)
void Show();//显示结果
void ShortestPath_Floyed();//弗洛伊德算法，求每对顶点之间的最短路径
void ShortestPath_Dijkstra(int);//狄克斯特拉算法，求单源最短路径
//输入v为源点编号
};
#endif // !defined(AFX_ADJMATRIX_H__220DF675_DDB5_4E64_BD89_CDDA2C1F7804__INCLUDED_)
// AdjMatrix.cpp: implementation of the AdjMatrix class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "AdjMatrix.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
AdjMatrix::~AdjMatrix(){
int Dim = (int)a[0][0]+1;
Delete2DArray(a,Dim);
}
AdjMatrix & AdjMatrix::operator = (const AdjMatrix &matrix){
int Dim1 = (int)a[0][0],Dim2 = (int)matrix.a[0][0];
Delete2DArray(a,Dim1+1);
Make2DArray(a,Dim2+1,Dim2+1);
for(int i = 0;i <= Dim2;i++)
for(int j = 0;j <= Dim2;j++)
a[i][j] = matrix.a[i][j];
return *this;
}
void AdjMatrix::Trs(AdjMatrix &B){
int Dim1 = (int)a[0][0],Dim2 = (int)B.a[0][0];
Delete2DArray(B.a,Dim2+1);
Make2DArray(B.a,Dim1+1,Dim1+1);
B.a[0][0] = Dim1;
for(int i = 1,j = 1;i <= Dim1,j <= Dim1;i++,j++){
B.a[i][0] = 0;
B.a[0][j] = 0;
}
for(int i1 = 1;i1 <= Dim1;i1++)
for(int j1 = 1;j1 <= Dim1;j1++)
B.a[i1][j1] = a[j1][i1];
}
void AdjMatrix::Show(){
if((int)a[0][0] == 0)
cerr<<"Error!矩阵不存在!
";
else{
for(int i = 1;i <= a[0][0];i++){
for(int j = 1;j <= a[0][0];j++){
if(a[i][j] == INT_MAX)
cout<<setw(5)<<setprecision(7)<<"∞"<<'';
else
cout<<setw(5)<<setprecision(7)<<a[i][j]<<'';
}
cout<<endl;
}
}
}
void AdjMatrix::ShortestPath_Floyed(){
int Dim = (int)a[0][0],pre;
AdjMatrix A,Path;
this->Trs(Path);
Path.Trs(A);//取A=*(this)
for(int i = 1;i <= Dim;i++){
for(int j = 1;j <= Dim;j++)
Path.a[i][j] = -1;
}
for(int k = 1;k <= Dim;k++){
for(int i1 = 1;i1 <= Dim;i1++)
for(int j1 = 1;j1 <= Dim;j1++)
if(A.a[i1][j1] > A.a[i1][k]+A.a[k][j1]){
A.a[i1][j1] = A.a[i1][k]+A.a[k][j1];
Path.a[i1][j1] = k;
}
}
cerr<<"↘Floyed算法求解如下:
";
for(int i2 = 1;i2 <=Dim;i2++){//输出最短路径
for(int j2 = 1;j2 <=Dim;j2++)
if(i2 != j2){
cout"<<j2<<": ";
if(A.a[i2][j2] == INT_MAX){
if(i2 != j2)
cout<<"不存在路径!
";
}
else{
cout<<"路径长度："<<setw(3)<<A.a[i2][j2]<<" ";
cout";
pre = (int)Path.a[i2][j2];
while(pre != -1){
cout";
pre = (int)Path.a[pre][j2];
}
cout<<j2<<endl;
}
}
}
}
void AdjMatrix::ShortestPath_Dijkstra(int v){
int Dim = (int)a[0][0];
AdjMatrix A,temp;
this->Trs(temp);
temp.Trs(A);//取A=*(this)
int *s, *path,u,pre;
s = new int[Dim+1],path = new int[Dim+1];
s[0]=0,path[0]=0;
double *dist,mindis;
dist = new double[Dim+1];
dist[0] = 0.0;
for(int k = 1;k <= Dim;k++){
dist[k] = A.a[v][k];//距离初始化
s[k] = 0;//s[]置空
if(A.a[v][k] < INT_MAX)//路径初始化
path[k] = v;
else
path[k] = -1;
}
s[v] = 1,path[v] = 0;//源点编号v放入s中
for(int i = 1;i <= Dim;i++){//循环直到所有顶点的最短路径都求出
mindis = INT_MAX;
u = -1;
for(int j = 1;j <= Dim;j++){//选取不在s中且具有最小距离的顶点u
if(s[j] == 0 && dist[j] < mindis){
u = j;
mindis = dist[j];
}
}
if(u != -1){
s[u] = 1;
for(int r = 1;r <= Dim;r++)
if(s[r] == 0)
if(A.a[u][r] < INT_MAX && dist[u]+A.a[u][r] < dist[r]){
dist[r] = dist[u]+A.a[u][r];
path[r] = u;
}
}
}
cout<<"↘Dijkstra算法求解如下：
";
Stack st;
for(int i1 = 1;i1 <= Dim;i1++){//输出最短路径的长度，路径逆序输出
if(i1 != v){
cout"<<i1<<": ";
if(s[i1] == 1){
cout<<"路径长度："<<setw(3)<<dist[i1]<<" ";
pre = i1;
cout<<"路径：";
while(pre != v){//一直回溯到初始顶点
st.Push(pre);
pre = path[pre];
}
st.Push(pre);
while(0 < st.GetTop() ){
cout";
}
cout<<st.Pop()<<endl;
}
else
cout<<"不存在路径!
";
}
}
}
// LinkGraph.h: interface for the LinkGraph class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_LINKGRAPH_H__711D918A_0412_49B6_A496_B78EAAB3C611__INCLUDED_)
#define AFX_LINKGRAPH_H__711D918A_0412_49B6_A496_B78EAAB3C611__INCLUDED_
#include
#include
#include
#include "Stack.h"
#define INT_MAX 0x7FFFFFFF
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
struct EdgeNode{ //每一个顶点建立的单链表中结点的类型
int index; //邻接点序号
double value; //边的权值
EdgeNode *next;//下一条边的顶点
EdgeNode(EdgeNode *ne = NULL):next(ne){}//可选择参数的默认构造函数
};
struct VertexNode{ //单链表中头结点类型
char name[32]; //结点信息
int indegree; //入度计数域
EdgeNode *link;//指向第一条边结点
VertexNode(EdgeNode *li = NULL):link(li){}//可选择参数的默认构造函数
};
class LinkGraph{//图的邻接表类
private:
int num;//实际顶点数
VertexNode *adjlist;//单链表头结点数组
public:
LinkGraph(char **names = NULL,double **matrix = NULL,int n = 0){
num = n;
if(names){
EdgeNode *p1,*p2;
int *temp;
temp = new int[num];
for(int k = 0;k < num;k++)
temp[k] = 0;
adjlist = new VertexNode[num];
for(int i = 0;i < num;i++){
strcpy(adjlist[i].name,*(names+i));
for(int j = 0;j < num;j++){
if(matrix[j][i] != 0)
temp[i]++;
if(matrix[i][j] != 0){
adjlist[i].indegree++;
p1 = new EdgeNode;
p1->index = j;
p1->value = matrix[i][j];
if(!adjlist[i].link){
adjlist[i].link = p1;
p2 = p1;
}
else{
p2->next = p1;
p2 = p1;
}
}
}
adjlist[i].indegree = temp[i];
}
}
else
adjlist = NULL;
}
virtual ~LinkGraph();
void Show();
void TopologicalSort();
};
#endif // !defined(AFX_LINKGRAPH_H__711D918A_0412_49B6_A496_B78EAAB3C611__INCLUDED_)
// LinkGraph.cpp: implementation of the LinkGraph class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "LinkGraph.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
LinkGraph::~LinkGraph(){
EdgeNode *p1,*p2;
if(adjlist){
for(int i = 0;i < num;i++){
p1 = adjlist[i].link;
while(p1){
p2 = p1->next;
delete p1;
p1 = p2;
}
}
}
delete []adjlist;
}
void LinkGraph::Show(){
EdgeNode *temp;
if(adjlist){
for(int i = 0;i < num;i++){
if(adjlist[i].link)
cout<<" "<<adjlist[i].name<<":: ";
else
cout<<" "<<adjlist[i].name<<" ";
temp = adjlist[i].link;
while(temp){
coutindex].name<<" ";
temp = temp->next;
}
cout<<endl;
}
}
}
void LinkGraph::TopologicalSort(){
Stack st;
EdgeNode *temp;
int j,k,tag = 0;
for(int i = 0;i < num;i++){
if(adjlist[i].indegree == 0)
st.Push(i);
}
cout<<"↘拓扑排序算法求解如下：
";
while(!st.IsEmpty()){
j = st.Pop();
if(tag%6 == 0)
cout<<"
";
tag ++;
if(tag != num)
cout ";
else
cout<<adjlist[j].name<<endl;
temp = adjlist[j].link;
while(temp){
k = temp->index;
adjlist[k].indegree --;
temp = temp->next;
if(adjlist[k].indegree == 0)
st.Push(k);
}
}
if(num == tag)
cout<<"
拓扑排序成功!
";
else
cout<<"
失败,有向图中存在环!
";
}
// Exercise_4.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include "AdjMatrix.h"
#include "LinkGraph.h"
#define MAXSIZE1 6
#define MAXSIZE2 11
void DisplayMenu();
int main(int argc, char* argv[]){
DisplayMenu();
double a[MAXSIZE1][MAXSIZE1] = { 0, 50, 10,INT_MAX,INT_MAX,INT_MAX,
INT_MAX, 0, 15, 50, 10,INT_MAX,
20, 70, 0, 15,INT_MAX,INT_MAX,
INT_MAX, 20,INT_MAX, 0, 35,INT_MAX,
INT_MAX,INT_MAX,INT_MAX, 30, 0,INT_MAX,
INT_MAX,INT_MAX,INT_MAX, 3,INT_MAX, 0};
char str[MAXSIZE2][32] = {"程序设计","数值分析","普通物理","高等数学","数据结构",
"人工智能","编译原理","操作系统","计算机原理","线性代数","离散数学"};
double b[MAXSIZE2][MAXSIZE2] = {0,1,0,0,1,0,1,0,0,0,1,
0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,1,0,0,
0,1,1,0,0,0,0,0,0,1,0,
0,0,0,0,0,1,1,1,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,
0,1,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,0};
double **matrix1;
Make2DArray(matrix1,MAXSIZE1,MAXSIZE1);
for(int i1 = 0;i1 < MAXSIZE1;i1++){
for(int j1 = 0;j1 < MAXSIZE1;j1++)
matrix1[i1][j1] = a[i1][j1];
}
AdjMatrix A(matrix1,MAXSIZE1);
cout<<"↘邻接矩阵：
";
A.Show();
cout<<"*******************************************************************************
";
A.ShortestPath_Floyed();
cout<<endl;
A.ShortestPath_Dijkstra(2);
char **names;
Make2DArray(names,MAXSIZE2,12);
for(int s = 0;s < MAXSIZE2;s++){
strcpy(*(names+s),*(str+s));
}
double **matrix2;
Make2DArray(matrix2,MAXSIZE2,MAXSIZE2);
for(int i2 = 0;i2 < MAXSIZE2;i2++){
for(int j2 = 0;j2 < MAXSIZE2;j2++)
matrix2[i2][j2] = b[i2][j2];
}
LinkGraph Graph(names,matrix2,MAXSIZE2);
cout<<"*******************************************************************************
";
cout<<"↘邻接表：
";
Graph.Show();
cout<<endl;
Graph.TopologicalSort();
return 0;
}
void DisplayMenu(){
char *menu[]={
" ☆☆ 图 ☆☆ ",
" 1. Floyed算法 2. Dijkstra算法 3. 拓扑排序算法 ",
NULL
};
for(int i=0;menu[i];i++)
cout<<menu[i]<<'
';
}
用C++实现寻找迷宫里最短路线
答：起点由我给定的(x,y),终点是(1,1)迷宫也是已知的一个21*21的二维数组,数组中每一项的值:1表示墙,0表示路最后用一个链表储存下每一步的动作(1234分别代表向上下左右)要求走... 起点由我给定的(x,y),终点是(1,1)迷宫也是已知的一个21*21的二维数组,数组中每一项的值:1表示墙,0表示路最后用一个链表...
...随机生成一个迷宫,然后找出从入口到出口的路线图。急!
答：initmaze();/*初始化迷宫数组*/ findmaze(int i,int j);/*找到了（i,j）可走，标记*/ mapmaze();/*画出原始迷宫*/ int findpath(int row,int col);/*递归函数，找出迷宫路径*/ mapbar();/*画出方格*/ initgrap();/*初始化VGA*/ print();/*迷宫走完后，输出是否成功 */ int s...
关于迷宫出路的问题,已经BFS遍历找到终点了,请问如何能求出路径_百度知...
答：bfs(x1,y1);//打印路径 print(x2,y2);//可求起点到任意点的最短距离
【面试求助】VB或C语言编程
答：你看这样可否：首先我们假定不重复地走格子，因为重复走肯定不是最小路线。以左上角的那个格子作为根节点，找到从该格子出发，下一步可走的格子，然后作为子节点放到根节点下，然后逐个以这些子节点为出发点，递归地按照处理根节点时的办法，继续寻找从子节点出发可走的格子，再作为子节点的子节点放到每...
数据结构C语言版迷宫问题
答：思路：首先，迷宫如何用计算机语言表示？一般用二维数组。0表示墙，1表示路。其次，其次就是如何从迷宫中走出来了。结合堆栈，进行搜索。你可以尝试着对问题进行分层，然后逐步细化来解决。如果你要解决一个别人给的走迷宫的问题，同样还是要这样，首先把别人给的迷宫在计算机中表示出来，其次结合数据结构所...
c语言程序设计题 急用~!!!
答：include <conio.h> include <dos.h> define N 20/*迷宫的大小，可改变*/ int oldmap[N][N];/*递归用的数组,用全局变量节约时间*/ int yes=0;/*yes是判断是否找到路的标志,1找到，0没找到*/ int way[100][2],wayn=0;/*way数组是显示路线用的,wayn是统计走了几个格子*/ void ...
工匠物语2沙漠洞窟最短路线走法讲解
答：沙漠洞窟算是一个比较复杂的迷宫，玩家如果没有合适的线路来选择，就会在里面绕很久，这里来讲解下最短路线应该怎么走，玩家也可以了解下这个捷径。路线讲解括号(A),(B)表示双向传送点→箭头方向表示单向传送点紫色点,表示人物需要(不暴雷)※做上角那块区域无法通过沙漠洞窟内到达I,C,L三个传送点,是...
一道C语言棋盘最优路径的题目,求教
答：Part.5这样一来每个格子对应的3种走法的价值最大值就能得到了如此回到Part.3循环列j = 1..m-1 最后只要取max(k=0,1){f[n-1][m-1][k]} 即可得到最优路径价值和 试着写了一下，不知道能不能过。。注意由于开了1000x1000的long数组，所以VC调试的时候注意把堆栈开大一点 include <...
求路径搜索游戏c/c++代码
答：http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/table_of_contents.html 看看这个,boost的bgl,提供所有的图算法, 你说的可以使用最短路径 :)
C程序设计,三选一,倾囊360分(100悬赏,260追加),7月1号下午前救急有效...
答：printf("\nthe node is: line%d arrange%d \n", element.x, element.y); /* 打印路径上的每一点 */ } } /* 迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径 */ /* 其中 1<=x1,x2<=M-2 , 1<=y1,y2<=N-2 */ void mazePath(int maze[][N],...
