圖（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每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
