#include"SeqList.h"
#include"SeqQueue.h"
const int MaxVertices=10;
const int MaxWeight=10000;
class AdjMWGraph
{
private:
SeqList Vertices;//顶点信息的线性表
int Edge[MaxVertices][MaxVertices];
int numOfEdges;
public:
AdjMWGraph(const int sz=MaxVertices);
int GraphEmpty( )const
{return Vertices.ListEmpty( );}
int NumOfVertices(void)
{return Vertices.ListSize( );}
int NumOfEdges(void)
{return numOfEdges;}
VerT GetValue(const int i);
int GetWeight(const int v1,const int v2);
void InsertVertex(const VerT &vertex);
void InsertEdge(const int v1,const int v2,int weight);
void DeleteVertex(const int i);
void DeleteEdge(const int v1,const int v2);
int GetFirstNeighbor(const int v);
int GetNextNeighbor(const int v1,const int v2);
void DepthFirstSearch(const int v,int visited[],void visit(VerT item));
void BroadFirstSearch(const int v,int visited[],void visit(VerT item));
void DepthFirstSearch(void visit(VerT item));
void BroadFirstSearch(void visit(VerT item));
};
AdjMWGraph::AdjMWGraph(const int sz)
{
for(int i=0; i<sz; i++)
for(int j=0; j<sz; j++)
{
if(i == j) Edge[i][j]=0;
else Edge[i][j]=MaxWeight;
}
numOfEdges=0;
}
VerT AdjMWGraph::GetValue(const int i)
{
if(i<0||i>Vertices.ListSize())
{
cerr<<"参数i越界出错!"<<endl;
exit(1);
}
return Vertices.GetData(i);
}
int AdjMWGraph::GetWeight(const int v1,const int v2)
{
if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
{
cerr<<"参数v1或v2越界出错!"<<endl;
exit(1);
}
return Edge[v1][v2];
}
void AdjMWGraph::InsertVertex(const VerT &vertex)
{
Vertices.Insert(vertex,Vertices.ListSize());
}
void AdjMWGraph::InsertEdge(const int v1,const int v2,int weight)
{
if(v1<0||v1>Vertices.ListSize()||v2<0||v2> Vertices.ListSize())
{
cerr<<"参数v1或v2越界出错!"<<endl;
exit(1);
}
Edge[v1][v2]=weight;
numOfEdges++;
}
void AdjMWGraph::DeleteVertex(const int v)
{
for(int i=0;i<Vertices.ListSize();i++)
for(int j=0;j<Vertices.ListSize();j++)
if((i==v||j==v)&&Edge[i][j]>0 &&Edge[i][j]<MaxWeight)
{
Edge[i][j]=MaxWeight;
numOfEdges--;
}
Vertices.Delete(v);
}
void AdjMWGraph::DeleteEdge(const int v1,const int v2)
{
if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()||v1==v2)
{
cerr<<"参数v1或v2出错!"<<endl;
exit(1);
}
Edge[v1][v2]=MaxWeight;
numOfEdges--;
}
int AdjMWGraph::GetFirstNeighbor(const int v)
{
if(v<0||v>Vertices.ListSize( ))
{
cerr<<"参数v1越界出错!"<<endl;
exit(1);
}
for(int col=0;col<=Vertices.ListSize();col++)
if(Edge[v][col]>0&&Edge[v][col]<MaxWeight) return col;
return -1;
}
int AdjMWGraph::GetNextNeighbor(const int v1,const int v2)
{
if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize())
{
cerr<<"参数v1或v2越界出错!"<<endl;
exit(1);
}
for(int col=v2+1; col<=Vertices.ListSize(); col++)
if(Edge[v1][col]>0&&Edge[v1][col]<MaxWeight)return col;
return -1;
}
void AdjMWGraph::DepthFirstSearch(const int v,int visited[],void visit(VerT item))
{
visit(GetValue(v));
visited[v]=1;
int w=GetFirstNeighbor(v);
while(w!=-1)
{
if(!visited[w])DepthFirstSearch(w,visited,visit);
w=GetNextNeighbor(v,w);
}
}
void AdjMWGraph::BroadFirstSearch(const int v,int visited[],void visit(VerT item))
{
VerT u,w;
SeqQueue queue;//定义队列queue
visit(GetValue(v));
visited[v]=1;
queue.QInsert(v);
while(!queue.QueueEmpty())
{
u=queue.QDelete();
w=GetFirstNeighbor(u);
while(w!=-1)
{
if(!visited[w])
{
visit(GetValue(w));
visited[w]=1;
queue.QInsert(w);
}
w=GetNextNeighbor(u,w);
}
}
}
void AdjMWGraph::DepthFirstSearch(void visit(VerT item))
{
int *visited=new int[NumOfVertices()];
for(int i=0;i<NumOfVertices();i++)visited[i]=0;
for(i=0;i<NumOfVertices();i++)
if(!visited[i])DepthFirstSearch(i,visited,visit);
delete []visited;
}
//非连通图的广度优先搜索遍历算法如下
void AdjMWGraph::BroadFirstSearch(void visit(VerT item))
{
int *visited=new int[NumOfVertices()];
for(int i=0;i<NumOfVertices();i++)visited[i]=0;
for(i=0; i<NumOfVertices(); i++)
if(!visited[i]) BroadFirstSearch(i,visited,visit);
delete []visited;
}
struct RowColWeight
{
int row;
int col;
int weight;
};
void CreatGraph(AdjMWGraph &G,Datatype V[],int n,RowColWeight E[],int e)//建图
{
for(int i=0; i<n;i++)G.InsertVertex(V[i]);
for(int k=0; k<e;k++)G.InsertEdge(E[k].row,E[k].col,E[k].weight);
}
void Printchar(char item)
{
cout << item<<" ";
}
void Dijkstra(AdjMWGraph &G,int v0,int distance[],int path[])(迪杰斯特拉算法)
{
int n=G.NumOfVertices();
int *s=new int[n];
int minDis,i,j,u;
for(i=0;i<n;i++)
{
distance[i]=G.GetWeight(v0,i);
s[i]=0;
if(i!=v0&&distance[i]<MaxWeight)path[i]=v0;
else path[i]=-1;
}
s[v0]=1;
for(i=1;i<n;i++)
{
minDis=MaxWeight;
for(j=0;j<=n;j++)
if(s[j]==0&&distance[j]<minDis)
{
u=j;
minDis=distance[j];
}
if(minDis==MaxWeight)return;
s[u]=1;
for(j=0;j<n;j++)
if(s[j]==0&&G.GetWeight(u,j)<MaxWeight&&distance[u]+G.GetWeight(u,j)<distance[j])
{
distance[j]=distance[u]+G.GetWeight(u,j);
path[j]=u;
}
}
}
1. 主函数：
typedef char VerT;
typedef char Datatype;
#include"AdjMWGraph.h"
#include"View.h"
int main()
{
int s,sss=1,j=1;
char ch,qd,zd;
AdjMWGraph g;
char a[]={'A','B','C','D','E','F','G','H','I','J'};
RowColWeight rcw[]={{0,1,20},{0,3,30},{0,4,30},{1,0,20},{2,3,20},{3,0,30},{3,2,20},{3,8,30},{3,9,20},{4,0,30},{4,6,20},{5,6,15},{5,9,15},{6,4,20},{6,5,15},{6,7,10},{7,6,10},{8,3,30},{8,9,15},{9,5,15},{9,8,15}};
int n=10,e=24;
CreatGraph(g,a,n,rcw,e);
int m=g.NumOfVertices();
int *distance=new int[m];
int *path=new int[m];
int v0=0,v1;
Dijkstra(g,v0,distance,path);
end:
if (j==0){system("cls");}
do{
viewshow();
cout<<"1.地点介绍 2.最短路径 3.结束"<<endl<<"请选择功能:";
cin>>s;
system("cls");
if(s==1)
{
do {
viewshow();
cout<<"A.操场 B.偏门 C.图书馆 D.大门 E.食堂"<<endl
<<"F.诚智楼 G.博学楼 H.创新楼 I.海天楼 J.明德楼 "<<endl<<"请选择地点:";
cin>>ch;
switch(ch)
{
case 'A':
zhengdamenshow();
cin.get();
cin.get();
system("cls");break;
case 'B':
mdshow();
cin.get();
cin.get();
system("cls");break;
case 'C':
czshow();
cin.get();
cin.get();
system("cls");break;
case 'D':
bxshow();
cin.get();
cin.get();
system("cls");break;
case 'E':
cxshow();
cin.get();
cin.get();
system("cls");break;
case 'F':
bahaoshow();
cin.get();
cin.get();
system("cls");break;
case 'G':
sitangshow();
cin.get();
cin.get();
system("cls");break;
case 'H':
shihaoshow();
cin.get();
cin.get();
system("cls");break;
case 'I':
caochangshow();
cin.get();
cin.get();
system("cls");break;
case 'J':
tushuguanshow();
cin.get();
cin.get();
system("cls");break;
case'K':
j=0;
goto end;
default:
cout<<"选择有误,请重新选择!"<<endl;
cin.get();
cin.get();
system("cls");
}
} while(1);
}
if(s==2)
{
do {
viewshow();
QIDIAN:
cout<<"请输入起点位置:";
cin>>qd;
if (qd=='A')v0=0;
else if(qd=='B')v0=1;
else if(qd=='C')v0=2;
else if(qd=='D')v0=3;
else if(qd=='E')v0=4;
else if(qd=='F')v0=5;
else if(qd=='G')v0=6;
else if(qd=='H')v0=7;
else if(qd=='I')v0=8;
else if(qd=='J')v0=9;
else {cout<<"起点输入有误，请重新输入!"<<endl;cin.get();cin.get();system("cls");goto QIDIAN;}
cout<<"请输入终点位置:";
cin>>zd;
if (zd=='A')v1=0;
else if(zd=='B')v1=1;
else if(zd=='C')v1=2;
else if(zd=='D')v1=3;
else if(qd=='E')v1=4;
else if(zd=='F')v1=5;
else if(zd=='G')v1=6;
else if(zd=='H')v1=7;
else if(zd=='I')v1=8;
else if(zd=='J')v1=9;
else {cout<<"终点输入有误，请重新输入!"<<endl;cin.get();cin.get();system("cls");goto QIDIAN;}
cout<<"起点"<<g.GetValue(v0)<<"到终点"<<g.GetValue(v1)<<"的最短距离为:"<<distance[v1]<<endl;
cout<<"是否继续查询:1.是 2.否;请选择:";
cin>>sss;
system("cls");
}while(sss==1);
}
if (s==3){cout<<"谢谢使用!"<<endl;return 0;}
}while(1);
}