#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define MAXV 100 //最大顶点个数
#define INF 32767 //INF表示无穷大
typedef struct{
int no; //顶点编号
int info; //顶点的其他信息
char name[60];
}VertexType; //顶点类型
typedef struct{ //图的定义
int edges[MAXV][MAXV]; //邻接矩阵
int n,e; //顶点数,边数
VertexType vexs[MAXV]; //存放顶点信息
}MGraph;
//以下定义邻接表类型
typedef struct ANode //边的节点结构类型
{ int adjvex; //该边的终点位置
struct ANode *nextarc; //指向下一条边的指针
int info; //该边的相关信息,这里用于存放权值
} ArcNode;
typedef struct Vnode //邻接表头结点的类型
{ int data; //顶点信息
char name[60];
ArcNode *firstarc; //指向第一条弧
} VNode;
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //图的邻接表类型
int visited[MAXV];
//********************************************************
//********************************************************
void MatToList(MGraph g,ALGraph *&G) //将邻接矩阵g转换成邻接表G
{
int i,j; //n为顶点数
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<g.n;i++) //给邻接表中所有头结点的指针域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<g.n;i++) //检查邻接矩阵中每个元素
for (j=g.n-1;j>=0;j--)
if (g.edges[i][j]!=0 && g.edges[i][j]!=INF) //邻接矩阵的当前元素不为0
{
p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*p
p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc; //将*p链到链表后
G->adjlist[i].firstarc=p;
}
for(i=0;i<g.n;i++)
strcpy(G->adjlist[i].name,g.vexs[i].name);
G->n=g.n;G->e=g.e;
}
void DispAdj(ALGraph *G) //输出邻接表G
{
int i;
ArcNode *p;
for (i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
printf("%3d: ",i);
while (p!=NULL)
{
printf("%3d(%d)",p->adjvex,p->info);
p=p->nextarc;
}
printf("\n");
}
}
void FindPath(ALGraph *G,int u,int v,int path[],int d)//G用邻接表存储,输出图G从顶点u到v的所有简单路径
{ //d表示path中的路径长度,初始为-1;
int w,i;
ArcNode *p;
d++;path[d]=u; //路径长度d增1,顶点u加入到数组path中
visited[u]=1; //置顶点u已经访问
if(u==v && d>=1)//找到一条简单路径就输出存储顶点的数组path
{
for(i=0;i<d;i++)
{
printf("%2s→",G->adjlist[path[i]].name);
}
printf("%2s",G->adjlist[path[i]].name);
printf("\n");
}
p=G->adjlist[u].firstarc; //p指向顶点u的第一个相邻点
while(p!=NULL)
{
w=p->adjvex; //w为顶点u的相邻顶点
if(visited[w]==0){ //若顶点w未访问,递归访问它
FindPath(G,w,v,path,d);
}
p=p->nextarc; //p指向顶点u的下一个相邻点
}
visited[u]=0; //恢复环境,使该顶点可重新使用
}
void main(){
int path[MAXV],u=1,v=4,d=-1;
int i,j;
MGraph g;
ALGraph *G;
g.n=5;
g.e=8;
int A[MAXV][MAXV]={
{0,3,0,5,4},{3,0,5,4,0},{0,5,0,2,1},
{5,4,2,0,1},{4,0,1,1,0}};
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.edges[i][j]=A[i][j];
for(i=0;i<g.n;i++)
g.vexs[i].no=i;
strcpy(g.vexs[0].name,"正门");
strcpy(g.vexs[1].name,"教学楼");
strcpy(g.vexs[2].name,"英东楼");
strcpy(g.vexs[3].name,"学生宿舍");
strcpy(g.vexs[4].name,"艺术学院");
MatToList(g,G);
for(i=0;i<g.n;i++)
visited[i]=0;
DispAdj(G);
FindPath(G,u,v,path,d);
}