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

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

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

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

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

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

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

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

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

无向图中连通且n个顶点n-1条边称为生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

对于图来说，邻接矩阵是不错的一种图存储结构，但是我们也发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式：邻接表（Adjacency List），即数组与链表相结合的存储方法。

顶点用一个一维数组存储，另外，在顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。

每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。

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

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

#define MVNum 50 //最大顶点数

typedef struct{

VertexType vexs[MVNum];

Adjmatrix arcs[MVNum[MVNum];

}MGraph

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

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

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

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

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

下图是一个有向网图。

最短路径代码：

#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("%10d",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("%5d",D2[i]);

printf("%5d",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)。

运行效果如下：

输入图中顶点个数和边数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

结束求最短路径，再见！

有如下有向网图：

运行结果：

输入图中顶点个数和边数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－