用Prim算法的基本思想求解吃所有的最小生成树并给出求解过程的动

[求计算机图形学中的直线绘制函数法 DDA算法中点法和]Bresenham算法的特点是： 1，不必计算直线之斜率，因此不做除法； 2，不用浮点数，只用整数； 3，只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现. Bresenham算法速度很快，并适于用硬件...+阅读

看看这个相似的吧： #include #include using namespace std; #define BUFSIZE 555 #define ULTIMATE 2000000000 struct Node{ int parent; int key; }node[BUFSIZE]; int N,M; int Graph[BUFSIZE][BUFSIZE]; void init() { fill_n(&Graph[0][0],BUFSIZE*BUFSIZE,ULTIMATE); scanf( ＂%d%d ＂,&N,&M); for(int i=1;i int s,d,v; scanf( ＂%d%d%d ＂,&s,&d,&v); Graph[s][d] = v; Graph[d][s] = v; } } bool comp(Node a,Node b) { if(a.key){ if(b.key) return a.key else return true; } return false; } void prim() { SUM = 0; for(int j=1;j node[j].parent = N; node[j].key = Graph[N][j]; } node[N].key = 0; for(int i=1;i Node *p = min_element(node+1,node+1+N,comp); int k = p - node; p->key = 0； //表示点p已经加入了生成树的集合。

for(int j=1;j if(Graph[k][j] node[j].parent = k; node[j].key = Graph[k][j]； } } } 修改删除举报引用回复加为好友发送私信在线聊天 wwq_vista 等级：发表于：2007-07-11 21:20:042楼得分：0 必须按严格按要求做啊，提出的要求全部要实现、、、、由于本人平时没有认真学习加之时间紧迫，不得以而发贴求问啊。请高手帮忙，在下先谢过。修改删除举报引用回复加为好友发送私信在线聊天 pkurao pkurao 等级：发表于：2007-07-22 10:51:553楼得分：5 好像我另外一块硬盘上有写过，还经过测试的，给我发email我如果还在就给你发过去pkurao126.om 修改删除举报引用回复加为好友发送私信在线聊天 trueytht 一碗阳春面等级：发表于：2007-08-02 20:38:414楼得分：80 我在vs2005下写了一个，经过测试完全满足你的要求. 一共两个project ：一个Graph 还有一个UnDiGraph. 其中Graph project下有3个文件Edge.h, Vertex.h, Graph.h.里面分别是边类，顶点类和图类. 而UnDiGraph project下只有一个文件夹UnDiGraph.h，里面是UnDiGraph类的定义. 其中类UnDiGraph 继承自类Graph. 我是用模板写的，由于编译器不支持类模板的分离编译，所以除了main所在的文件以外，没有.cpp文件.全放在了.h文件中实现. 另外，输入输出我都截图了，可惜发现无法发上来. 修改删除举报引用回复加为好友发送私信在线聊天 trueytht 一碗阳春面等级：发表于：2007-08-02 20:39:215楼得分：0 /*************** Graph Project *********************/ // Edge.h #ifndef EDGE_H #define EDGE_H #include using namespace std; template class Edge { public: Edge(int dest, DistType cost) { //constructor this->dest = dets; this->cost = cost; this->link = NULL; } Edge(int dest, DistType cost, Edge *link) { //constructor this->dest = dest; this->cost = cost; this->link = link; } int getDest(void) const { return dest; } DistType getCost(void) const { return cost; } Edge * getLink(void) const { return link; } void setDest(int dest) { this->dest = dest; } void setCost(DistType cost) { this->cost = cost; } void setLink(Edge *p) { this->link = p; } private: int dest; DistType cost; Edge *link; }; #endif //Vertex.h #ifndef VERTEX_H #define VERTEX_H #include ＂Edge.h ＂ template class Vertex { public: Vertex(void) { this->adj = NULL; } Vertex(NameType data) { this->data = data; this->adj = NULL; } NameType getData(void) const { return data; } Edge * getAdj(void) const { return adj; } void setData(NameType data) { this->data = data; } void setAdj(Edge *adj) { this->adj = adj; } private: NameType data; Edge *adj; }; #endif // Graph.h #ifndef GRAPH_H #define GRAPH_H #include ＂Vertex.h ＂ template class Graph { public: Graph(int maxnum, int n ,int e):maxNumVertices(maxnum), numVertices(n), numEdges(e) { // constructor NameType name; nodeTable = new Vertex [maxNumVertices]; // partly intialize, cannot initialize nodeTable within derived class for (int i = 0; i cout cin >>name; nodeTable[i].setData(name); nodeTable[i].setAdj(NULL); } } Graph(const Graph &otherGraph) { // copy constructor numVertices = otherGraph.getNumVertices(); numEdges = otherGraph.getNumEdges(); nodeTable = new Vertex [numVertices]; // partly intialize, cannot initialize nodeTable within derived class for (int i = 0; i nodeTable[i].setData(otherGraph.getVertexValue(i)); nodeTable[i].setAdj(NULL); } } Graph & operator =(const Graph &otherGraph) { // = if (this != &otherGraph) { for (int i = 0; i for (Edge *p = nodeTable[i].getAdj(); p != NULL; p = nodeTable[i].getAdj()) { nodeTable[i].setAdj(p->getLink()); delete p; } } delete []nodeTable; numVertices = 0; numEdges = 0; numVertices = otherGraph.getNumVertices(); numEdges = otherGraph.getNumEdges(); nodeTable = new Vertex [numVertices]; // partly intialize for (int i = 0; i nodeTable[i].setData(otherGraph.getVertexValue(i)); nodeTable[i].setAdj(NULL); } } return *this; } virtual ~Graph(void) { // destructor for (int i = 0; i for (Edge *p = nodeTable[i].getAdj(); p != NULL; p = nodeTable[i].getAdj()) { nodeTable[i].setAdj(p->getLink()); delete p; } } numVertices = 0; numEdges = 0; ...