关于图的简单路径和最短路径
#include<stdio.h>#include<malloc.h>
#include<string.h>
#define MAXV 100 //最大顶点个数
#define INF 32767 //INF表示无穷大
typedef struct{
int no; //顶点编号
int info; //顶点的其他信息
char name;
}VertexType; //顶点类型
typedef struct{ //图的定义
int edges; //邻接矩阵
int n,e; //顶点数，边数
VertexType vexs; //存放顶点信息
}MGraph;
//以下定义邻接表类型
typedef struct ANode //边的节点结构类型
{ int adjvex; //该边的终点位置
struct ANode *nextarc; //指向下一条边的指针
int info; //该边的相关信息,这里用于存放权值
} ArcNode;
typedef struct Vnode //邻接表头结点的类型
{ int data; //顶点信息
char name;
ArcNode *firstarc; //指向第一条弧
} VNode;
typedef VNode AdjList; //AdjList是邻接表类型
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //图的邻接表类型
int visited;
//********************************************************
//********************************************************
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.firstarc=NULL;
for (i=0;i<g.n;i++) //检查邻接矩阵中每个元素
for (j=g.n-1;j>=0;j--)
if (g.edges!=0 && g.edges!=INF) //邻接矩阵的当前元素不为0
{
p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*p
p->adjvex=j;
p->info=g.edges;
p->nextarc=G->adjlist.firstarc; //将*p链到链表后
G->adjlist.firstarc=p;
}
for(i=0;i<g.n;i++)
strcpy(G->adjlist.name,g.vexs.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.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=u; //路径长度d增1，顶点u加入到数组path中
visited=1; //置顶点u已经访问
if(u==v && d>=1)//找到一条简单路径就输出存储顶点的数组path
{
for(i=0;i<d;i++)
{
printf("%2s→",G->adjlist].name);
}
printf("%2s",G->adjlist].name);
printf("\n");
}
p=G->adjlist.firstarc; //p指向顶点u的第一个相邻点
while(p!=NULL)
{
w=p->adjvex; //w为顶点u的相邻顶点
if(visited==0){ //若顶点w未访问，递归访问它
FindPath(G,w,v,path,d);
}
p=p->nextarc; //p指向顶点u的下一个相邻点
}
visited=0; //恢复环境，使该顶点可重新使用
}
void main(){
int path,u=1,v=4,d=-1;
int i,j;
MGraph g;
ALGraph *G;
g.n=5;
g.e=8;
int A={
{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=A;
for(i=0;i<g.n;i++)
g.vexs.no=i;
strcpy(g.vexs.name,"正门");
strcpy(g.vexs.name,"教学楼");
strcpy(g.vexs.name,"英东楼");
strcpy(g.vexs.name,"学生宿舍");
strcpy(g.vexs.name,"艺术学院");
MatToList(g,G);
for(i=0;i<g.n;i++)
visited=0;
DispAdj(G);
FindPath(G,u,v,path,d);
}
我这是带权无向图，我想在简单的路径后面把边的权值和算出来，但老不错，求各位大神！
还有 关于最短路径的求法，到底需要怎么求？小甲鱼的视频看不懂不会用？{:10_285:} 有人吗？求救
我这是带权无向图，我想在简单的路径后面把边的权值和算出来，但老不错，求各位大神！
还有 关于最短路径的求法，到底需要怎么求？小甲鱼的视频看不懂不会用？ 参考我的“带权重的最优路径解法”的帖子吧
http://bbs.fishc.com/thread-81073-1-1.html
页:
[1]