如題;這是一套完整的可運作的代碼;需要讀者有一定的基礎去閱讀;
語言是用C語言實作;在C++環境中編寫;在C++中可直接運作;在C語言中需要改部分頭檔案和輸出語句;
頭檔案;這要是代碼的聲明部分;
Prim算法, Kruskal算法, Dijkstra算法, Floyd算法中;隻有Floyd算法是動态規劃(Dynamic Programming);
其他的三個都是貪心算法(Greedy algorithm);如果需要對算法有更深刻的了解;就要學習動态規劃;精髓是解決問題的思想;将複雜的問題劃分為小問題求解;
# ifndef _AMGRAPH_
# define _AMGRAPH_
# include <iostream>
using namespace std;
# define MaxVertexNum 256
typedef char VertexType;
typedef int EdgeType;
typedef struct
{
VertexType vertex[MaxVertexNum];
EdgeType edge[MaxVertexNum][MaxVertexNum];
int vertexNum;
int edgeNum;
}AMGraph, * PAMGraph;
int LocateVertex(PAMGraph g, VertexType x);
PAMGraph CreateGraph(void);
void BFS(PAMGraph g, int i);
void BFSTraversal(PAMGraph g);
# define INFINITY 10000
typedef struct
{
int adjvertex;
int lowcost;
}AuxArray;
void MiniSpanTreePrim(PAMGraph g, int i);
void ShortestPathDij(PAMGraph g, int u, int * D, int * P);
void ShortestPathFloyd(PAMGraph g, int ** D, int ** P);
//void Show(int i, int j, int ** D, int ** P);
# endif
實作檔案;主要是代碼的實作;
# include "AMGraph.h"
# include "SeqQueue.h"
bool visited[MaxVertexNum] = { 0 };
int LocateVertex(PAMGraph g, VertexType x)
{
int i = 0;
while ((i < g->vertexNum) && (g->vertex[i] != x))
{
i += 1;
}
if (i >= g->vertexNum)
{
return -1;
}
else
{
return i;
}
}
PAMGraph CreateGraph(void)
{
PAMGraph g = (PAMGraph)malloc(sizeof(AMGraph));
if (NULL != g)
{
//輸入頂點數和邊數;
cout << "Please input the vertexNum and edgeNum: " << endl;
cin >> g->vertexNum >> g->edgeNum;
//輸入頂點值;
for (int i = 0; i < g->vertexNum; i++)
{
cout << "Please input the element value: " << endl;
cin >> g->vertex[i];
}
//輸入邊節點的值;
for (int i = 0; i < g->vertexNum; i++)
{
for (int j = 0; j < g->vertexNum; j++)
{
if (i == j)
{
g->edge[i][j] = 0;
}
else
{
g->edge[i][j] = INFINITY;
}
}
}
int i = 0;
int j = 0;
for (int k = 0; k < g->edgeNum; k++)
{
cout << "Please input the two index: " << endl;
cin >> i >> j;
int weight = 0;
cout << "Please input weight value: " << endl;
cin >> weight;
g->edge[i][j] = weight;
//g->edge[j][i] = weight;//如果是無向圖要加上;
}
return g;
}
else
{
cout << "Memory allocate is error! " << endl;
system("pause");
exit(0);
}
}
void BFS(PAMGraph g, int i)
{
PSeqQueue q = InitSeqQueue();
cout << g->vertex[i] << endl;
visited[i] = true;
InSeqQueue(q, i);
while (!EmptySeqQueue(q))
{
OutSeqQueue(q, &i);
for (int j = 0; j < g->vertexNum; j++)
{
if (g->edge[i][j] == 1 && !visited[j])
{
cout << g->vertex[j] << endl;
visited[j] = true;
InSeqQueue(q, j);
}
}
}
}
void BFSTraversal(PAMGraph g)
{
for (int i = 0; i < g->vertexNum; i++)
{
visited[i] = false;
}
for (int i = 0; i < g->vertexNum; i++)
{
if (!visited[i])
{
BFS(g, i);
}
}
}
void MiniSpanTreePrim(PAMGraph g, int u)
{
//定義疊代變量;
int i = 0;
int j = 0;
int k = 0;
//動态生成輔助數組;
AuxArray * array = new AuxArray[g->vertexNum];
//将輔助數組從u開始初始化;
for (i = 0; i < g->vertexNum; i++)
{
array[i].adjvertex = u;
array[i].lowcost = g->edge[u][i];
}
for (i = 0; i < g->vertexNum - 1; i++)
{
//設定象征意義的無窮大;
int v = INFINITY;
//查找最小的邊;
for (j = 0; j < g->vertexNum; j++)
{
//目前元素不是U集且小于v;
if ((array[j].lowcost != 0) && (array[j].lowcost < v))
{
v = array[j].lowcost;
k = j;
}
}
//将最小的邊置0;即進入U集;
array[k].lowcost = 0;
//更新輔助數組;
for (j = 0; j < g->vertexNum; j++)
{
if (g->edge[k][j] < array[j].lowcost)
{
array[j].adjvertex = k;
array[j].lowcost = g->edge[k][j];
}
}
}
//總權值;
int w = 0;
//統計資訊;
for (i = 0; i < g->vertexNum; i++)
{
//跳過開始的元素;
if (i != u)
{
cout << i << "->" << array[i].adjvertex << ", " << g->edge[i][array[i].adjvertex] << endl;
w += g->edge[i][array[i].adjvertex];
}
}
cout << "Total weight = " << w << endl;
}
void ShortestPathDij(PAMGraph g, int u, int * D, int * P)
{
//定義疊代變量;
int i = 0;
int j = 0;
int k = 0;
int min = 0;
//定義标志數組;
int * flag = (int *)malloc(g->vertexNum * sizeof(int));
//初始化D, P, flag數組;
for (i = 0; i < g->vertexNum; i++)
{
flag[i] = false;
D[i] = g->edge[u][i];
P[i] = -1;
if (D[i] < INFINITY)
{
P[i] = u;
}
}
flag[u] = true;
P[u] = -1;
//主for循環;
for (i = 0; i < g->vertexNum; i++)
{
//查找最短路徑;
k = -1;
min = INFINITY;
for (j = 0; j < g->vertexNum; j++)
{
if ((!flag[j]) && (D[j] < min))
{
k = j;
min = D[j];
}
}
if (k == -1)
{
break;
}
flag[k] = true;
//更新D 和 P數組;
for (j = 0; j < g->vertexNum; j++)
{
if ((!flag[j]) && (min + g->edge[k][j] < D[j]))
{
D[j] = min + g->edge[k][j];
P[j] = k;
}
}
}
}
void ShortestPathFloyd(PAMGraph g, int ** D, int ** P)
{
int i = 0;
int j = 0;
int k = 0;
for (i = 0; i < g->vertexNum; i++)
{
for (j = 0; j < g->vertexNum; j++)
{
D[i][j] = g->edge[i][j];
//這個if-else是記錄路徑的,目前我還沒有搞清楚;
if (D[i][j] < INFINITY)
{
P[i][j] = i;
}
else
{
P[i][j] = -1;
}
}
}
for (k = 0; k < g->vertexNum; k++)
{
for (i = 0; i < g->vertexNum; i++)
{
for (j = 0; j < g->vertexNum; j++)
{
if (D[i][k] + D[k][j] < D[i][j])
{
D[i][j] = D[i][k] + D[k][j];
P[i][j] = k;
}
}
}
}
return;
}
//void Show(int i, int j, int ** D, int ** P)
//{
// cout << D[i][j] << " " << j << "<-";
// while (P[i][j] != -1)
// {
// cout << P[i][j] << "<-";
// j = P[i][j];
// }
//
// return;
//}
Main函數;
# include "AMGraph.h"
int main(int argc, char ** argv)
{
AMGraph g;
g.vertexNum = 6;
g.edgeNum = 8;
for (int i = 0; i < g.vertexNum; i++)
{
for (int j = 0; j < g.vertexNum; j++)
{
if (i == j)
{
g.edge[i][j] = 0;
}
else
{
g.edge[i][j] = INFINITY;
}
}
}
g.edge[0][5] = 100;
g.edge[0][4] = 30;
g.edge[0][2] = 10;
g.edge[1][2] = 5;
g.edge[2][3] = 50;
g.edge[3][5] = 10;
g.edge[4][3] = 20;
g.edge[4][5] = 60;
//cout << "----------------------------" << endl;
//BFSTraversal(g);
//cout << "----------------------------" << endl;
//MiniSpanTreePrim(g, 3);
//int * D = new int[g.vertexNum];
//int * P = new int[g.vertexNum];
//ShortestPathDij(&g, 0, D, P);
//for (int i = 0; i < g.vertexNum; i++)
//{
// cout << D[i] << endl;
//}
//for (int i = 0; i < g.vertexNum; i++)
//{
// if (P[i] == -1)
// {
// continue;
// }
//
// cout << i << "<-";
// int j = i;
// while (P[j] != -1)
// {
// cout << P[j] << "<-";
// j = P[j];
// }
//
// cout << ", " << D[i] << endl;
//}
AMGraph gg;
gg.vertexNum = 3;
gg.edgeNum = 5;
for (int i = 0; i < gg.vertexNum; i++)
{
for (int j = 0; j < gg.vertexNum; j++)
{
//gg.edge[i][j] = INFINITY;
if (i == j)
{
gg.edge[i][j] = 0;
}
else
{
gg.edge[i][j] = INFINITY;
}
}
}
gg.edge[0][1] = 4;
gg.edge[0][2] = 11;
gg.edge[2][0] = 3;
gg.edge[1][0] = 6;
gg.edge[1][2] = 2;
int ** DD = (int **)malloc(gg.vertexNum * sizeof(int *));
for (int i = 0; i < gg.vertexNum; i++)
{
DD[i] = (int *)malloc(gg.vertexNum * sizeof(int));
}
int ** PP = new int *[gg.vertexNum];
for (int i = 0; i < gg.vertexNum; i++)
{
PP[i] = new int[gg.vertexNum];
}
ShortestPathFloyd(&gg, DD, PP);
cout << endl << "----------------------------------" << endl;
for (int i = 0; i < gg.vertexNum; i++)
{
for (int j = 0; j < gg.vertexNum; j++)
{
cout << DD[i][j] << endl;
}
}
cout << endl << "----------------------------------" << endl;
Show(0, 1, DD, PP);
cout << "--------" << endl;
Show(2, 0, DD, PP);
cout << "--------" << endl;
Show(0, 2, DD, PP);
system("pause");
return 0;
}