图的简单应用(C/C++实现)

存档:

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define maxv 10//定义最大顶点数
 4 typedef char elem;//图中顶点的数据类型
 5 #include "graph.h"
 6 void main()
 7 {
 8     elem v0;
 9     int v;
10     mgraph g;
11     printf("1.初始化函数测试:\n");
12     initial(g);
13     printf("2.创建函数测试:\n");
14     create(g);
15     printf("3.输出函数测试:\n");
16     printg(g);
17     printf("4.求最短路径:\n");
18     printf("请输出源顶点数据v0:");
19     scanf("%c",&v0);
20     v=locate(g,v0);
21     dijkstra(g,v);
22     printf("5.输出最短路径:\n");
23     printpath(g,v);
24     printf("\n");
25 }
  1 //有向带权网的邻接矩阵,顶点数据为字符型
  2 #define inf 32767
  3 typedef struct MGraph
  4 {
  5     elem vexes[maxv];//顶点表
  6     int edges[maxv][maxv];//邻接矩阵
  7     int n,e;//顶点数n和边数e
  8 }mgraph;
  9 void initial(mgraph &g)//初始化函数
 10 {
 11     int i,j;
 12     g.e=0;
 13     g.n=0;
 14     for(j=0;j<maxv;j++)//建立顶点表
 15         g.vexes[j]=0;
 16     for(i=0;i<maxv;i++)
 17     {
 18         for(j=0;j<maxv;j++)
 19         {
 20             g.edges[i][j]=inf;//初始化邻接矩阵
 21         }
 22     }
 23 }
 24 int locate(mgraph g,elem u)//查找顶点对应的数组下标值
 25 {
 26     for(int i=0;i<g.n;i++)
 27     {
 28         if(g.vexes[i]==u)
 29             return i;
 30     }
 31     return -1;
 32 }
 33 void create(mgraph &g)//创建有向带权网的邻接矩阵存储
 34 {
 35     int i,j,k,w;
 36     elem u,v;
 37     printf("请输入有向图的顶点数:");
 38     scanf("%d",&g.n);
 39     printf("请输入有向图的弧数:");
 40     scanf("%d",&g.e);
 41     fflush(stdin);//清空缓存中的数据
 42     printf("请输入字符型顶点数据,如ABCD:");
 43     for(j=0;j<g.n;j++)
 44         scanf("%c",&g.vexes[j]);//建立顶点表
 45     fflush(stdin);
 46     printf("请输入弧的信息,格式:弧尾,弧头,权值\n");
 47     for(k=0;k<g.e;k++)
 48     {
 49         scanf("%c,%c,%d",&u,&v,&w);
 50         i=locate(g,u);
 51         j=locate(g,v);
 52         g.edges[i][j]=w;
 53         fflush(stdin);
 54     }
 55 }
 56 void printg(mgraph g)//输出有向带权网的邻接矩阵
 57 {
 58     int i,j;
 59     printf("输入图的邻接矩阵存储信息:\n");
 60     printf("顶点数据:\n");
 61     for(i=0;i<g.n;i++)
 62         printf("%d: %c\n",i,g.vexes[i]);
 63     printf("邻接矩阵数据:\n");
 64     for(i=0;i<g.n;i++)
 65     {
 66         for(j=0;j<g.n;j++)
 67         {
 68             if(g.edges[i][j]==inf)
 69                 printf(" ∞");
 70             else
 71                 printf("%3d",g.edges[i][j]);
 72         }
 73         printf("\n");
 74     }
 75 }
 76 int dist[maxv];//dist存当前找到的最短路径长度
 77 int path[maxv];//当前找到的最短路径最后的一个中转顶点
 78 bool s[maxv];//标记当前是否已求出最短路径,false表示没求出,true表示已求出
 79 void dijkstra(mgraph g,int v)//迪杰斯特拉算法从顶点v到其余各顶点的最短路径
 80 {
 81     int mindis,i,j,u;
 82     for(i=0;i<g.n;i++)
 83     {
 84         dist[i]=g.edges[v][i];//当前最短路径长度初始化
 85         s[i]=false;//s[]标记还没求出当前路径
 86         if(g.edges[v][i]<inf)//初始化当前找到的最短路径最后一个中转顶点
 87             path[i]=v;
 88         else
 89             path[i]=-1;
 90     }
 91     s[v]=true;//源点编号v标记已求出最短路径
 92     path[v]=0;//源点v没有前驱顶点
 93     for(i=0;i<g.n;i++)//循环直到所有顶点的最短路径都求出或没有最短路径
 94     {
 95         mindis=inf;
 96         u=-1;//存当前找到的路径最短的新顶点下标
 97         for(j=0;j<g.n;j++)//选取不在s中且具有最小距离的顶点u
 98         {
 99             if((s[j]==false)&&(dist[j]<mindis))
100             {
101                 u=j;
102                 mindis=dist[j];
103             }
104         }
105         if(mindis<inf)//如果找到了新的最短路径
106         {
107             s[u]=true;//新选出顶点u标记为找到了最短路径
108             for(j=0;j<g.n;j++)//修改未找到最短路径顶点信息
109             {
110                 if(s[j]==false)
111                 {
112                     if(g.edges[u][j]<inf&&dist[u]+g.edges[u][j]<dist[j])
113                     {
114                         dist[j]=dist[u]+g.edges[u][j];//修改当前最短路径长度
115                         path[j]=u;//修改当前最短路径最后一个中转点
116                     }
117                 }
118             }
119         }
120     }
121 }
122 void printpath(mgraph g,int v)//输出最短路径和最短路径长度
123 {
124     int i,j,w;
125     int road[maxv];//为输出最短路径做临时存储
126     printf("%c到其他各顶点有没有找到最短路径:\n",g.vexes[v]);
127     for(i=0;i<g.n;i++)
128     {
129         if(s[i])
130             printf("%d:有  ",i);
131         else
132             printf("%d:无  ",i);
133     }
134     printf("\n");
135     for(i=0;i<maxv;i++)
136         road[i]=-1;
137     for(i=0;i<g.n;i++)
138     {
139         if((s[i]==true)&&(i!=v))//当前顶点有最短路径,并且不是源点
140         {
141             printf("从%c到%c的最短路径长度为:%d\t路径为:",g.vexes[v],g.vexes[i],dist[i]);
142             printf("%c->",g.vexes[v]);
143             w=path[i];//最短路径途径的顶点
144             j=0;//为实现逆转标记途径顶点数
145             while(w!=v)//回溯途径顶点
146             {
147                 road[j]=w;
148                 j++;
149                 w=path[w];
150             }
151             for(j--;j>=0;j--)//输出最短路径
152             {
153                 printf("%c->",g.vexes[road[j]]);
154                 road[j]=-1;
155             }
156             printf("%c\n",g.vexes[i]);
157         }
158         else
159             printf("从%c到%c不存在路径\n",g.vexes[v],g.vexes[i]);
160     }
161 }

运行结果如下:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

树上倍增求LCA及例题

先瞎扯几句 树上倍增的经典应用是求两个节点的LCA 当然它的作用不仅限于求LCA,还可以维护节点的很多信息 求LCA的方法除了倍增之外,还有树链剖分、离线tar...

3536
来自专栏大前端_Web

深入理解xhr的responseType中blob和arrayBuffer

版权声明:本文为吴孔云博客原创文章,转载请注明出处并带上链接,谢谢。 https://blog.csdn.net/wkyseo/articl...

2084
来自专栏计算机视觉与深度学习基础

水题第二弹题解

改过的标题很具有迷惑性哦! A POJ3414本次代码量最大的一题,思想是搜索,详细解题报告,请见点击打开链接 B巨水,不要被题目迷惑了,连通图的性质最少需要(...

2707
来自专栏潇涧技术专栏

Problem: Vertext Cover Problem

给定一个N个点M条边的无向图G(点的编号从1至N),问是否存在一个不超过K个点的集合S,使得G中的每条边都至少有一个点在集合S中。

992
来自专栏marsggbo

Udacity并行计算课程笔记-The GPU Hardware and Parallel Communication Patterns

本小节笔记大纲: 1.Communication patterns gather,scatter,stencil,transpose 2.GPU hardwa...

2276
来自专栏java一日一条

简单理解倒排索引

倒排索引从逻辑结构和基本思路上来讲非常简单。下面我们通过具体实例来进行说明,使得读者能够对倒排索引有一个宏观而直接的感受。假设文档集合包含五个文档,每个文档内容...

1092
来自专栏YG小书屋

ES 查询优化(二)

1.1K3
来自专栏C/C++基础

Linux命令(12)——wc命令

(3)从文件读取输入文件名。如果有多个文件名,并且希望 wc 从一个文件中读取它们,那么使用-files0-from 选项。这里将文件名称必须以NULL字符结束...

1011
来自专栏落影的专栏

使用VideoToolbox硬编码H.264

前言 H.264是目前很流行的编码层视频压缩格式,目前项目中的协议层有rtmp与http,但是视频的编码层都是使用的H.264。 在熟悉H.264的过程中,为...

4058
来自专栏码农分享

2、苏宁百万级商品爬取 思路讲解 类别页数爬取

这种方法是为了单独解决这个问题而使用的,很笨拙,因为如果只有200个类别,多线程的意义就没有办法体现出来,这一点在之后的编码中我进行了修改。

1332

扫码关注云+社区

领取腾讯云代金券