#include
#include
#include
#define TRUE 1
#define FALSE 0
#define MAX_VERTEX_NUM 20
#define MAX_EDGE 20
#define MAX 30
#define INFINT 32765
int visited[MAX_VERTEX_NUM]; /*定义全局变量 纪录是否访问图节点*/
int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*用来记录两点间的最短路径的长度*/
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
int length ; /*两个点的的距离*/
char arcname[20];/*存储路的名称*/
char arcinfo[100];/*路的信息*/
}ArcNode;
typedef struct VertexNode
{ char mark;
char name[30];
char info[100];
ArcNode *firstarc;
}VertexNode;
typedef struct
{
VertexNode vertex[MAX];
int vexNum,arcNum;
}AdjList;
typedef struct
{
char vexname[MAX_VERTEX_NUM];/*所访问的节点名称*/
int last;
}SeqList;
SeqList path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
char adjvex;
int lowcost;
}edge;
edge closedge[MAX_EDGE];
char pathsave[11];/*存储两点间所有路径*/
void searchAllPath(AdjList *g, int start, int end, int place1);
void Menu(AdjList *g);
void display_RoadInfo(AdjList *g,int orp,int tep);
void Init(AdjList *g);
void LoadNum(AdjList *g);
void Create_Graph(AdjList *g);/*创建图*/
void visit(AdjList *g,int v);
void DepthFirstSearch(AdjList *g,int v0);
void printgraph(AdjList *g);
void Push(ArcNode **s,ArcNode *q);
void DFSGraph(AdjList *g,int v0);
void Initdist();/*初始化两点间的距离，置为INFINT*/
void InitList(SeqList *path);
void AddTail(SeqList*path,char ch);
SeqList JoinList(SeqList *path1,SeqList *path2);
void ShortestPath_Floyd(AdjList *g,int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM],SeqList path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]);
void MinSpanTree(AdjList *g,char u);
int LocateVertex(AdjList *g,char v);
int Minium(edge dge[]);
void clean();
int main()
{
AdjList *g;
int v =1;
g = (AdjList *)malloc(sizeof(AdjList));
LoadNum(g);
Init(g);
Initdist();
Create_Graph(g);
Menu(g);
return 0;
}
void Menu(AdjList *g)
{
int select = -1;
int u,v;
char ch;
int a =0;
int i;
system("clear");
printf("**********************************************************\n");
printf("**** 1.查找任意结点的信息 ****\n");
printf("**** 2.查找路的信息 ****\n");
printf("**** 3.任意两点间的最短距离 ****\n");
printf("**** 4.深度优先任意景点出发访问所有景点 ****\n");
printf("**** 5.普里姆法任意景点出发访问所有景点 ****\n");
printf("**** 6.任意两点之间的所有路径 ****\n");
printf("**** 0.退出 ****\n");
printf("**********************************************************\n");
printf("请输入你想选择等功能：");
scanf("%d",&select);
getchar();
switch(select){
case 0: break;
case 1:{
printf("请输入要查询的结点编号:");
scanf("%d",&u);
getchar();
printf("结点的名称是：%s\n",g->vertex[u].name);
printf("序号是：%c\n",g->vertex[u].mark);
printf("概况：%s\n",g->vertex[u].info);
printf("是否继续查询(y/n)?");
scanf("%c",&ch);
getchar();
if(ch == 'y'||ch == 'Y')
Menu(g);
else break;
}
case 2:{
printf("输入你想要查找的两个端点序号(0~10):");
scanf("%d %d",&u,&v);
getchar();
display_RoadInfo(g,u,v);
printf("是否继续查询(y/n)?");
scanf("%c",&ch);
getchar();
if(ch == 'y'||ch == 'Y')
Menu(g);
else break;
}
case 3:{
ShortestPath_Floyd(g,dist,path);
printf("是否继续查询(y/n)?");
scanf("%c",&ch);
getchar();
printf("%c ",ch);
clean();
if(ch == 'y'||ch == 'Y')
Menu(g);
else break;
}
case 4:{
printf("请输入您想从那个景点开始遍历整个景区(1~10):");
scanf("%d",&u);
getchar();
DFSGraph(g,u);
printf("是否继续查询(y/n)?");
scanf("%c",&ch);
getchar();
clean();
if(ch == 'y'||ch == 'Y')
Menu(g);
else break;;
}
case 5:{
printf("请输入您想从那个景点开始遍历整个景区:(A~J)");
scanf("%c",&ch);
getchar();
MinSpanTree(g,ch);
printf("是否继续查询(y/n)?");
scanf("%c",&ch);
getchar();
clean();
if(ch == 'y'||ch == 'Y')
Menu(g);
else break;
}
case 6:{
printf("请输入两点的编号:(1~10)");
scanf("%d %d",&u,&v);
// printf("%d %d",u,v);
getchar();
searchAllPath(g,u,v,a);
printf("是否继续查询(y/n)?");
scanf("%c",&ch);
getchar();
clean();
if(ch == 'y'||ch == 'Y')
Menu(g);
else break;
}
}
}
void display_RoadInfo(AdjList *g,int orp,int tep)
{
ArcNode *p;
p =(ArcNode *)malloc(sizeof(ArcNode));
p = g->vertex[orp].firstarc;
while(p){
if(p->adjvex == tep){
printf("起点:%s \n终点:%s\n",g->vertex[orp].name,g->vertex[tep].name);
printf("路名：%s\n",p->arcname);
printf("路长：%d\n",p->length);
printf("信息:%s\n",p->arcinfo);
break;
}
p = p->nextarc;
}
if(p==NULL)
printf("没有从%s==>%s的直接路径!\n",g->vertex[orp].name,g->vertex[tep].name);
}
/**************************************************************
* 该函数用来读取结点数和于中的边数 *
***************************************************************/
void LoadNum(AdjList *g)
{
FILE *in;
if((in=fopen("Number.in","r"))==NULL){
printf("Cannot open the file Number.in!\n");
exit(0);
}
fscanf(in,"%d %d",&g->vexNum,&g->arcNum);
fclose(in);
}
void Init(AdjList *g)
{
int i = 0;
FILE *in;
if((in = fopen("schoolInfo.in","r")) == NULL){
printf("Cannot open the file schoolInfo.in!\n");
exit(0);
}
for(i = 1;i <=g->vexNum;i ++){
visited[i] = 0;
fscanf(in,"%c %s %s\n",&g->vertex[i].mark,g->vertex[i].name,g->vertex[i].info);
g ->vertex[i].firstarc = NULL;
printf("%c %s %s\n",g->vertex[i].mark,g->vertex[i].name,g->vertex[i].info);
}
fclose(in);
}
void printgraph(AdjList *g)
{
int i =0;
ArcNode *p;
for(i = 0;i
// printf("hhh\n");
printf("%c->",g->vertex[i].mark);
p = g->vertex[i].firstarc;
while(p!=NULL) {
printf("%d->",p->adjvex);
p = p->nextarc;
}
// printf("\n");
}
return ;
}
void Create_Graph(AdjList *g)
{
int i;
int locate1,locate2;
ArcNode *p,*q;
FILE *in;
if((in = fopen("roadInfo.in","r")) ==NULL){
printf("Cannot open the file roadLength.in");
exit(0);
}
for(i = 1;i <= g->vexNum;i ++){
g->vertex[i].firstarc = NULL;
// printf("%d ",g->vexNum);
}
for(i = 1;i <= g->arcNum; i ++){
p =(ArcNode *)malloc(sizeof(ArcNode));
q = (ArcNode *)malloc(sizeof(ArcNode));/*存储对称路径信息*/
p -> nextarc =NULL;
q -> nextarc = NULL;
fscanf(in,"%d %d %d %s %s",&locate1,&locate2,&p->length,p ->arcname,p->arcinfo);
p -> adjvex = locate2;
q -> adjvex = locate1;
dist[locate1][locate2] = p->length;/*初始化两点之间的距离*/
q -> length = p-> length; /*两条路的长度是一样的，只是结点顺序不同*/
dist[locate2][locate1] = q -> length;
strcpy(q->arcname,p->arcname);
strcpy(q->arcinfo,p->arcinfo);
p -> nextarc = g->vertex[locate1].firstarc;/*将边结点插入到表图结点之后*/
q -> nextarc = g->vertex[locate2].firstarc;
g->vertex[locate1].firstarc = p;
g->vertex[locate2].firstarc = q;
}
/* for(i = 1;i <=g->vexNum;i ++){
p = g->vertex[i].firstarc;
while(p){
printf("%d->%d 's length: %d name:%s\n",i,p->adjvex,p->length,p->arcname);
p = p->nextarc;
}
}
*/
}
void visit(AdjList *g,int v)
{
printf("%s ",g->vertex[v].name);
}
void Push(ArcNode **s,ArcNode *q)
{
*s = (ArcNode *)malloc(sizeof(ArcNode));
*s = q;
}
/************************************************
* 深度遍历非递归算法 *
************************************************/
void DFSGraph(AdjList *g,int v0)
{
ArcNode *s[MAX_VERTEX_NUM];
ArcNode *p;
int v;
int i;
int top = -1;
p =(ArcNode *)malloc(sizeof(ArcNode));
visit(g,v0);
visited[v0] = TRUE;
top = top +1;
Push(&s[top],g -> vertex[v0].firstarc);
while(top >= 0){
p = s[top --];
if(p != NULL){
top = top + 1;
Push(&s[top],p->nextarc);
v = p->adjvex;
if(!visited[v]){
visit(g,v);
visited[v] = TRUE;
top = top +1;
Push(&s[top],g->vertex[v].firstarc);
}
}
}
printf("\n");
// for(i = 0;i <=)
}
/*************************************************************
*以下函数是实现任意两点之间最短距离的弗洛伊德算法所依赖的函数*
*************************************************************/
void Initdist()/*初始化两点间的距离，置为INFINT*/
{
int i,j;
for(i = 0;i
dist[i][j] = INFINT;
}
void InitList(SeqList *path)
{
// int i;
path->last = -1;
}
void AddTail(SeqList *path,char ch)
{
int k;
// path =(SeqList *)malloc(sizeof(SeqList));
path->last ++;
//JoinList(path1,path2);
path->vexname[path->last] = ch;
k = path->last + 1;
path->vexname[k]='\0';
}
SeqList JoinList(SeqList *path1,SeqList *path2)
{
SeqList path11;
strcpy(path11.vexname,path1->vexname);
strcat(path11.vexname,path2->vexname);
path11.last =path1->last+path2->last+2;
return path11;
}
void ShortestPath_Floyd(AdjList *g,int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM],SeqList path[MAX_VERTEX_NUM][MAX_VERTEX_NUM])
{
int i,j,k,jj;
int p1,p2;
for(i = 1;i <= g->vexNum;i ++ ) {
for(j = 1;j <= g->vexNum;j ++ ){
InitList(&path[i][j]);
if(dist[i][j] < INFINT){
AddTail(&path[i][j],g->vertex[i].mark);
AddTail(&path[i][j],g->vertex[j].mark);
}
}
}
for(k =1;k<= g->vexNum;k ++){
for(i =1;i<= g->vexNum;i ++)
for(j =1;j <=g->vexNum;j ++){
if(dist[i][k]+dist[k][j] < dist[i][j]){
dist[i][j] = dist[i][k] +dist[k][j];
path[i][j] = JoinList(&path[i][k],&path[k][j]);
}
}
}
printf("input 2 place: ");
scanf("%d %d",&i,&j);
getchar();
for(k = 0;k
for(jj = k;jj
}
}
}
printf("path is :%s\n",path[i][j].vexname);
}
/*********************************************************************
* 从顶点U出发，按照普理姆算法构造连通网g的最小生成树 *
* 并输出生成树的每条边 *
*********************************************************************/
void MinSpanTree(AdjList *g,char u)
{
int k,i,e;
int k0;
char u0,v0;
k =LocateVertex(g,u);
closedge[k].lowcost = 0;
for(i =1;i <= g->vexNum;i ++){
if(i != k){
closedge[i].adjvex = u;
closedge[i].lowcost = dist[k][i];
}
}
for(e = 2;e <= g->vexNum;e ++){
k0 = Minium(closedge); /*closedge[k0]中存有当前最小边(u0,v0)的信息*/
u0 = closedge[k0].adjvex;
v0 = g->vertex[k0].mark;
printf("%c",v0);/*将生成树的当前最小边打印出*/
closedge[k0].lowcost = 0;/*将顶点v0纳入集合U中*/
for(i = 1; i <= g->vexNum;i ++){/*将顶点v0并入U后,更新closedge[i]*/
if(dist[k0][i] < closedge[i].lowcost){
closedge[i].lowcost = dist[k0][i];
closedge[i].adjvex = v0;
}
}
}
}
int LocateVertex(AdjList *g,char v)
{
int i;
int flag =-1;
for(i = 1;i <= g->vexNum;i ++){
if(g->vertex[i].mark == v){
flag = i;
break;
}
}
return (flag);
}
int Minium(edge dge[])
{
int i;
int min=INFINT,flag;
for(i = 1; i <= MAX_EDGE;i ++){
if(min > dge[i].lowcost &&dge[i].lowcost != 0){
min = dge[i].lowcost;
flag = i;
}
}
return flag;
}
/*************************************************************************
＊ 以下函数主要实现从一点到任一点的所有路径的实现 *
*************************************************************************/
void searchAllPath(AdjList *g, int start, int end, int place1)
//求有向图G中顶点start到end之间的所有简单路径,length表示当前路径长度
{
ArcNode *p;
int i, t = 0;
int k;
pathsave[place1] = (char)(start+64); //加入当前路径中
visited[start] = 1;
if(start == end) //找到了一条简单路径
{
printf("找到一条路径:\n");
for(i=0; i <= place1; i++)
printf("%c ",pathsave[i]); //打印输出
printf("\n");
}
else
for(p = g->vertex[start].firstarc; p != NULL ; p = p->nextarc)
{
t=p->adjvex;
if(visited[t] == 0)
searchAllPath(g , t, end, place1 + 1); //继续寻找
}
visited[start] = 0;
pathsave[place1]= '\0'; //回溯
}
/*对visited进行清0*/
void clean()
{
int i =0;
for(i = 0;i < MAX_VERTEX_NUM;i ++){
visited[i] = 0;
}
}