临沂网站建,做电器的集团网站,东莞城乡建设网站,2网站建设总结题目#xff1a;
题目和浙大陈越何钦铭数据结构07-图6 旅游规划是一样的#xff0c;不同的是用最小堆实现函数【FindMinDist】。
时间复杂度对比#xff1a; 浙大陈越何钦铭数据结构07-图6 旅游规划#xff1a; 创建图#xff08;CreateGraph#xff09;#xff1a;时…题目
题目和浙大陈越何钦铭数据结构07-图6 旅游规划是一样的不同的是用最小堆实现函数【FindMinDist】。
时间复杂度对比 浙大陈越何钦铭数据结构07-图6 旅游规划 创建图CreateGraph时间复杂度为O(N^2)因为需要使用两层循环初始化邻接矩阵。 插入边InsertEdge时间复杂度为O(1)因为只是将边的距离和代价插入到邻接矩阵中。 构建图BuildGraph时间复杂度为O(E)其中E为边的个数。需要进行E次的边的插入操作。 查找未被收录顶点中dist最小者FindMinDist时间复杂度为O(N)需要遍历所有未收录的顶点查找其中dist最小的顶点。 Dijkstra算法主循环时间复杂度为O(N^2)每次循环都需要找到未收录顶点中dist最小的顶点并更新其周围顶点的dist和cost值。 综上所述整个算法的时间复杂度为O(N^2)。
堆实现代码 如果将 FindMinDist 函数使用最小堆实现会使得 Dijkstra 算法的时间复杂度变为 O((N E)logN)其中 N 为顶点数E 为边数。 具体分析如下 创建图CreateGraph时间复杂度仍为 O(N^2)与之前相同。 插入边InsertEdge时间复杂度仍为 O(1)与之前相同。 构建图BuildGraph时间复杂度仍为 O(E)与之前相同。 查找未被收录顶点中dist最小者FindMinDist使用最小堆实现后每次查找最小值的时间复杂度为 O(logN)总共需要进行 N 次查找因此时间复杂度为 O(NlogN)。 Dijkstra算法主循环在每个节点更新最短路径时需要将其邻接节点的信息插入最小堆中插入一个节点的时间复杂度为 O(logN)总共需要插入 E 个节点因此时间复杂度为 O(ElogN)。同时在每个节点更新最短路径时还需要进行一次堆操作将堆中的最小值取出时间复杂度为 O(logN)总共需要进行 N 次堆操作因此时间复杂度为 O(NlogN)。 综上所述使用最小堆实现的 Dijkstra 算法的时间复杂度为 O((N E)logN)。相比于之前的 O(N^2)当图的规模较大时使用最小堆可以提高算法的效率。
代码
#include stdio.h
#include stdlib.h
#include stdbool.h#define MAX_VERTEX_NUM 500
#define MAX_DIST 501
#define MAX_COST 501
#define ERROR -1
#define MIN_DATA -1000typedef int ELEMENT_TYPE;
typedef int Vertex;struct _MinHeap
{ELEMENT_TYPE *Elements;int Size;int Capacity;
};
typedef struct _MinHeap *MinHeap;struct _Edge
{Vertex V, W;int dist, cost;
};
typedef struct _Edge *Edge;struct _MGraph
{int Nv, Ne;int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int cost[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
};
typedef struct _MGraph *MGraph; /* 以邻接矩阵存储的图的类型 */void InsertEdge(MGraph G, Edge E); // 插入边
MGraph CreateGraph(int vertexNum); // 初始化图
MGraph BuildGraph();bool isEmpty(MinHeap H);
bool isFull(MinHeap H);
void PercUp(MinHeap H, int p, int dist[]);
ELEMENT_TYPE DelMin(MinHeap H, int dist[]);
void FreeHeap(MinHeap H);
MinHeap CreateHeap(int MaxSize);
void BuildMinHeap(MinHeap H, int dist[]);Vertex FindMinDist(MinHeap H, int dist[]);
void Dijkstra(MGraph G, int dist[], int cost[], Vertex S);Vertex src, dst;
// 对于全局的int数组自动初始化为0bool数组初始化为false
int dist[MAX_VERTEX_NUM];
int cost[MAX_VERTEX_NUM];
bool collected[MAX_VERTEX_NUM];/*
07-图6 旅游规划
难度3颗星4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 203 40*/int main()
{MGraph G BuildGraph();Dijkstra(G, dist, cost, src);printf(%d %d\n, dist[dst], cost[dst]);return 0;
}MGraph CreateGraph(int vertexNum)
{MGraph G (MGraph)malloc(sizeof(struct _MGraph));G-Nv vertexNum;G-Ne 0;Vertex V, W;for (V 0; V vertexNum; V){for (W 0; W vertexNum; W){G-dist[V][W] MAX_DIST;G-cost[V][W] MAX_COST;}}return G;
}void InsertEdge(MGraph G, Edge E)
{/* 插入边V,W */G-dist[E-V][E-W] E-dist;G-cost[E-V][E-W] E-cost;/* 若是无向图则要反向也插入 */G-dist[E-W][E-V] E-dist;G-cost[E-W][E-V] E-cost;
}MGraph BuildGraph()
{MGraph G;Edge E;int Nv, Ne;scanf(%d %d %d %d, Nv, Ne, src, dst);G CreateGraph(Nv);if (Ne){G-Ne Ne;E (Edge)malloc(sizeof(struct _Edge));for (int i 0; i G-Ne; i){scanf(%d %d %d %d, E-V, E-W, E-dist, E-cost);InsertEdge(G, E);}free(E);}return G;
}Vertex FindMinDist(MinHeap H, int dist[])
{Vertex minV ERROR;// 从堆中取出最小值并维护最小堆的有效性。minV DelMin(H, dist);return minV;
}void Dijkstra(MGraph G, int dist[], int cost[], Vertex S)
{Vertex V, W;/* 初始化此处默认邻接矩阵中不存在的边用INFINITY表示 */for (V 0; V G-Nv; V){ // dist和cost分别保存的是源点到顶点V的距离和开销dist[V] G-dist[S][V];cost[V] G-cost[S][V];}/* 先将起点收入集合 */dist[S] 0;cost[S] 0;collected[S] true;// 根据dist对未收录顶点创建最小堆MinHeap H CreateHeap(MAX_VERTEX_NUM);for (V 0; V G-Nv; V){if (collected[V] false){ // H-Elements保存的是未收集顶点的编号本例依次是1,2,3H-Elements[H-Size] V;}}BuildMinHeap(H, dist);while (1){/* V 未被收录顶点中dist最小者 */V FindMinDist(H, dist);if (V ERROR) /* 若这样的V不存在 */break; /* 算法结束 */collected[V] true; /* 收录V */for (W 0; W G-Nv; W) /* 对图中的每个顶点W *//* 若W是V的邻接点并且未被收录 */if (collected[W] false G-dist[V][W] MAX_DIST){if (G-dist[V][W] 0) /* 若有负边 */return; /* 不能正确解决返回错误标记 *//* 若收录V使得dist[W]变小 */if (dist[V] G-dist[V][W] dist[W]){dist[W] dist[V] G-dist[V][W]; /* 更新dist[W] */cost[W] cost[V] G-cost[V][W];}else if (dist[V] G-dist[V][W] dist[W] cost[V] G-cost[V][W] cost[W]){cost[W] cost[V] G-cost[V][W];}}} /* while结束*/FreeHeap(H);free(G);
}bool isEmpty(MinHeap H)
{return H-Size 0;
}bool isFull(MinHeap H)
{return H-Size H-Capacity;
}ELEMENT_TYPE DelMin(MinHeap H, int dist[])
{if (!isEmpty(H)){ELEMENT_TYPE min, last;int parent, child;min H-Elements[1];last H-Elements[H-Size--];for (parent 1; 2 * parent H-Size; parent child){child 2 * parent;if ((child ! H-Size) (dist[H-Elements[child]] dist[H-Elements[child 1]])){child;}if (dist[last] dist[H-Elements[child]]){break;}else{H-Elements[parent] H-Elements[child];}}H-Elements[parent] last;return min;}else{return ERROR;}
}void PercUp(MinHeap H, int p, int dist[])
{ /*根据顶点的dist值决定顶点在堆中的存储位置。对dist[H-Elements[child]] dist[H-Elements[child 1]]的理解dist[x] dist[y],本质是比较两个顶点之间的dist值x,y是顶点序号。dist[x]的初始值通过dist[V] G-dist[S][V]获得并用dist[W] dist[V] G-dist[V][W]更新child是顶点在堆中的索引H-Elements[child]存储的是顶点序号所以dist[H-Elements[child]]是顶点的dist值。*/int parent, child;ELEMENT_TYPE X;X H-Elements[p];for (parent p; 2 * parent H-Size; parent child){child 2 * parent;if ((child ! H-Size) (dist[H-Elements[child]] dist[H-Elements[child 1]])){child;}if (dist[X] dist[H-Elements[child]]){break;}else{H-Elements[parent] H-Elements[child];}}H-Elements[parent] X;
}void FreeHeap(MinHeap H)
{if (H ! NULL){free(H-Elements);free(H);}
}MinHeap CreateHeap(int MaxSize)
{MinHeap H (MinHeap)malloc(sizeof(struct _MinHeap));H-Elements (ELEMENT_TYPE *)malloc((MaxSize 1) * sizeof(ELEMENT_TYPE));H-Elements[0] MIN_DATA;H-Size 0;H-Capacity MaxSize;return H;
}void BuildMinHeap(MinHeap H, int dist[])
{ // p表示顶点在堆中的位置int p;for (p H-Size / 2; p 0; p--){PercUp(H, p, dist);}
}小结 本题的最小堆比用循环的方式实现FindMinDist要难一些主要是要理解和修改堆的几个实现核心是构造和维护最小堆要根据dist的值来维护对应的顶点。
