#define MaxVertexNum 35
#define MAX 40
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#include<iostream.h>
typedef struct arcell //邊的權值信息
{
int adj; //權值
}arcell,adjmatrix[MaxVertexNum][MaxVertexNum]; //圖的鄰接矩陣類型
typedef struct vexsinfo //頂點信息
{
int position; //景點的編號
char name[32]; //景點的名稱
char introduction[256]; //景點的介紹
}vexsinfo;
typedef struct mgraph //圖結構信息
{
vexsinfo vexs[MaxVertexNum]; //頂點向量(數組)
adjmatrix arcs; //鄰接矩陣
int vexnum,arcnum; //分別指定頂點數和邊數
}mgraph;
//全局變量
int visited[35]; //用於標誌是否已經訪問過
int d[35]; //用於存放權值或存儲路徑頂點編號
mgraph campus; //圖變量(大學校園)
// (1) 對圖初始化
mgraph initgraph()
{
int i=0,j=0;
mgraph c;
c.vexnum =28; //頂點個數
c.arcnum =39; //邊的個數
for(i=0;i<c.vexnum ;i++) //依次設置頂點編號
c.vexs[i].position =i;
//依次輸入頂點信息
strcpy(c.vexs[0].name ,"小西南門");
strcpy(c.vexs[0].introduction ,"離公交站近");
strcpy(c.vexs[1].name ,"學校南正門");
strcpy(c.vexs[1].introduction ,"學校大門、學校班車進出口");
strcpy(c.vexs[2].name ,"語言文化職業學院");
strcpy(c.vexs[2].introduction ,"語言文化職業學院辦公樓，樓高6層");
strcpy(c.vexs[3].name ,"藝術學院");
strcpy(c.vexs[3].introduction ,"音樂系、美術系，樓高4層");
strcpy(c.vexs[4].name ,"行政樓");
strcpy(c.vexs[4].introduction ,"行政辦公大樓，樓高5層");
strcpy(c.vexs[5].name,"文學院");
strcpy(c.vexs[5].introduction ,"文學院，樓高6層");
strcpy(c.vexs[6].name ,"體育場");
strcpy(c.vexs[6].introduction ,"室外標準田徑場");
strcpy(c.vexs[7].name,"教育科學學院");
strcpy(c.vexs[7].introduction ,"教心系、經管系，樓高5層");
strcpy(c.vexs[8].name ,"南區學生宿舍");
strcpy(c.vexs[8].introduction ,"離西南門近");
strcpy(c.vexs[9].name, "數學與經濟管理學院");
strcpy(c.vexs[9].introduction , "數學與經濟管理學院大樓，樓高4層");
strcpy(c.vexs[10].name ,"中區學生宿舍");
strcpy(c.vexs[10].introduction ,"若幹棟，離學生1、2食堂近");
strcpy(c.vexs[11].name ,"職業學院教學大樓");
strcpy(c.vexs[11].introduction ,"職業學院教學大樓，樓高5層");
strcpy(c.vexs[12].name ,"體育系");
strcpy(c.vexs[12].introduction ,"體育系，樓高5層");
strcpy(c.vexs[13].name ,"遊泳館");
strcpy(c.vexs[13].introduction ,"室內小型遊泳館");
strcpy(c.vexs[14].name ,"報告廳、階梯教室");
strcpy(c.vexs[14].introduction ,"可舉辦中、大型學術會議。有大小報告廳1－6個、階梯教室1－6個");
strcpy(c.vexs[15].name ,"大禮堂、體育館");
strcpy(c.vexs[15].introduction ,"文藝演出所在地、室內運動場");
strcpy(c.vexs[16].name ,"1食堂");
strcpy(c.vexs[16].introduction ,"教工食堂及學生1食堂在此");
strcpy(c.vexs[17].name ,"新圖書館");
strcpy(c.vexs[17].introduction ,"建築面積46000平方米");
strcpy(c.vexs[18].name ,"2食堂");
strcpy(c.vexs[18].introduction ,"學校東區，學生食堂");
strcpy(c.vexs[19].name ,"東區學生宿舍");
strcpy(c.vexs[19].introduction ,"離學生2食堂近");
strcpy(c.vexs[20].name ,"計算機學院");
strcpy(c.vexs[20].introduction ,"計算機學院大樓，樓高5層");
strcpy(c.vexs[21].name ,"教工宿舍");
strcpy(c.vexs[21].introduction ,"學校青年教職工租住地");
strcpy(c.vexs[22].name ,"西區學生宿舍");
strcpy(c.vexs[22].introduction ,"離學生3、4食堂近");
strcpy(c.vexs[23].name ,"3食堂");
strcpy(c.vexs[23].introduction ,"學校西區，學生食堂");
strcpy(c.vexs[24].name ,"外國語學院");
strcpy(c.vexs[24].introduction ,"外國語學院大樓，樓高5層");
strcpy(c.vexs[25].name ,"4食堂");
strcpy(c.vexs[25].introduction ,"學校西區，學生食堂，人氣較高");
strcpy(c.vexs[26].name ,"校醫院");
strcpy(c.vexs[26].introduction ,"看小病的地方");
strcpy(c.vexs[27].name ,"實驗樓");
strcpy(c.vexs[27].introduction ,"物電學院、化學與生命科學學院、機電系、建材系所在地，機房及多媒體教室若幹");
//依次輸入邊上的權值信息
for(i=0;i<c.vexnum ;i++)
for(j=0;j<c.vexnum ;j++)
c.arcs [i][j].adj =Infinity; //先初始化圖的鄰接矩陣
//部分弧長
c.arcs[0][2].adj=50; c.arcs[0][3].adj=60;
c.arcs[1][4].adj=90;
c.arcs[2][3].adj=60; c.arcs[2][8].adj=40;
c.arcs[3][4].adj=60; c.arcs[3][6].adj=40;
c.arcs[4][5].adj=70; c.arcs[4][9].adj=70; c.arcs[4][10].adj=80; c.arcs[4][17].adj=200;
c.arcs[5][7].adj=70;
c.arcs[6][9].adj=40;
c.arcs[7][18].adj=190;
c.arcs[8][11].adj=50;
c.arcs[9][12].adj=40;
c.arcs[10][18].adj=70;
c.arcs[11][12].adj=60; c.arcs[11][14].adj=50; c.arcs[11][15].adj=50;
c.arcs[12][16].adj=50;
c.arcs[13][14].adj=40; c.arcs[13][22].adj=60;
c.arcs[14][15].adj=50; c.arcs[14][20].adj=90;
c.arcs[15][16].adj=60; c.arcs[15][21].adj=40;
c.arcs[16][17].adj=60;
c.arcs[17][18].adj=80;
c.arcs[18][19].adj=60;
c.arcs[20][21].adj=60; c.arcs[20][24].adj=80;
c.arcs[22][23].adj=60; c.arcs[22][25].adj=80;
c.arcs[23][24].adj=60;
c.arcs[24][26].adj=100; c.arcs[24][27].adj=100;
c.arcs[25][26].adj=90;
c.arcs[26][27].adj=90;
for(i=0;i<c.vexnum ;i++) //鄰接矩陣是對稱矩陣，對稱賦值
for(j=0;j<c.vexnum ;j++)
c.arcs[j][i].adj =c.arcs[i][j].adj ;
return c;
}//initgraph
// (2) 查找景點在圖中的序號
int locatevex(mgraph c,int v)
{
int i;
for(i=0;i<c.vexnum ;i++)
if(v==c.vexs[i].position)
return i; //找到，返回頂點序號i
return -1; //否則，返回-1
}
//(3) 、(4) 求兩景點間的所有路徑
// (3) 打印序號為m,n景點間的長度不超過8個景點的路徑
void path(mgraph c, int m,int n,int k)
{
int s,x=0;
int t=k+1; //t 記載路徑上下壹個中間頂點在d[]數組中的下標
if(d[k]==n && k<8) //d[k]存儲路徑頂點。若d[k]是終點n且景點個數<=8，則輸出該路徑
{ //遞歸出口，找到壹條路徑
for(s=0;s<k;s++)
printf("%s--->",c.vexs[d[s]].name); //輸出該路徑。s=0 時為起點m
printf("%s",c.vexs[d[s]].name); //輸出最後壹個景點名(即頂點n的名字，此時s==k)
printf("\n\n");
}
else
{
s=0;
while(s<c.vexnum) //從第m個頂點，試探至所有頂點是否有路徑
{
if((c.arcs[d[k]][s].adj<Infinity) && (visited[s]==0)) //初態：頂點m到頂點s有邊，且未被訪問
{
visited[s]=1;
d[k+1]=s; //存儲頂點編號s 至d[k+1]中
path(c,m,n,t); //求從下標為t=k+1的第d[t]個頂點開始的路徑(遞歸調用)，同時打印出壹條m至n的路徑
visited[s]=0; //將找到的路徑上頂點的訪問標誌重新設置為0，以用於試探新的路徑
}
s++; //試探從下壹個頂點 s 開始是否有到終點的路徑
}//endwhile
}//endelse
}//endpath
//(4) 打印兩景點間的景點個數不超過8的所有路徑。調用(3)
int allpath(mgraph c)
{
int k,i,j,m,n;
printf("\n\n請輸入妳要查詢的兩個景點編號:\n\n");
scanf("%d%d",&i,&j);
printf("\n\n");
m=locatevex(c,i); //調用(2)，確定該頂點是否存在。若存在，返回該頂點編號
n=locatevex(c,j);
d[0]=m; //存儲路徑起點m (int d[]數組是全局變量)
for(k=0;k<c.vexnum;k++) //全部頂點訪問標誌初值設為0
visited[k]=0;
visited[m]=1; //第m個頂點訪問標誌設置為1
path(c,m,n,0); //調用(3)。k=0，對應起點d[0]==m。k為d[]數組下標
return 1;
}
// (5) 用迪傑斯特拉算法，求出壹個景點到其他景點間的最短路徑，並打印
void shortestpath_dij(mgraph c)
{
//迪傑斯特拉算法，求從頂點v0到其余頂點的最短路經及其帶權長度d[v]
//若p[v][w]為1，則w是從v0到v的最短路經上的頂點
//final[v]類型用於設置訪問標誌
int v,w,i,min,t=0,x,flag=1,v0; //vo為起始景點的編號
int final[35],d[35],p[35][35];
printf("\n請輸入壹個起始景點的編號：");
scanf("%d",&v0);
printf("\n\n");
while(v0<0||v0>c.vexnum)
{
printf("\n妳所輸入的景點編號不存在\n");
printf("請重新輸入：");
scanf("%d",&v0);
}//while
for(v=0;v<c.vexnum ;v++)
{
final[v]=0; //初始化各頂點訪問標誌
d[v]=c.arcs[v0][v].adj; //v0 到各頂點 v 的權值賦值給d[v]
for(w=0;w<c.vexnum ;w++) //初始化p[][]數組，各頂點間的路徑全部設置為空路徑0
p[v][w]=0;
if(d[v]<Infinity) //v0 到v 有邊相連，修改p[v][v0]的值為1
{
p[v][v0]=1;
p[v][v]=1; //各頂點自己到自己要連通
}
}//for
d[v0]=0; //自己到自己的權值設為0
final[v0]=1; //v0的訪問標誌設為1，v 屬於 s 集
for(i=1;i<c.vexnum ;i++) //對其余c.vexnum-1個頂點w，依次求 v 到 w 的最短路徑
{
min=Infinity;
for(w=0;w<c.vexnum ;w++) //在未被訪問的頂點中，查找與 v0 最近的頂點v
if(!final[w])
if(d[w]<min) //v0 到 w (有邊)的權值<min
{
v=w;
min=d[w];
}//if
final[v]=1; //v 的訪問標誌設置為1，v 屬於s集
for(w=0;w<c.vexnum ;w++) //修改v0 到其余各頂點w 的最短路徑權值d[w]
if(!final[w]&&(min+c.arcs[v][w].adj <d[w])) //若w 不屬於s，且v 到w 有邊相連
{
d[w]=min+c.arcs[v][w].adj; //修改v0 到w 的權值d[w]
for(x=0;x<c.vexnum ;x++) //所有v0 到v 的最短路徑上的頂點x，都是v0 到w 的最短路徑上的頂點
p[w][x]=p[v][x];
p[w][w]=1;
}//if
}//for
for(v=0;v<c.vexnum ;v++) //輸出v0 到其它頂點v 的最短路徑
{
if(v!=v0)
printf("%s",c.vexs[v0].name); //輸出景點v0 的景點名
for(w=0;w<c.vexnum ;w++) //對圖中每個頂點w，試探w 是否是v0 到v 的最短路徑上的頂點
{
if(p[v][w] && w!=v0 && w!=v) //若w 是且w 不等於v0，則輸出該景點
printf("--->%s",c.vexs[w].name);
}
printf("---->%s",c.vexs[v].name);
printf("\n總路線長為%d米\n\n",d[v]);
}//for
}//shortestpath
//(6)-(11)修改圖的信息。包括建圖、更新信息、刪除、增加結點和邊
//(6) 構造圖的鄰接矩陣
int creatgragh(mgraph &c) //建圖。以圖的鄰接矩陣存儲圖
{
int i,j,m,n;
int v0,v1;
int distance;
printf("請輸入圖的頂點數和邊數: \n");
scanf("%d %d",&c.vexnum ,&c.arcnum );
printf("下面請輸入景點的信息：\n");
for(i=0;i<c.vexnum ;i++) //構造頂點向量(數組)
{
printf("請輸入景點的編號：");
scanf("%d",c.vexs[i].position );
printf("\n請輸入景點的名稱：");
scanf("%s",c.vexs[i].name );
printf("\n請輸入景點的簡介：");
scanf("%s",c.vexs[i].introduction );
}
for(i=0;i<c.arcnum ;i++) //初始化鄰接矩陣
for(j=0;j<c.arcnum ;j++)
c.arcs[i][j].adj =Infinity;
printf("下面請輸入圖的邊的信息：\n");
for(i=1;i<=c.arcnum ;i++) //構造鄰接矩陣
{
printf("\n第%d條邊的起點 終點 長度為：",i);//輸入壹條邊的起點、終點及權值
scanf("%d %d %d",&v0,&v1,&distance);
m=locatevex(c,v0);
n=locatevex(c,v1);
if(m>=0 && n>=0)
{
c.arcs[m][n].adj =distance;
c.arcs[n][m].adj =c.arcs[m][n].adj ;
}
}
return 1;
}//creatgragh
// (7) 更新圖的部分信息。返回值: 1
int newgraph(mgraph &c)
{
int changenum; //計數。用於記錄要修改的對象的個數
int i,m,n,t,distance,v0,v1;
printf("\n下面請輸入妳要修改的景點的個數：\n");
scanf("%d",&changenum);
while(changenum<0||changenum>c.vexnum )
{
printf("\n輸入錯誤！請重新輸入");
scanf("%d",&changenum);
}
for(i=0;i<changenum;i++)
{
printf("\n請輸入景點的編號：");
scanf("%d",&m);
t=locatevex(c,m);
printf("\n請輸入景點的名稱：");
scanf("%s",c.vexs[t].name );
printf("\n請輸入景點的簡介：");
scanf("%s",c.vexs[t].introduction );
}
printf("\n下面請輸入妳要更新的邊數");
scanf("%d",&changenum);
while(changenum<0||changenum>c.arcnum )
{
printf("\n輸入錯誤！請重新輸入");
scanf("%d",&changenum);
}
printf("\n下面請輸入更新邊的信息：\n");
for(i=1;i<=changenum ;i++)
{
printf("\n修改的第%d條邊的起點 終點 長度為：",i);
scanf("%d %d %d",&v0,&v1,&distance);
m=locatevex(c,v0);
n=locatevex(c,v1);
if(m>=0&&n>=0)
{
c.arcs[m][n].adj =distance;
c.arcs[n][m].adj =c.arcs[m][n].adj ;
}
}
return 1;
}//newgraph