鱼C论坛

 找回密码
 立即注册
查看: 3868|回复: 2

关于图的简单路径和最短路径

[复制链接]
发表于 2016-12-10 15:23:03 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
#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);
}

我这是带权无向图,我想在简单的路径后面把边的权值和算出来,但老不错,求各位大神!
还有 关于最短路径的求法,到底需要怎么求?小甲鱼的视频看不懂不会用?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-12-10 15:23:38 | 显示全部楼层
有人吗?求救
我这是带权无向图,我想在简单的路径后面把边的权值和算出来,但老不错,求各位大神!
还有 关于最短路径的求法,到底需要怎么求?小甲鱼的视频看不懂不会用?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-5 09:40:29 | 显示全部楼层
参考我的“带权重的最优路径解法”的帖子吧
http://bbs.fishc.com/thread-81073-1-1.html
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 17:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表