做行程的网站推荐,热门搜索关键词,腾讯企点有风险吗,标志设计课件在一个具有几个顶点的连通图G中#xff0c;如果存在子图G包含G中所有顶点和一部分边#xff0c;且不形成回路#xff0c;则称G为图G的生成树#xff0c;代价最小生成树则称为最小生成树。 许多应用问题都是一个求无向连通图的最小生成树问题。例如#xff1a;要… 在一个具有几个顶点的连通图G中如果存在子图G包含G中所有顶点和一部分边且不形成回路则称G为图G的生成树代价最小生成树则称为最小生成树。 许多应用问题都是一个求无向连通图的最小生成树问题。例如要在n个城市之间铺设光缆主要目标是要使这 n 个城市的任意两个之间都可以通信但铺设光缆的费用很高且各个城市之间铺设光缆的费用不同另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。 性质 最小生成树的边数必然是顶点数减一|E| |V| - 1。最小生成树不可以有循环。最小生成树不必是唯一的。Prim算法与Kruskal算法是寻找最小生成树的经典方法。 prim算法 从单一顶点开始普里姆算法按照以下步骤逐步扩大树中所含顶点的数目直到遍及连通图的所有顶点。 输入一个加权连通图其中顶点集合为V边集合为E初始化Vnew {x}其中x为集合V中的任一节点起始点Enew {}重复下列操作直到Vnew V在集合E中选取权值最小的边u, v其中u为集合Vnew中的元素而v则不是如果存在有多条满足前述条件即具有相同权值的边则可任意选取其中之一将v加入集合Vnew中将u, v加入集合Enew中输出使用集合Vnew和Enew来描述所得到的最小生成树。 为实现这个算法需要一个辅助数组closedge来记录Vnew到V-Vnew具有最小权值的边。对于每个顶点vi∈V-Vnew在辅助数组中存在一个分量closedge[i]表示vi到Vnew的最小代价边closedge包括两个域 adjvex表示这条边的顶点lowcost表示vi到adjvex的权值。当选择新的顶点到Vnew,选择新的边到Enew时要更新closedge 无向加权图 Graph #include iostream
#include vector
#include queue
#define MAXW 1000//定义最大权值
using namespace std;
templateclass T
class Graph//无向加权图
{
public:Graph();~Graph();void Create();//生成加权图void DFSTraverse(void (*fun)(T));//深度优先遍历void BFSTraverse(void (*fun)(T));//广度优先遍历int LocateVex(T vex);int GetVexnum(){return vexnum;}int GetArcnum(){return arcnum;}int** GetAdjMatrix(){return adjMatrix;}T GetVex(int i){return vexs[i];}
private:vectorT vexs;//顶点数组int** adjMatrix;//邻接矩阵int arcnum;//弧数int vexnum;//顶点数bool *visited;int FirstAdjVex(int v);//v的第一个邻接点int NextAdjVex(int v,int w);//从w开始找v的下个邻接点void DFS(int i,void (*fun)(T));
};templateclass T
GraphT::Graph()
{adjMatrixNULL;arcnum0;visitedNULL;
}templateclass T
GraphT::~Graph()
{for (int i0;ivexnum;i){delete [] adjMatrix[i];}delete adjMatrix;adjMatrix0;delete [] visited;
}templateclass T
void GraphT::Create()
{cout输入顶点数弧数以空格隔开;cinvexnum;cinarcnum;adjMatrixnew int*[vexnum];for(int i0;ivexnum;i)adjMatrix[i]new int[vexnum];for (int i0;ivexnum;i){for(int j0;jvexnum;j)adjMatrix[i][j]MAXW;//初始化邻接矩阵}visitednew bool[vexnum];cout输入顶点列以空格隔开;for (int i0;ivexnum;i){T temp;cintemp;vexs.push_back(temp);//输入顶点}cout输入一条边依附的顶点及权值A B 1:endl;for (int i0;iarcnum;i){T v1,v2;int w;cinv1;cinv2;cinw;int xLocateVex(v1);int yLocateVex(v2);adjMatrix[x][y]w;adjMatrix[y][x]w;//设置权值
}
}templateclass T
int GraphT::LocateVex(T vex)
{for(int i0;ivexnum;i){if (vexs[i]vex){return i;}}return -1;
}templateclass T
int GraphT::FirstAdjVex(int v)
{for (int i0;ivexnum;i){if(adjMatrix[v][i]!MAXW)return i;}return -1;
}templateclass T
int GraphT::NextAdjVex(int v,int w)
{for (int iw1;ivexnum;i){if(adjMatrix[v][i]!MAXW)return i;}return -1;
}templateclass T
void GraphT::DFS(int i,void (*fun)(T))//从第i个顶点深度优先遍历
{visited[i]true;fun(vexs[i]);for (int wFirstAdjVex(i);w0;wNextAdjVex(i,w)){if(!visited[w]) DFS(w,fun);}}templateclass T
void GraphT::DFSTraverse(void (*fun)(T))
{for(int i0;ivexnum;i)visited[i]false;for (int i0;ivexnum;i){if(!visited[i])DFS(i,fun);}
}templateclass T
void GraphT::BFSTraverse(void (*fun)(T))
{queueint Q;for(int i0;ivexnum;i)visited[i]false;visited[0]true;fun(vexs[0]);Q.push(0);//顶点入队while (!Q.empty()){//int vQ.back();int vQ.front();// 出队Q.pop();for(int wFirstAdjVex(v);w0;wNextAdjVex(v,w)){if(!visited[w]){visited[w]true;fun(vexs[w]);Q.push(w);//访问后顶点入队}}}
} prim算法 templateclass T
void MinSpanTree_PRIM(GraphT G,T u)
{//Prim算法生成最小生成树struct cell{T adjvex;//邻接顶点int lowcost;//最小权值};cell* closedgenew cell[G.GetVexnum()];//辅助数组int kG.LocateVex(u);for (int i0;iG.GetVexnum();i){if(i!k){closedge[i].adjvexu;closedge[i].lowcostG.GetAdjMatrix()[k][i];}}closedge[k].lowcost0;for (int i1;iG.GetVexnum();i){int wMAXW;for(int j0;jG.GetVexnum();j){if(closedge[j].lowcostwclosedge[j].lowcost0){wclosedge[j].lowcost;kj;}}//输出路径coutendl;cout找到路径closedge[k].adjvex----G.GetVex(k)权值wendl;closedge[k].lowcost0;for(int j0;jG.GetVexnum();j){//更新closedge[j]if (G.GetAdjMatrix()[k][j]closedge[j].lowcost){closedge[j].adjvexG.GetVex(k);closedge[j].lowcostG.GetAdjMatrix()[k][j];}}}} main void printfun(char ch)
{coutch ;
}
int main()
{Graphchar G;G.Create();cout深度优先遍历:;G.DFSTraverse(printfun);coutendl广度优先遍历;G.BFSTraverse(printfun);MinSpanTree_PRIM(G,G.GetVex(0));return 1;} 例子 原图 运行结果 转载于:https://www.cnblogs.com/wonderKK/archive/2012/04/12/2444571.html
