圖（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個頂點的無向圖：

無權無向圖的鄰接矩陣可定義為：

下圖是一個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("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)。

運行效果如下：

輸入圖中頂點個數和邊數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－

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部