用c语言建立邻接矩阵(图的邻接矩阵和最短路径)

图(Graph)是由顶点(Vertex)的有穷非空集合和顶点之间边(Edge)的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。图中的数据元素,我们称之为顶点(Vertex),顶点集合有穷非空。在图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的。

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。

用一个顺序表来存储顶点信息

用邻接矩阵(二维数组)表示顶点间的相邻关系

图按照有无方向分为无向图和有向图。无向图由顶点和边组成,有向图由顶点和弧构成。弧有弧尾和弧头之分,带箭头一端为弧头。

图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度。有向图顶点分为入度和出度。

图上的边或弧带有权则称为网。

在一个图中,每条边或弧可以拥有一个与之相关的数值,我们将它称为权。这些权可以具有一定的含义,比如,表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。

图中顶点间存在路径,两顶点存在路径则说明是连通的,如果路径最终回到起始点则称为环,当中不重复的叫简单路径。若任意两顶点都是连通的,则图就是连通图,有向则称为强连通图。图中有子图,若子图极大连通则就是连通分量,有向的则称为强连通分量。

图的邻接矩阵的存储结构定义如下:

#define MVNum 50 //最大顶点数

typedef struct{

VertexType vexs[MVNum];

Adjmatrix arcs[MVNum[MVNum];

}MGraph

下图是一个4个顶点的无向图:

无权无向图的邻接矩阵可定义为:

用c语言建立邻接矩阵(图的邻接矩阵和最短路径)(1)

用c语言建立邻接矩阵(图的邻接矩阵和最短路径)(2)

下图是一个4个顶点的有向图:

用c语言建立邻接矩阵(图的邻接矩阵和最短路径)(3)

在图的术语中,我们提到了网的概念,也就是每条边上都带有权的图叫做网。那些这些权值就需要保存下来。

设图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:

用c语言建立邻接矩阵(图的邻接矩阵和最短路径)(4)

下图是一个有向网图。

用c语言建立邻接矩阵(图的邻接矩阵和最短路径)(5)

最短路径代码:

#include <stdio.h>

#include <stdlib.h>

#define MVNum 100 //最大顶点数

#define Maxint 32767

typedef char VertexType;

typedef int Adjmatrix;

typedef enum {FALSE,TRUE} boolean; //定义布尔型

typedef struct {

VertexType vexs[MVNum]; //顶点数组,类型假定为char型

Adjmatrix arcs[MVNum][MVNum]; //邻接矩阵,假定为int型

}MGraph;

//全局数组

int D1[MVNum],P1[MVNum];

int D[MVNum][MVNum],P[MVNum][MVNum];

//声明函数原型

void CreateMGraph(MGraph *,int ,int );

void Dijkstra(MGraph,int,int );

void Floyd(MGraph ,int);

void displayNode(MGraph *,int);

//主程序

void main( )

{ MGraph G;

int n,e,v,w,k;

int xz=1;

printf("输入图中顶点个数和边数n,e:");

scanf("%d %d",&n,&e);

CreateMGraph(&G,n,e);//建立图的存储结构

displayNode(&G,n);

while (xz!=0) {

printf("******求城市之间的最短路径******\n");

printf("================================\n");

printf("1.求一个城市到所有城市的最短路径\n");

printf("2.求任意的两个城市之间的最短路径\n");

printf("================================\n");

printf(" 请选择:1 或 2,选择 0 退出 :");

scanf("%d",&xz);

if(xz==2) {

Floyd(G,n); //调用费洛伊德算法

printf(" 输入源点(或称起点)和终点:v,w :");

scanf("%d %d",&v,&w);

k=P[v][w]; //k为起点v的后继顶点

if(k==0)

printf("顶点 %d 到 %d 无路径!\n",v,w);

else

{

printf("从顶点%d到%d的最短路径是:%d",v,w,v);

while(k!=w) {

printf("→%d",k); //输出后继顶点

k=P[k][w]; //继续找下一个后继顶点

}

printf("→%d\n",w); //输出终点w

printf(" 路径长度:%d\n",D[v][w]);

}

}

else

if(xz==1) {

printf("求单源路径,输入源点 v :");

scanf("%d",&v);

Dijkstra(G,v,n); //调用迪杰斯特拉算法

}

// xz=0;

}

printf("结束求最短路径,再见!\n");

system("pause");

}

void CreateMGraph(MGraph* G,int n,int e)

{//采用邻接矩阵表示法构造有向网G, n、e表示图的当前顶点数和边数

int i,j,k,w;

for(i=1;i<=n;i )//输入顶点信息

G->vexs[i]=(char)i;

for(i=1;i<=n;i )

for(j=1;j<=n;j )

G->arcs[i][j]=Maxint;//初始化邻接矩阵

printf("输入%d条边的i、j及w:\n",e);

for(k=1;k<=e;k ){ //读入e条边,建立邻接矩阵

scanf("%d %d %d",&i,&j,&w);

G->arcs[i][j]=w;

}

printf("有向图的存储结构建立完毕!\n");

}

void displayNode(MGraph *G,int m)

{

int i,j;

printf("图的邻接矩阵为:\n");

for(i=1;i<=m;i )

{

for(j=1;j<=m;j )

printf("d",G->arcs[i][j]);

printf("\n");

}

}

//迪杰斯特拉算法

void Dijkstra(MGraph G,int v1,int n)

{ //用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径P[v]及其权D[v]

//设G是有向网的邻接矩阵,若边<i,j>不存在,则G[i][j]=Maxint

//S[v]为真当且仅当v∈S,即已求得从v1到v的最短路径

int D2[MVNum],P2[MVNum];

int v,i,w,min;

boolean S[MVNum];

for(v=1;v<=n;v ){//初始化S和D

S[v]=FALSE; //置空最短路径终点集

D2[v]=G.arcs[v1][v]; //置初始的最短路径值

if(D2[v]<Maxint)

P2[v]=v1; //v1是v的前趋(双亲)

else

P2[v]=0; //v无前趋

}//end_for

D2[v1]=0;S[v1]=TRUE; //S集初始时只有源点,源点到源点的距离为0

//开始循环,每次求得v1到某个v顶点的最短路径,并加v到S集中

for(i=2;i<n;i )

{//其余n-1个顶点

min=Maxint;

for(w=1;w<=n;w )

if(!S[w] && D2[w]<min)

{

v=w;

min=D2[w];

}//w顶点离v1顶点更近

S[v]=TRUE;

for(w=1;w<=n;w )//更新当前最短路径及距离

if(!S[w]&&(D2[v] G.arcs[v][w]<D2[w]))

{ //修改D2[w]和P2[w],w∈V-S

D2[w]=D2[v] G.arcs[v][w];

P2[w]=v;

}//End_if

}//End_for

printf("路径长度 路径\n");

for(i=1;i<=n;i )

{

printf("]",D2[i]);

printf("]",i);v=P2[i];

while(v!=0) {

printf("<-%d",v);

v=P2[v];

}

printf("\n");

}

}

//费洛伊德算法

void Floyd(MGraph G,int n)

{

int i,j,k;

for(i=1;i<=n;i ) //设置路径长度D和路径path初值

for(j=1;j<=n;j )

{

if(G.arcs[i][j]!=Maxint)

P[i][j]=j; //j是i的后继

else

P[i][j]=0;

D[i][j]=G.arcs[i][j];

}

for(k=1;k<=n;k )

{//做k次迭代,每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上

for(i=1;i<=n;i )

for(j=1;j<=n;j )

{

if(D[i][k] D[k][j]<D[i][j])

{

D[i][j]= D[i][k] D[k][j]; //修改长度

P[i][j]=P[i][k];

}

}

}

}

有如下有向图,为了操作方便,对于图的顶点都用序号来表示,顶点的字母用对应的序号来操作:a(1),b(2),c(3),d(4),e(5),f(6),g(7)。

用c语言建立邻接矩阵(图的邻接矩阵和最短路径)(6)

运行效果如下:

输入图中顶点个数和边数n,e(空格分隔):7 10

输入10条边的i、j(矩阵行列或坐标值)及w(权值,如距离、花费时间等):

1 7 9

2 1 20

2 3 10

2 4 20

3 5 5

5 4 12

5 7 15

6 5 18

6 7 10

7 3 18

有向图的存储结构建立完毕!

图的邻接矩阵为:

32767 32767 32767 32767 32767 32767 9

20 32767 10 20 32767 32767 32767

32767 32767 32767 32767 5 32767 32767

32767 32767 32767 32767 32767 32767 32767

32767 32767 32767 12 32767 32767 15

32767 32767 32767 32767 18 32767 10

32767 32767 18 32767 32767 32767 32767

******求城市之间的最短路径******

================================

1.求一个城市到所有城市的最短路径

2.求任意的两个城市之间的最短路径

================================

请选择:1 或 2,选择 0 退出 :1

求单源路径,输入源点 v :1

路径长度 路径

0 1

32767 2

27 3<-7<-1

44 4<-5<-3<-7<-1

32 5<-3<-7<-1

32767 6

9 7<-1

******求城市之间的最短路径******

================================

1.求一个城市到所有城市的最短路径

2.求任意的两个城市之间的最短路径

================================

请选择:1 或 2,选择 0 退出 :2

输入源点(或称起点)和终点:v,w :1 4

从顶点1到4的最短路径是:1→7→3→5→4

路径长度:44

******求城市之间的最短路径******

================================

1.求一个城市到所有城市的最短路径

2.求任意的两个城市之间的最短路径

================================

请选择:1 或 2,选择 0 退出 :2

输入源点(或称起点)和终点:v,w :4 7

顶点 4 到 7 无路径!

******求城市之间的最短路径******

================================

1.求一个城市到所有城市的最短路径

2.求任意的两个城市之间的最短路径

================================

请选择:1 或 2,选择 0 退出 :0

结束求最短路径,再见!

有如下有向网图:

用c语言建立邻接矩阵(图的邻接矩阵和最短路径)(7)

运行结果:

输入图中顶点个数和边数n,e(空格分隔):7 20

输入20条边的i、j(矩阵行列或坐标值)及w(权值,如距离、花费时间等):

1 2 2553

2 1 2553

1 3 695

3 1 695

1 4 704

4 1 704

2 3 511

3 2 511

2 5 812

5 2 812

3 4 349

4 3 349

3 6 1579

6 3 1579

4 7 651

7 4 651

5 6 2368

6 5 2368

6 7 1385

7 6 1385

有向图的存储结构建立完毕!

******求城市之间的最短路径******

================================

1.求一个城市到所有城市的最短路径

2.求任意的两个城市之间的最短路径

================================

请选择:1 或 2,选择 0 退出 :1

求单源路径,输入源点 v :1

路径长度 路径

0 1

1206 2<-3<-1

695 3<-1

704 4<-1

2018 5<-2<-3<-1

2274 6<-3<-1

1355 7<-4<-1

******求城市之间的最短路径******

================================

1.求一个城市到所有城市的最短路径

2.求任意的两个城市之间的最短路径

================================

请选择:1 或 2,选择 0 退出 :2

输入源点(或称起点)和终点:v,w :5 7

从顶点5到7的最短路径是:5→2→3→4→7

路径长度:2323

******求城市之间的最短路径******

================================

1.求一个城市到所有城市的最短路径

2.求任意的两个城市之间的最短路径

================================

请选择:1 或 2,选择 0 退出 :2

输入源点(或称起点)和终点:v,w :7 2

从顶点7到2的最短路径是:7→4→3→2

路径长度:1511

******求城市之间的最短路径******

================================

1.求一个城市到所有城市的最短路径

2.求任意的两个城市之间的最短路径

================================

请选择:1 或 2,选择 0 退出 :0

结束求最短路径,再见!

请按任意键继续. . .

-End-

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页