图的单源最短路径算法
生活随笔
收集整理的這篇文章主要介紹了
图的单源最短路径算法
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
第1關(guān)：求圖（鄰接矩陣存儲(chǔ)）最短路徑的狄克斯特拉算法
任務(wù)描述
本關(guān)任務(wù)：圖的存儲(chǔ)結(jié)構(gòu)為鄰接矩陣，要求編寫函數(shù)實(shí)現(xiàn)狄克斯特拉算法。
測(cè)試說明
平臺(tái)會(huì)對(duì)你編寫的代碼進(jìn)行測(cè)試：
測(cè)試輸入：
1
lt4.txt
輸入說明：
第一行輸入1，表示輸入圖的類型為有向網(wǎng)。
第二行輸入文件名，該文件里保存了圖的數(shù)據(jù)信息，內(nèi)容如下：
7
12
0
1
2
3
4
5
6
0 1 4
0 2 6
0 3 6
1 2 1
1 4 6
2 4 6
2 5 4
3 2 2
3 5 5
4 6 6
5 4 1
5 6 8
第1行為圖的頂點(diǎn)的個(gè)數(shù)n；
第2行為圖的邊的條數(shù)m；
第3行至第n+2行是n個(gè)頂點(diǎn)的數(shù)據(jù)；
第n+3行至第n+m+2行是m條邊的數(shù)據(jù)；
預(yù)期輸出：
有向網(wǎng)
7個(gè)頂點(diǎn)12條邊。頂點(diǎn)依次是: 0 1 2 3 4 5 6
圖的鄰接矩陣:
∞ 4 6 6 ∞ ∞ ∞
∞ ∞ 1 ∞ 6 ∞ ∞
∞ ∞ ∞ ∞ 6 4 ∞
∞ ∞ 2 ∞ ∞ 5 ∞
∞ ∞ ∞ ∞ ∞ ∞ 6
∞ ∞ ∞ ∞ 1 ∞ 8
∞ ∞ ∞ ∞ ∞ ∞ ∞
dist: ∞ 4 6 6 ∞ ∞ ∞
path: -1 0 0 0 -1 -1 -1
dist: ∞ 4 5 6 10 ∞ ∞
path: -1 0 1 0 1 -1 -1
dist: ∞ 4 5 6 10 9 ∞
path: -1 0 1 0 1 2 -1
dist: ∞ 4 5 6 10 9 ∞
path: -1 0 1 0 1 2 -1
dist: ∞ 4 5 6 10 9 17
path: -1 0 1 0 1 2 5
dist: ∞ 4 5 6 10 9 16
path: -1 0 1 0 1 2 4
dist: ∞ 4 5 6 10 9 16
path: -1 0 1 0 1 2 4
從0到1最短路徑長度為:4 0→1
從0到2最短路徑長度為:5 0→1→2
從0到3最短路徑長度為:6 0→3
從0到4最短路徑長度為:10 0→1→4
從0到5最短路徑長度為:9 0→1→2→5
從0到6最短路徑長度為:16 0→1→4→6
輸出說明：
第一行輸出圖的類型。
第二部分起輸出圖的頂點(diǎn)和邊的數(shù)據(jù)信息。
第三部分輸出輔助數(shù)組的變化過程。
第四部分輸出從起點(diǎn)到其余各頂點(diǎn)的最短路徑。
代碼如下
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<limits.h> #include<iostream> using namespace std; #include"MGraph.h"void Dijkstra(MGraph g,int v); //求從v到其他頂點(diǎn)的最短路徑 void DispAllPath(MGraph &g,int dist[],int path[],int S[],int v) ;//輸出從頂點(diǎn)v出發(fā)的所有最短路徑 void Dispdistpath(int dist[],int path[],int n); //輸出dist數(shù)組和path數(shù)組int main() {MGraph g;int i,j,n;CreateGraphF(g); /* 利用數(shù)據(jù)文件創(chuàng)建有向圖*/Display(g); /* 輸出有向圖*/ Dijkstra(g,0); return 0; }void Dijkstra(MGraph g,int v) { //求從v到其他頂點(diǎn)的最短路徑/********** Begin **********/int min,num,dist[MAX_VERTEX_NUM],path[MAX_VERTEX_NUM],s[MAX_VERTEX_NUM];for(int i = 0; i < g.vexnum; i++){dist[i] = g.arcs[v][i].adj;if(dist[i]!=INFINITY){path[i] = v;}else{path[i] = -1;}}for(int i = 0; i < g.vexnum; i++) s[i] = 0;s[v] = 1;num = 1;while(num<g.vexnum){int mini = INFINITY,m;for(int i = 0; i < g.vexnum; i++){if(s[i]==0&&dist[i]<mini){mini = dist[i];m = i ;}}s[m] = 1;Dispdistpath(dist,path,g.vexnum);for(int i = 0; i < g.vexnum; i++){if(s[i] == 0 && (dist[i] > dist[m] + g.arcs[m][i].adj)){dist[i] = dist[m] + g.arcs[m][i].adj;path[i] = m;}}num++;}Dispdistpath(dist,path,g.vexnum);DispAllPath(g,dist,path,s,v);/********** End **********/ }void DispAllPath(MGraph &g,int dist[],int path[],int S[],int v) //輸出從頂點(diǎn)v出發(fā)的所有最短路徑 {int i,j,k,count=0;int apath[MAX_VERTEX_NUM],d; //存放一條最短路徑(逆向)及其頂點(diǎn)個(gè)數(shù)for (i=0;i<g.vexnum;i++)if (path[i]!=-1)count++;if (count==1) //path中只有一個(gè)不為-1時(shí)表示沒有路徑{ printf("從指定的頂點(diǎn)到其他頂點(diǎn)都沒有路徑!!!\n");return;}for (i=0;i<g.vexnum;i++) //循環(huán)輸出從頂點(diǎn)v到i的路徑if (S[i]==1 && i!=v){//printf("從%s到%s最短路徑長度為:%s\t路徑:",g.vexs [v],g.vexs[i],dist[i]);cout<<"從"<<g.vexs [v]<<"到"<<g.vexs[i]<<"最短路徑長度為:"<<dist[i]<<"\t";d=0; apath[d]=i; //添加路徑上的終點(diǎn)k=path[i];if (k==-1) //沒有路徑的情況printf("無路徑\n");else //存在路徑時(shí)輸出該路徑{ while (k!=v){ d++; apath[d]=k;k=path[k];}d++; apath[d]=v; //添加路徑上的起點(diǎn)//printf("%d",apath[d]); //先輸出起點(diǎn)cout<<g.vexs [ apath[d] ];for (j=d-1;j>=0;j--) //再輸出其他頂點(diǎn)//printf("→%d",apath[j]);cout<<"→"<<g.vexs [ apath[j] ];printf("\n");}} }void Dispdistpath(int dist[],int path[],int n) //輸出dist數(shù)組和path數(shù)組 {int i;printf("dist:\t");for (i=0;i<n;i++)if (dist[i]==INFINITY)printf("%s\t","∞");elseprintf("%d\t",dist[i]);printf("\n");printf("path:\t");for (i=0;i<n;i++)printf("%d\t",path[i]);printf("\n"); }第2關(guān)：求圖（鄰接表存儲(chǔ)）最短路徑的狄克斯特拉算法
任務(wù)描述
本關(guān)任務(wù)：圖的存儲(chǔ)結(jié)構(gòu)為鄰接表，要求編寫函數(shù)實(shí)現(xiàn)狄克斯特拉算法。
測(cè)試說明
平臺(tái)會(huì)對(duì)你編寫的代碼進(jìn)行測(cè)試：
測(cè)試輸入：
1
lt4.txt
輸入說明：
第一行輸入1，表示輸入圖的類型為有向網(wǎng)。
第二行輸入文件名，該文件里保存了圖的數(shù)據(jù)信息，內(nèi)容如下：
7
12
0
1
2
3
4
5
6
0 1 4
0 2 6
0 3 6
1 2 1
1 4 6
2 4 6
2 5 4
3 2 2
3 5 5
4 6 6
5 4 1
5 6 8
第1行為圖的頂點(diǎn)的個(gè)數(shù)n；
第2行為圖的邊的條數(shù)m；
第3行至第n+2行是n個(gè)頂點(diǎn)的數(shù)據(jù)；
第n+3行至第n+m+2行是m條邊的數(shù)據(jù)；
預(yù)期輸出：
有向網(wǎng)
7個(gè)頂點(diǎn)：
0 1 2 3 4 5 6
12條弧(邊):
0→3 :6 0→2 :6 0→1 :4
1→4 :6 1→2 :1
2→5 :4 2→4 :6
3→5 :5 3→2 :2
4→6 :6
5→6 :8 5→4 :1
dist: ∞ 4 6 6 ∞ ∞ ∞
path: -1 0 0 0 -1 -1 -1
dist: ∞ 4 5 6 10 ∞ ∞
path: -1 0 1 0 1 -1 -1
dist: ∞ 4 5 6 10 9 ∞
path: -1 0 1 0 1 2 -1
dist: ∞ 4 5 6 10 9 ∞
path: -1 0 1 0 1 2 -1
dist: ∞ 4 5 6 10 9 17
path: -1 0 1 0 1 2 5
dist: ∞ 4 5 6 10 9 16
path: -1 0 1 0 1 2 4
dist: ∞ 4 5 6 10 9 16
path: -1 0 1 0 1 2 4
從0到1最短路徑長度為:4 0→1
從0到2最短路徑長度為:5 0→1→2
從0到3最短路徑長度為:6 0→3
從0到4最短路徑長度為:10 0→1→4
從0到5最短路徑長度為:9 0→1→2→5
從0到6最短路徑長度為:16 0→1→4→6
輸出說明：
第一行輸出圖的類型。
第二部分起輸出圖的頂點(diǎn)和邊的數(shù)據(jù)信息。
第三部分輸出輔助數(shù)組的變化過程。
第四部分輸出從起點(diǎn)到其余各頂點(diǎn)的最短路徑。
代碼如下
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<limits.h> #include<iostream> using namespace std;#define INFINITY 4270000 // 用整型最大值代替∞ #include"ALGraph.h"int GetWeight(ALGraph G,VertexType a,VertexType b );//獲取權(quán)值void Dijkstra(ALGraph g,int v); //求從v到其他頂點(diǎn)的最短路徑 void DispAllPath(ALGraph &g,int dist[],int path[],int S[],int v) ;//輸出從頂點(diǎn)v出發(fā)的所有最短路徑 void Dispdistpath(int dist[],int path[],int n); //輸出dist數(shù)組和path數(shù)組int main() {ALGraph g;int i,j,n;CreateGraphF(g); /* 利用數(shù)據(jù)文件創(chuàng)建有向圖*/Display(g); /* 輸出有向圖*/ Dijkstra(g,0); return 0; }void Dijkstra(ALGraph g,int v) {//求從v到其他頂點(diǎn)的最短路徑/********** Begin **********/int min,num,dist[MAX_VERTEX_NUM],path[MAX_VERTEX_NUM],s[MAX_VERTEX_NUM];for(int i = 0; i < g.vexnum; i++){dist[i] = GetWeight(g,g.vertices[v].data,g.vertices[i].data);if(dist[i]!=INFINITY){path[i] = v;}else{path[i] = -1;}}for(int i = 0; i < g.vexnum; i++) s[i] = 0;s[v] = 1;num = 1;while(num<g.vexnum){int mini = INFINITY,m;for(int i = 0; i < g.vexnum; i++){if(s[i]==0&&dist[i]<mini){mini = dist[i];m = i ;}}s[m] = 1;Dispdistpath(dist,path,g.vexnum);for(int i = 0; i < g.vexnum; i++){if(s[i] == 0 && (dist[i] > dist[m] + GetWeight(g,g.vertices[m].data,g.vertices[i].data))){dist[i] = dist[m] + GetWeight(g,g.vertices[m].data,g.vertices[i].data);path[i] = m;}}num++;}Dispdistpath(dist,path,g.vexnum);DispAllPath(g,dist,path,s,v);/********** End **********/ }void DispAllPath(ALGraph &g,int dist[],int path[],int S[],int v) //輸出從頂點(diǎn)v出發(fā)的所有最短路徑 {int i,j,k,count=0;int apath[MAX_VERTEX_NUM],d; //存放一條最短路徑(逆向)及其頂點(diǎn)個(gè)數(shù)for (i=0;i<g.vexnum;i++)if (path[i]!=-1)count++;if (count==1) //path中只有一個(gè)不為-1時(shí)表示沒有路徑{ printf("從指定的頂點(diǎn)到其他頂點(diǎn)都沒有路徑!!!\n");return;}for (i=0;i<g.vexnum;i++) //循環(huán)輸出從頂點(diǎn)v到i的路徑if (S[i]==1 && i!=v){//printf("從%s到%s最短路徑長度為:%s\t路徑:",g.vexs [v],g.vexs[i],dist[i]);cout<<"從"<<g.vertices [v].data <<"到"<<g.vertices [i].data <<"最短路徑長度為:"<<dist[i]<<"\t";d=0; apath[d]=i; //添加路徑上的終點(diǎn)k=path[i];if (k==-1) //沒有路徑的情況printf("無路徑\n");else //存在路徑時(shí)輸出該路徑{ while (k!=v){ d++; apath[d]=k;k=path[k];}d++; apath[d]=v; //添加路徑上的起點(diǎn)//printf("%d",apath[d]); //先輸出起點(diǎn)cout<<g.vertices [ apath[d] ].data ;for (j=d-1;j>=0;j--) //再輸出其他頂點(diǎn)//printf("→%d",apath[j]);cout<<"→"<<g.vertices [ apath[j] ].data ;printf("\n");}} }void Dispdistpath(int dist[],int path[],int n) //輸出dist數(shù)組和path數(shù)組 {int i;printf("dist:\t");for (i=0;i<n;i++)if (dist[i]==INFINITY)printf("%s\t","∞");elseprintf("%d\t",dist[i]);printf("\n");printf("path:\t");for (i=0;i<n;i++)printf("%d\t",path[i]);printf("\n"); }int GetWeight(ALGraph G,VertexType a,VertexType b )//獲取權(quán)值 { int pa,pb;pa=LocateVex(G,a);pb=LocateVex(G,b);ArcNode* p;p=G.vertices[pa].firstarc;if(pa == pb)return 0;while(p!=NULL){ if( p->data.adjvex == pb)return p->data.info;elsep=p->nextarc;}return INFINITY; }輔助文件
lt.txt
6 9 武漢 上海 長沙 南京 成都 廣州 武漢 長沙 9 武漢 成都 2 長沙 上海 2 長沙 南京 2 上海 南京 5 上海 廣州 4 上海 成都 3 南京 廣州 8 成都 廣州 6lt2.txt
7 9 高等數(shù)學(xué) 程序設(shè)計(jì)基礎(chǔ) C語言 離散數(shù)學(xué) 數(shù)據(jù)結(jié)構(gòu) 編譯原理 操作系統(tǒng) 高等數(shù)學(xué) C語言 高等數(shù)學(xué) 離散數(shù)學(xué) 程序設(shè)計(jì)基礎(chǔ) 數(shù)據(jù)結(jié)構(gòu) 程序設(shè)計(jì)基礎(chǔ) C語言 C語言 數(shù)據(jù)結(jié)構(gòu) 離散數(shù)學(xué) 數(shù)據(jù)結(jié)構(gòu) 離散數(shù)學(xué) 編譯原理 數(shù)據(jù)結(jié)構(gòu) 編譯原理 數(shù)據(jù)結(jié)構(gòu) 操作系統(tǒng)lt3.txt
5 8 0 1 2 3 4 0 1 1 0 2 3 0 3 4 0 4 7 1 2 2 2 3 5 2 4 8 3 4 6lt4.txt
7 12 0 1 2 3 4 5 6 0 1 4 0 2 6 0 3 6 1 2 1 1 4 6 2 4 6 2 5 4 3 2 2 3 5 5 4 6 6 5 4 1 5 6 8lt5.txt
6 11 武漢 杭州 長沙 廈門 南京 上海 武漢 長沙 35 武漢 杭州 40 武漢 廈門 70 長沙 上海 50 長沙 南京 10 長沙 廈門 25 杭州 廈門 20 杭州 長沙 30 廈門 南京 15 廈門 上海 30 南京 上海 20MGraph.h
#ifndef __MGraph_H__ #define __MGraph_H__ typedef int VRType; // 頂點(diǎn)關(guān)系類型 typedef char VertexType[20]; // 頂點(diǎn)類型 // 圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示 #define INFINITY 4270000 // 用整型最大值代替∞ #define MAX_VERTEX_NUM 20 // 最大頂點(diǎn)個(gè)數(shù) typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} typedef struct {VRType adj; // 頂點(diǎn)關(guān)系類型。對(duì)無權(quán)圖，用1(是)或0(否)表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二維數(shù)組 typedef struct // 圖的數(shù)組(鄰接矩陣)存儲(chǔ) {VertexType vexs[MAX_VERTEX_NUM]; // 頂點(diǎn)向量 AdjMatrix arcs; // 鄰接矩陣 int vexnum,arcnum; // 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) GraphKind kind; // 圖的種類標(biāo)志 }MGraph; /*鄰接矩陣的8個(gè)基本操作函數(shù)聲明*/ int LocateVex(MGraph G,VertexType u);//若圖G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回-1 VertexType* GetVex(MGraph G,int v);// 根據(jù)圖G中某個(gè)頂點(diǎn)的序號(hào)v，返回該頂點(diǎn)的值 void visit(VertexType i);// 訪問輸出頂點(diǎn)的值 int FirstAdjVex(MGraph G,VertexType v);// v是圖G中某個(gè)頂點(diǎn)，返回v的第一個(gè)鄰接頂點(diǎn)的序號(hào)。若頂點(diǎn)v在G中沒有鄰接頂點(diǎn)，則返回-1 int NextAdjVex(MGraph G,VertexType v,VertexType w);//v是圖G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)，返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào)，若w是v的最后一個(gè)鄰接頂點(diǎn)，則返回-1 void CreateGraphF(MGraph &G);//采用數(shù)組(鄰接矩陣)表示法，由文件構(gòu)造無向網(wǎng)G void DestroyGraph(MGraph &G);//銷毀圖G void Display(MGraph G);//輸出鄰接矩陣存儲(chǔ)表示的圖G #endifMGraph.cpp
#include<stdio.h> #include<stdlib.h> #include<string.h> #include"MGraph.h" /*鄰接矩陣的8個(gè)基本操作函數(shù)定義*/ int LocateVex(MGraph G,VertexType u) {//初始條件：圖G存在，u和G中頂點(diǎn)有相同特征// 操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回-1 int i;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i]) == 0) return i; // VertexType是char [16]類型return -1; }VertexType* GetVex(MGraph G,int v) { // 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)的序號(hào)。操作結(jié)果：返回v的值if( v>=G.vexnum || v<0 )exit(0);return &(G.vexs[v]); }void visit(VertexType i) {printf("%s ",i); }int FirstAdjVex(MGraph G,VertexType v) {// 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn) // 操作結(jié)果：返回v的第一個(gè)鄰接頂點(diǎn)的序號(hào)。若頂點(diǎn)在G中沒有鄰接頂點(diǎn)，則返回-1 int i,j=0,k;k=LocateVex(G,v); // k為頂點(diǎn)v在圖G中的序號(hào) if(G.kind%2) // 網(wǎng) j=INFINITY;for(i=0;i<G.vexnum;i++)if(G.arcs[k][i].adj!=j)return i;return -1; }int NextAdjVex(MGraph G,VertexType v,VertexType w) {// 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn) // 操作結(jié)果：返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào)，若w是v的最后一個(gè)鄰接頂點(diǎn)，則返回-1 int i,j=0,k1,k2;k1=LocateVex(G,v); // k1為頂點(diǎn)v在圖G中的序號(hào) k2=LocateVex(G,w); // k2為頂點(diǎn)w在圖G中的序號(hào) if(G.kind%2) // 網(wǎng) j=INFINITY;for(i=k2+1;i<G.vexnum;i++)if(G.arcs[k1][i].adj!=j)return i;return -1; }void CreateGraphF(MGraph &G) {// 采用數(shù)組(鄰接矩陣)表示法，由文件構(gòu)造無向網(wǎng)Gint i,j,k,w;char filename[13];VertexType va,vb;FILE *graphlist;//printf("請(qǐng)輸入圖的類型(有向圖:0,有向網(wǎng):1,無向圖:2,無向網(wǎng):3): ");scanf("%d",&G.kind);//printf("請(qǐng)輸入數(shù)據(jù)文件名：");scanf("%s",filename); graphlist=fopen(filename,"r"); // 以graphlist指針 打開數(shù)據(jù)文件fscanf(graphlist,"%d",&G.vexnum);fscanf(graphlist,"%d",&G.arcnum);for(i=0;i<G.vexnum;++i) // 構(gòu)造頂點(diǎn)向量fscanf(graphlist,"%s",G.vexs[i]);for(i=0;i<G.vexnum;++i) // 初始化鄰接矩陣for(j=0;j<G.vexnum;++j){if(G.kind%2) // 網(wǎng)G.arcs[i][j].adj=INFINITY; else // 圖G.arcs[i][j].adj=0; }for(k=0;k<G.arcnum;++k){if(G.kind%2) // 網(wǎng)fscanf(graphlist,"%s%s%d",va,vb,&w);else // 圖fscanf(graphlist,"%s%s",va,vb);i=LocateVex(G,va);j=LocateVex(G,vb);if(G.kind == 0) // 有向圖G.arcs[i][j].adj =1;else if(G.kind == 1)G.arcs[i][j].adj=w; // 有向網(wǎng)else if(G.kind == 2) // 無向圖G.arcs[i][j].adj = G.arcs[j][i].adj=1;elseG.arcs[i][j].adj = G.arcs[j][i].adj = w;}fclose(graphlist); // 關(guān)閉數(shù)據(jù)文件 }void DestroyGraph(MGraph &G) { // 初始條件：圖G存在。操作結(jié)果：銷毀圖G int i,j,k=0;if(G.kind%2) // 網(wǎng) k=INFINITY; // k為兩頂點(diǎn)之間無邊或弧時(shí)鄰接矩陣元素的值 G.vexnum=0; // 頂點(diǎn)數(shù)為0 G.arcnum=0; // 邊數(shù)為0 }void Display(MGraph G) { // 輸出鄰接矩陣存儲(chǔ)表示的圖G int i,j;switch(G.kind){case DG: printf("有向圖\n"); break;case DN: printf("有向網(wǎng)\n"); break;case UDG:printf("無向圖\n"); break;case UDN:printf("無向網(wǎng)\n");}printf("%d個(gè)頂點(diǎn)%d條邊。頂點(diǎn)依次是: ",G.vexnum,G.arcnum);for(i=0;i<G.vexnum;++i) // 輸出G.vexs printf("%s ",G.vexs[i]);printf("\n圖的鄰接矩陣:\n"); // 輸出G.arcs.adj for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)if(G.kind%2) {if(G.arcs[i][j].adj==INFINITY)printf("%s\t","∞");elseprintf("%d\t",G.arcs[i][j].adj);}elseprintf("%d\t",G.arcs[i][j].adj);printf("\n");} }ALGraph.h
#ifndef __ALGraph_H__ #define __ALGraph_H__typedef char VertexType[20]; // 頂點(diǎn)類型為字符串 #define MAX_VERTEX_NUM 20 typedef enum{DG,DN,UDG,UDN}GraphKind; // {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} typedef struct {int adjvex; // 該弧所指向的頂點(diǎn)的位置 int info; // 網(wǎng)的權(quán)值指針 }ElemType;typedef struct ArcNode {ElemType data; // 除指針以外的部分都屬于ElemType struct ArcNode *nextarc; // 指向下一條弧的指針 }ArcNode; // 表結(jié)點(diǎn) typedef struct {VertexType data; // 頂點(diǎn)信息 ArcNode *firstarc; // 第一個(gè)表結(jié)點(diǎn)的地址,指向第一條依附該頂點(diǎn)的弧的指針 }VNode,AdjList[MAX_VERTEX_NUM]; // 頭結(jié)點(diǎn) typedef struct {AdjList vertices;int vexnum,arcnum; // 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) GraphKind kind; // 圖的種類標(biāo)志 }ALGraph;#define LNode ArcNode // 定義單鏈表的結(jié)點(diǎn)類型是圖的表結(jié)點(diǎn)的類型 #define next nextarc // 定義單鏈表結(jié)點(diǎn)的指針域是表結(jié)點(diǎn)指向下一條弧的指針域 typedef ArcNode *LinkList; // 定義指向單鏈表結(jié)點(diǎn)的指針是指向圖的表結(jié)點(diǎn)的指針 int equal(ElemType a,ElemType b); void visit(VertexType i); int LocateVex(ALGraph G,VertexType u);//若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回-1 int FirstAdjVex(ALGraph G,VertexType v); // 返回v的第一個(gè)鄰接頂點(diǎn)的序號(hào)；否則返回-1 int NextAdjVex(ALGraph G,VertexType v,VertexType w);//v是圖G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)，返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào) void CreateGraphF(ALGraph &G);// 采用鄰接表存儲(chǔ)結(jié)構(gòu)，由文件構(gòu)造沒有相關(guān)信息圖或網(wǎng)G void Display(ALGraph G); // 輸出圖的鄰接表G #endifALGraph.cpp
#include<stdio.h> #include<string.h> #include"ALGraph.h" #include"LinkList.h" int LocateVex(ALGraph G,VertexType u) { // 初始條件：圖G存在，u和G中頂點(diǎn)有相同特征 // 操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回-1 int i;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)return i;return -1; }int FirstAdjVex(ALGraph G,VertexType v) { // 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn) // 操作結(jié)果：返回v的第一個(gè)鄰接頂點(diǎn)的序號(hào)。若頂點(diǎn)在G中沒有鄰接頂點(diǎn)，則返回-1 LinkList p;int v1;v1=LocateVex(G,v); // v1為頂點(diǎn)v在圖G中的序號(hào) p=G.vertices[v1].firstarc;if(p)return p->data.adjvex;elsereturn -1; }int NextAdjVex(ALGraph G,VertexType v,VertexType w) { // 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn) // 操作結(jié)果：返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào)。若w是v的最后一個(gè)鄰接點(diǎn)，則返回-1 LinkList p,p1; // p1在Point()中用作輔助指針ElemType e;int v1;v1=LocateVex(G,v); // v1為頂點(diǎn)v在圖G中的序號(hào) e.adjvex=LocateVex(G,w); // e.adjvex為頂點(diǎn)w在圖G中的序號(hào) p=Point(G.vertices[v1].firstarc,e,equal,p1); // p指向頂點(diǎn)v的鏈表中鄰接頂點(diǎn)為w的結(jié)點(diǎn) if(!p||!p->next) // 沒找到w或w是最后一個(gè)鄰接點(diǎn) return -1;else // p->data.adjvex==w return p->next->data.adjvex; // 返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào) }void CreateGraphF(ALGraph &G) { // 采用鄰接表 存儲(chǔ)結(jié)構(gòu)，由文件構(gòu)造沒有相關(guān)信息圖或網(wǎng)G(用一個(gè)函數(shù)構(gòu)造4種圖) int i,j,k,w; // w是權(quán)值 VertexType va,vb; // 連接邊或弧的2頂點(diǎn) ElemType e;char filename[13];FILE *graphlist;//printf("請(qǐng)輸入圖的類型(有向圖:0,有向網(wǎng):1,無向圖:2,無向網(wǎng):3): ");scanf("%d",&G.kind);//printf("請(qǐng)輸入數(shù)據(jù)文件名：");scanf("%s",filename); graphlist=fopen(filename,"r"); // 以讀的方式打開數(shù)據(jù)文件，并以graphlist表示 fscanf(graphlist,"%d",&G.vexnum);fscanf(graphlist,"%d",&G.arcnum);for(i=0;i<G.vexnum;++i) // 構(gòu)造頂點(diǎn)向量 {fscanf(graphlist,"%s",G.vertices[i].data);G.vertices[i].firstarc=NULL; // 初始化與該頂點(diǎn)有關(guān)的出弧鏈表 }for(k=0;k<G.arcnum;++k) // 構(gòu)造相關(guān)弧鏈表 {if(G.kind%2) // 網(wǎng) fscanf(graphlist,"%s%s%d",va,vb,&w);else // 圖 fscanf(graphlist,"%s%s",va,vb);i=LocateVex(G,va); // 弧尾 j=LocateVex(G,vb); // 弧頭 e.info=0; // 給待插表結(jié)點(diǎn)e賦值，圖無權(quán) e.adjvex=j; // 弧頭 if(G.kind%2) // 網(wǎng) {e.info = w;}ListInsert(G.vertices[i].firstarc,1,e); // 插在第i個(gè)元素(出弧)的表頭if(G.kind>=2) // 無向圖或網(wǎng)，產(chǎn)生第2個(gè)表結(jié)點(diǎn)，并插在第j個(gè)元素(入弧)的表頭 {e.adjvex=i; // e.info不變，不必再賦值 ListInsert(G.vertices[j].firstarc,1,e); // 插在第j個(gè)元素的表頭}}fclose(graphlist); // 關(guān)閉數(shù)據(jù)文件 } void Display(ALGraph G) { // 輸出圖的鄰接表G int i;LinkList p;switch(G.kind){case DG: printf("有向圖\n"); break;case DN: printf("有向網(wǎng)\n"); break;case UDG:printf("無向圖\n"); break;case UDN:printf("無向網(wǎng)\n");}printf("%d個(gè)頂點(diǎn)：\n",G.vexnum);for(i=0;i<G.vexnum;++i)printf("%s ",G.vertices[i].data);printf("\n%d條弧(邊):\n",G.arcnum);for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){printf("%s→%s ",G.vertices[i].data,G.vertices[p->data.adjvex].data);if(G.kind%2) // 網(wǎng) printf(":%d\t",p->data.info ); p=p->nextarc;}printf("\n");} } int equal(ElemType a,ElemType b) { if(a.adjvex==b.adjvex)return 1;elsereturn 0; }void visit(VertexType i) {printf("%s ",i); }LinkList.h
#ifndef __LinkList_H__ #define __LinkList_H__ // 函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#include"ALGraph.h" typedef LNode * LinkList; // 另一種定義LinkList的方法// 不帶頭結(jié)點(diǎn)的單鏈表的部分基本操作(9個(gè))#define DestroyList ClearList // DestroyList()和ClearList()的操作是一樣的void InitList(LinkList &L); void ClearList(LinkList &L);int ListEmpty(LinkList L);int ListLength(LinkList L);int GetElem(LinkList L,int i,ElemType &e);int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType));int ListInsert(LinkList &L,int i,ElemType e);int ListDelete(LinkList &L,int i,ElemType &e);void ListTraverse(LinkList L,void(*vi)(ElemType));LinkList Point(LinkList L,ElemType e,int(*equal)(ElemType,ElemType),LinkList &p);//查找表L中滿足條件的結(jié)點(diǎn)。如找到#endifLinkList.cpp
#include<stdio.h> #include<stdlib.h> #include"LinkList.h" // 不帶頭結(jié)點(diǎn)的單鏈表的部分基本操作(9個(gè)) void InitList(LinkList &L) { // 操作結(jié)果：構(gòu)造一個(gè)空的線性表LL=NULL; // 指針為空 }#define DestroyList ClearList // DestroyList()和ClearList()的操作是一樣的 void ClearList(LinkList &L) { // 初始條件：線性表L已存在。操作結(jié)果：將L重置為空表LinkList p;while(L) // L不空{p=L; // p指向首元結(jié)點(diǎn)L=L->next; // L指向第2個(gè)結(jié)點(diǎn)(新首元結(jié)點(diǎn))free(p); // 釋放首元結(jié)點(diǎn)} }int ListEmpty(LinkList L) { // 初始條件：單鏈表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSEif(L)return FALSE;elsereturn TRUE; }int ListLength(LinkList L) { // 初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)int i=0;LinkList p=L;while(p) // p指向結(jié)點(diǎn)(沒到表尾){p=p->next; // p指向下一個(gè)結(jié)點(diǎn)i++;}return i; }int GetElem(LinkList L,int i,ElemType &e) { // L為不帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK，否則返回ERRORint j=1;LinkList p=L;if(i<1) // i值不合法return ERROR;while(j<i&&p) // 沒到第i個(gè)元素，也沒到表尾{j++;p=p->next;}if(j==i) // 存在第i個(gè)元素{e=p->data;return OK;}elsereturn ERROR; }int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType)) { // 初始條件：線性表L已存在，compare()是數(shù)據(jù)元素判定函數(shù)(滿足為1，否則為0)// 操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。// 若這樣的數(shù)據(jù)元素不存在，則返回值為0int i=0;LinkList p=L;while(p){i++;if(compare(p->data,e)) // 找到這樣的數(shù)據(jù)元素return i;p=p->next;}return 0; }int ListInsert(LinkList &L,int i,ElemType e) { // 在不帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素eint j=1;LinkList p=L,s;if(i<1) // i值不合法return ERROR;s=(LinkList)malloc(sizeof(LNode)); // 生成新結(jié)點(diǎn)s->data=e; // 給s的data域賦值if(i==1) // 插在表頭{s->next=L;L=s; // 改變L}else{ // 插在表的其余處while(p&&j<i-1) // 尋找第i-1個(gè)結(jié)點(diǎn){p=p->next;j++;}if(!p) // i大于表長+1return ERROR;s->next=p->next;p->next=s;}return OK; }int ListDelete(LinkList &L,int i,ElemType &e){ // 在不帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素，并由e返回其值int j=1;LinkList p=L,q;if(i==1) // 刪除第1個(gè)結(jié)點(diǎn){L=p->next; // L由第2個(gè)結(jié)點(diǎn)開始e=p->data;free(p); // 刪除并釋放第1個(gè)結(jié)點(diǎn)}else{while(p->next&&j<i-1) // 尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨{p=p->next;j++;}if(!p->next||j>i-1) // 刪除位置不合理return ERROR;q=p->next; // 刪除并釋放結(jié)點(diǎn)p->next=q->next;e=q->data;free(q);}return OK; }void ListTraverse(LinkList L,void(*vi)(ElemType)){ // 初始條件：線性表L已存在。操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()LinkList p=L;while(p){vi(p->data);p=p->next;}printf("\n");} LinkList Point(LinkList L,ElemType e,int(*equal)(ElemType,ElemType),LinkList &p) { //查找表L中滿足條件的結(jié)點(diǎn)。如找到，返回指向該結(jié)點(diǎn)的指針，p指向該結(jié)點(diǎn)的前驅(qū)(若該結(jié)點(diǎn)是首元結(jié)點(diǎn)，則p=NULL)。//如表L中無滿足條件的結(jié)點(diǎn)，則返回NULL，p無定義。函數(shù)equal()的兩形參的關(guān)鍵字相等，返回OK；否則返回ERRORint i,j;i=LocateElem(L,e,equal);if(i) // 找到 {if(i==1) // 是首元結(jié)點(diǎn) {p=NULL;return L;}p=L;for(j=2;j<i;j++)p=p->next;return p->next;}return NULL; // 沒找到 }總結(jié)
以上是生活随笔為你收集整理的图的单源最短路径算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 编程与手绘的对比
- 下一篇： python输出输入法_python 怎