6.4图的应用
6.4.1最小生成树
最小生成树的概念
什么是生成树？
怎么做呢？
有没有更便宜的修路方案呢？
有的话就叫做
Prim算法
换一种连法
同一个有多种最小生成树，但是时数值都是一样的
换一个顶点开始：从农场出发
机器实现：
更新
Kruskal算法
机器实现：
6.4.2最短路径
单源最短路径-DFS算法解决单源问题
只有一个源头
void BFS_MIN_Distance(Graph G,int u){ for(i=0;i<G.vexnum;++i){ d[i]=MAX; path[i]=-1; } d[u]=0; visited[u]=TRUE; Enqueue(Q,u); while(!isEmpty(Q)){ Dequeue(Q,u); for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)) if(!vosoted[w]){ d[w]=d[u]+1; path[w]=u; visited[w]=TRUE; Enqueue(Q,w); } } }
单源最短路径-Dijkstra算法
BFS算法只能解决无权图 或者权值都相同的图
机器实现以及时间复杂度
当为负权值的边的图 该算法不适用
