YoYoHomeZone
22-01-2010, 02:17 PM
Có ai biết viết code hoàn chỉnh (chạy hoàn chỉnh, không báo lỗi), hoặc ai đó đã từng làm bài toán này thành công thì giúp yoyo với.
Viết chương trình thuật toán Kruskal và thuật toán Prim. Tính độ phức tạp của thuật toán.
Mình chẳng hiểu đề nói chi hết á. Mình dở cái môn lập trình quá chừng. Những học kỳ cuối học toàn lập trình hông à. Chắc chết quá.
Ai tốt bụng giúp yoyo vượt qua cái môn này với. Cảm ơn nhiều nhiều
free_wind
26-01-2010, 11:23 PM
Làm xong rồi có đãi người ta cái gì không thế :leaf17: Tốn hết một buổi chiều của tớ rồi đấy :leaf17:
File chính:
/* tab:8
*
* mygraph.h - Some algorithms on graph
*
* "Copyright (c) 2010 by Son Vu."
*
* Permission to use, copy, modify, and distribute this software and its
* documentation for any purpose, without fee, and without written agreement is
* hereby granted, provided that the above copyright notice and the following
* two paragraphs appear in all copies of this software.
*
* IN NO EVENT SHALL THE AUTHOR OR THE HCM UNIVERSITY OF TECHNOLOGY BE LIABLE
* TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
* DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION,
* EVEN IF THE AUTHOR AND/OR THE HCM UNIVERSITY OF TECHNOLOGY HAS BEEN ADVISED
* OF THE POSSIBILITY OF SUCH DAMAGE.
*
* THE AUTHOR AND THE HCM UNIVERSITY OF TECHNOLOGY SPECIFICALLY DISCLAIM ANY
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
* PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND NEITHER THE AUTHOR NOR
* THE HCM UNIVERSITY OF TECHNOLOGY HAS ANY OBLIGATION TO PROVIDE MAINTENANCE,
* SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
*
* Author: Son Vu
* Version: 1.1
* Creation Date: Tue, Jan 26th, 2010
* Last Modified: Tue, Jan 26th, 2010
* History:
* 1.0: inital writing
* 1.1: fix a bug in Prim's algorithm...
*/
#include <malloc.h>
/* VERTEX_LIST: describe the vertices list of a graph
* vIndex: the index of the vertex
* vData: the data of the vertex, may be changed to a suitable structure
* vInTree: special markup tool for some alogrithm, otherwise not used
* vNext: pointer to the next vertex
*/
typedef struct V_LIST
{
int vIndex;
int vData;
int vInTree;
struct V_LIST *vNext;
} VERTEX_LIST;
/* ARC_LIST: describe the arcs list of a graph
* aWeight: the "weight" of an arc
* aInTree: special markup tool for some alogrithm, otherwise not used
* aVertex1:the vertex which the arc come from
* aVertex2:the vertex which the arc come to
* aNext: pointer to the next arc in the list
*/
typedef struct A_LIST
{
int aWeight;
int aInTree;
VERTEX_LIST *aVertex1;
VERTEX_LIST *aVertex2;
struct A_LIST *aNext;
} ARC_LIST;
/* G_LIST: describe an indirected graph in general
* Note that we may expend it to a directed one using this structure
* vCount: number of vertices in the list
* aCount: number of arcs in the list
* vFirst: first vertex in the list
* aFirst: first arc in the list
*/
typedef struct G_LIST
{
int vCount;
int aCount;
VERTEX_LIST *vFirst;
ARC_LIST *aFirst;
} GRAPH;
/* void createGraph(GRAPH *gHead)
* Usage : Use to initialized a graph
* Input :
* gHead: pointer to the graph structure
* Output: none
* Side effects: none
* Limitation: not known yet
*/
void createGraph(GRAPH *gHead)
{
gHead->vCount = 0;
gHead->aCount = 0;
gHead->vFirst = NULL;
gHead->aFirst = NULL;
}
/* int insertVertex(GRAPH *gHead, int nData, int nIndex)
* Usage : to insert a vertex to the graph
* Input :
* gHead: pointer to the graph structure
* nData: the data of the new node
* nIndex: index of the new node
* Output:
* -1 if out of free memory
* 1 if success
* Side effects: none
* Limitation: this function will not check if nIndex is used
*/
int insertVertex(GRAPH *gHead, int nData, int nIndex)
{
VERTEX_LIST *vTemp;
// allocate memory...
vTemp = (VERTEX_LIST*)malloc(sizeof(VERTEX_LIST));
if (NULL == vTemp)
return -1;
vTemp->vIndex = nIndex;
vTemp->vData = nData;
vTemp->vInTree = 0;
vTemp->vNext = NULL;
// insert to the tree...
vTemp->vNext = gHead->vFirst;
gHead->vFirst = vTemp;
gHead->vCount++;
return 1;
}
/* int deleteVertex(GRAPH *gHead, int nIndex)
* Usage : to remove a vertex from the graph
* Input :
* gHead: pointer to the graph structure
* nIndex: index of the new node we want to remove
* Output:
* -2 if the gHead doesn't have a vertex
* -1 if we can't find the vertex whose index match requirement
* 1 if success
* Side effects: none
* Limitation: not known yet
*/
int deleteVertex(GRAPH *gHead, int nIndex)
{
VERTEX_LIST *vLocat, *vPrevi;
// is empty tree?
if (0 == gHead->vCount)
return -2;
// find the vertex with right index...
vPrevi = NULL;
vLocat = gHead->vFirst;
while((NULL != vLocat) && (nIndex != vLocat->vIndex))
{
vPrevi = vLocat;
vLocat = vLocat->vNext;
}
// can we find?
if (NULL == vLocat)
return -1;
// delete it and free memory
if (NULL == vPrevi)
gHead->vFirst = vLocat->vNext;
else
vPrevi->vNext = vLocat->vNext;
gHead->vCount--;
free(vLocat);
return 1;
}
/* int insertArc(GRAPH *gHead, int nWeight, int nFromIndex, int nToIndex)
* Usage : to insert an arc to the graph
* Input :
* gHead: pointer to the graph structure
* nWeight: the weight of the new arc
* nFromIndex: the index of the vertex where the arc come from
* nToIndex: the index of the vertex where the arc come to
* Output:
* -1 if out of free memory
* -2 if we can't find the indexes which match with the requirements
* 1 if success
* Side effects: none
* Limitation: this function will not check if an arc with the same
* nFromIndex and nToIndex already existed
* work bizzarely if nFromIndex > nToIndex
*/
int insertArc(GRAPH *gHead, int nWeight, int nFromIndex, int nToIndex)
{
ARC_LIST *aNew;
VERTEX_LIST *vList;
// create a dummy pointer and allocate memory for it
aNew = (ARC_LIST*)malloc(sizeof(ARC_LIST));
if (NULL == aNew)
return -1;
aNew->aWeight = nWeight;
aNew->aInTree = 0;
aNew->aNext = NULL;
aNew->aVertex1 = NULL;
aNew->aVertex2 = NULL;
// check index...
for(vList = gHead->vFirst; NULL != vList; vList = vList->vNext)
{
if (vList->vIndex == nFromIndex)
aNew->aVertex1 = vList;
if (vList->vIndex == nToIndex)
aNew->aVertex2 = vList;
}
// can we find both index?
if ((NULL == aNew->aVertex1) || (NULL == aNew->aVertex2))
{
// blah.. no.. then we should free the memory
free(aNew);
return -2;
}
// insert it into the tree
aNew->aNext = gHead->aFirst;
gHead->aFirst = aNew;
gHead->aCount++;
return 1;
}
/* int deleteArc(GRAPH *gHead, int nFromIndex, int nToIndex)
* Usage : to remove an arc from the graph
* Input :
* gHead: pointer to the graph structure
* nFromIndex: the index of the vertex where the arc come from
* nToIndex: the index of the vertex where the arc come to
* Output:
* -2 if the gHead doesn't have any arc
* -1 if we can't find the vertex whose index match requirement
* 1 if success
* Side effects: none
* Limitation: work bizzarely if nFromIndex < nToIndex (a guess, I think)
*/
int deleteArc(GRAPH *gHead, int nFromIndex, int nToIndex)
{
ARC_LIST *aLocat, *aPrevi;
// again =.=" empty tree
if (0 == gHead->aCount)
return -2;
// find the right pointer...
aPrevi = NULL;
aLocat = gHead->aFirst;
while((NULL != aLocat) &&
(nFromIndex != aLocat->aVertex1->vIndex) &&
(nToIndex != aLocat->aVertex2->vIndex))
{
aPrevi = aLocat;
aLocat = aLocat->aNext;
}
// no match...
if (NULL == aLocat)
return -1;
// delete it and free memory...
if (NULL == aPrevi)
gHead->aFirst = aLocat->aNext;
else
aPrevi->aNext = aLocat->aNext;
gHead->aCount--;
free(aLocat);
return 1;
}
/* deleteGraph(GRAPH *gHead)
* Usage: delete and free all memory used by the graph;
* Input: gHead: pointer to the graph
* Output: none
* Side effect: none
* Limitation: not known yet
*/
void deleteGraph(GRAPH *gHead)
{
ARC_LIST *aList, *aPrev;
VERTEX_LIST *vList, *vPrev;
gHead->aCount = 0;
gHead->vCount = 0;
if (NULL == gHead->aFirst)
return;
if (NULL == gHead->vFirst)
return;
aList = gHead->aFirst; vList = gHead->vFirst;
aPrev = NULL; vPrev = NULL;
// purge the arcs list...
while(NULL != aList)
{
aPrev = aList;
aList = aList->aNext;
free(aPrev);
}
// purge the vertices list...
while(NULL != vList)
{
vPrev = vList;
vList = vList->vNext;
free(vPrev);
}
gHead->vFirst = NULL;
gHead->aFirst = NULL;
}
#include <limits.h>
/* int gPrim(GRAPH *gHead)
* Usage : find the minimum spanning tree of a graph using Prim's algorithm.
* Input :
* gHead: pointer to the graph
* Output:
* aInTree and vInTree will be set accordingly
* 0 or -2: not chosen
* 1 : chosen
* The function also return:
* -1: empty graph
* -2: not connected graph
* 1 : success
* Side effects: none
* Limitation: none
*/
int gPrim(GRAPH *gHead)
{
ARC_LIST *aPtr, *aMinWeight;
VERTEX_LIST *vPtr;
int bFinish;
int nMinWeight;
// empty graph?
if ((NULL == gHead) || (0 == gHead->aCount) || (0 == gHead->vCount))
return -1;
// wipe out aInTree and vInTree information
for (vPtr = gHead->vFirst; NULL != vPtr; vPtr = vPtr->vNext)
vPtr->vInTree = -1;
// also check for a closed graph?
for (aPtr = gHead->aFirst; NULL != aPtr; aPtr = aPtr->aNext)
{
aPtr->aInTree = 0;
aPtr->aVertex1->vInTree = 0;
aPtr->aVertex2->vInTree = 0;
}
for (vPtr = gHead->vFirst; NULL != vPtr; vPtr = vPtr->vNext)
if (-1 == vPtr->vInTree)
return -2;
// finish checking, let's get moving !!!
// pick up the first vertex...
gHead->vFirst->vInTree = 1;
nMinWeight = INT_MAX;
bFinish = 0;
while (!bFinish)
{
bFinish = 1;
nMinWeight = INT_MAX;
// find the smallest arc that has aVertex->vInTree = 1
for (aPtr = gHead->aFirst; NULL != aPtr; aPtr = aPtr->aNext)
{
if (((1 == aPtr->aVertex1->vInTree) ||
(1 == aPtr->aVertex2->vInTree)) &&
(0 == aPtr->aInTree) &&
(aPtr->aWeight < nMinWeight))
{
// remember the smallest weight...
aMinWeight = aPtr;
nMinWeight = aPtr->aWeight;
}
}
// mark up the change...
if ((1 == aMinWeight->aVertex1->vInTree) &&
(1 == aMinWeight->aVertex2->vInTree))
aMinWeight->aInTree = -2;
else
{
aMinWeight->aInTree = 1;
aMinWeight->aVertex1->vInTree = 1;
aMinWeight->aVertex2->vInTree = 1;
}
// check if all vertices has been marked...
for (vPtr = gHead->vFirst; NULL !=vPtr; vPtr = vPtr->vNext)
if (0 == vPtr->vInTree)
bFinish = 0;
}
return 1;
}
/* int gKruskal(GRAPH *gHead)
* Usage : find the minimum spanning tree of a graph using Prim's algorithm.
* Input :
* gHead: pointer to the graph
* Output:
* aInTree will be set accordingly
* -1 : unusable by the algorithm
* 0 : not chosen
* 1 : chosen
* vInTree will be set to a same index
* The function also return:
* -1: empty graph
* -2: not connected graph
* 1 : success
* Side effects: none
* Limitation: may not work correctly with negative index
*/
int gKruskal(GRAPH *gHead)
{
ARC_LIST *aPtr, *aMinWeight;
VERTEX_LIST *vPtr;
int bFinish;
int nMinWeight, nSmallIndex, nBigIndex;
// empty graph?
if ((NULL == gHead) || (0 == gHead->aCount) || (0 == gHead->vCount))
return -1;
// wipe out aInTree and vInTree information
for (vPtr = gHead->vFirst; NULL != vPtr; vPtr = vPtr->vNext)
vPtr->vInTree = -2;
// also check for a closed graph?
for (aPtr = gHead->aFirst; NULL != aPtr; aPtr = aPtr->aNext)
{
aPtr->aInTree = 0;
aPtr->aVertex1->vInTree = -1;
aPtr->aVertex2->vInTree = -1;
}
for (vPtr = gHead->vFirst; NULL != vPtr; vPtr = vPtr->vNext)
if (-2 == vPtr->vInTree)
return -2;
// finish checking, let's get moving !!!
nMinWeight = INT_MAX;
bFinish = 0;
while (!bFinish)
{
bFinish = 1;
nMinWeight = INT_MAX;
// find the smallest arc that is unprocessed (i.e aInTree = 0)...
for (aPtr = gHead->aFirst; NULL != aPtr; aPtr = aPtr->aNext)
if ((0 == aPtr->aInTree) && (aPtr->aWeight < nMinWeight))
{
aMinWeight = aPtr;
nMinWeight = aPtr->aWeight;
}
/* mark up vInTree of the two vertices contain it using some rule...
* - if both vertex has vInTree are -1, set to the smaller index
* - if one vertex has vInTree is -1, set to the other index
* - if both vertices >0 and different from each other, search the whole
* structure , replace the bigger index with the smaller index.
* - if both vertices >=0 and the same, mark the arc as unusable.
*/
if (aMinWeight->aVertex1->vInTree == aMinWeight->aVertex2->vInTree)
{
if (-1 == aMinWeight->aVertex1->vInTree)
{ // case 1
nSmallIndex = (aMinWeight->aVertex1->vIndex < aMinWeight->aVertex2->vIndex) ?
aMinWeight->aVertex1->vIndex : aMinWeight->aVertex2->vIndex;
aMinWeight->aVertex1->vInTree = nSmallIndex;
aMinWeight->aVertex2->vInTree = nSmallIndex;
aMinWeight->aInTree = 1;
}
else // case 4
aMinWeight->aInTree = -2;
}
else
{ // case 2
if (-1 == aMinWeight->aVertex1->vInTree)
aMinWeight->aVertex1->vInTree = aMinWeight->aVertex2->vInTree;
else if (-1 == aMinWeight->aVertex2->vInTree)
aMinWeight->aVertex2->vInTree = aMinWeight->aVertex1->vInTree;
else
{ // case 3
nSmallIndex = (aMinWeight->aVertex1->vInTree < aMinWeight->aVertex2->vInTree) ?
aMinWeight->aVertex1->vInTree : aMinWeight->aVertex2->vInTree;
nBigIndex = (aMinWeight->aVertex1->vInTree > aMinWeight->aVertex2->vInTree) ?
aMinWeight->aVertex1->vInTree : aMinWeight->aVertex2->vInTree;
for (vPtr = gHead->vFirst; NULL != vPtr; vPtr = vPtr->vNext)
if (vPtr->vInTree == nBigIndex)
vPtr->vInTree = nSmallIndex;
}
aMinWeight->aInTree = 1;
}
// check if all vertices has been marked...
for (vPtr = gHead->vFirst; NULL !=vPtr; vPtr = vPtr->vNext)
if (-1 == vPtr->vInTree)
bFinish = 0;
}
return 0;
}
File test:
/* tab:8
*
* mygraph.c - Some algorithms on graph. Demo
*
* "Copyright (c) 2010 by Son Vu."
*
* Permission to use, copy, modify, and distribute this software and its
* documentation for any purpose, without fee, and without written agreement is
* hereby granted, provided that the above copyright notice and the following
* two paragraphs appear in all copies of this software.
*
* IN NO EVENT SHALL THE AUTHOR OR THE HCM UNIVERSITY OF TECHNOLOGY BE LIABLE
* TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
* DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION,
* EVEN IF THE AUTHOR AND/OR THE HCM UNIVERSITY OF TECHNOLOGY HAS BEEN ADVISED
* OF THE POSSIBILITY OF SUCH DAMAGE.
*
* THE AUTHOR AND THE HCM UNIVERSITY OF TECHNOLOGY SPECIFICALLY DISCLAIM ANY
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
* PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND NEITHER THE AUTHOR NOR
* THE HCM UNIVERSITY OF TECHNOLOGY HAS ANY OBLIGATION TO PROVIDE MAINTENANCE,
* SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
*
* Author: Son Vu
* Version: 1.1
* Creation Date: Tue, Jan 26th, 2010
* Last Modified: Tue, Jan 26th, 2010
* History:
* 1.0: inital writing
* 1.1: fix outline...
*/
#include <stdio.h>
#include "mygraph.h"
void printGraph(GRAPH *gHead)
{
int ii;
VERTEX_LIST *vPtr = gHead->vFirst;
ARC_LIST *aPtr = gHead->aFirst;
if (NULL != vPtr)
{
for (ii = 0; ii < gHead->vCount; ii++)
{
printf("Vertex #%c. Status:%d\n", vPtr->vIndex, vPtr->vInTree);
vPtr = vPtr->vNext;
}
}
if (NULL != aPtr)
{
for (ii=0; ii < gHead->aCount; ii++)
{
printf("Arc connect from %c to %c. Status %d. Weight %d\n",
aPtr->aVertex1->vIndex, aPtr->aVertex2->vIndex,
aPtr->aInTree, aPtr->aWeight);
aPtr = aPtr->aNext;
}
}
}
int main()
{
GRAPH gNew;
int nDummy;
createGraph(&gNew);
nDummy = insertVertex(&gNew, 0, 'G');
nDummy = insertVertex(&gNew, 0, 'F');
nDummy = insertVertex(&gNew, 0, 'E');
nDummy = insertVertex(&gNew, 0, 'D');
nDummy = insertVertex(&gNew, 0, 'C');
nDummy = insertVertex(&gNew, 0, 'B');
nDummy = insertVertex(&gNew, 0, 'A');
nDummy = insertArc(&gNew, 7, 'A', 'B');
nDummy = insertArc(&gNew, 8, 'B', 'C');
nDummy = insertArc(&gNew, 5, 'C', 'E');
nDummy = insertArc(&gNew, 9, 'B', 'C');
nDummy = insertArc(&gNew, 7, 'B', 'E');
nDummy = insertArc(&gNew, 5, 'A', 'D');
nDummy = insertArc(&gNew, 15, 'D', 'E');
nDummy = insertArc(&gNew, 6, 'D', 'F');
nDummy = insertArc(&gNew, 8, 'E', 'F');
nDummy = insertArc(&gNew, 9, 'E', 'G');
nDummy = insertArc(&gNew, 11, 'F', 'G');
printf("Number of vertices:%d. Number of arcs %d \n",
gNew.vCount, gNew.aCount);
printGraph(&gNew);
gKruskal(&gNew);
printf("\n\nKruskal's Alogrithm:\n");
printGraph(&gNew);
gPrim(&gNew);
printf("\n\nPrim's Alogrithm:\n");
printGraph(&gNew);
deleteGraph(&gNew);
return 0;
}
Đồ thị dùng trong file test:
http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Kruskal_Algorithm_6.svg/618px-Kruskal_Algorithm_6.svg.png
Còn độ phức tạptheế nào thì chịu khó xem wiki đi nhé :)) Tớ lười rồi^^
Edit: vì độ dài bài post có hạn nên chịu khó đọc bài sau của tớ =.="
free_wind
27-01-2010, 05:52 AM
Output của bài trên
Number of vertices:7. Number of arcs 11
Vertex #A. Status:0
Vertex #B. Status:0
Vertex #C. Status:0
Vertex #D. Status:0
Vertex #E. Status:0
Vertex #F. Status:0
Vertex #G. Status:0
Arc connect from F to G. Status 0. Weight 11
Arc connect from E to G. Status 0. Weight 9
Arc connect from E to F. Status 0. Weight 8
Arc connect from D to F. Status 0. Weight 6
Arc connect from D to E. Status 0. Weight 15
Arc connect from A to D. Status 0. Weight 5
Arc connect from B to E. Status 0. Weight 7
Arc connect from B to C. Status 0. Weight 9
Arc connect from C to E. Status 0. Weight 5
Arc connect from B to C. Status 0. Weight 8
Arc connect from A to B. Status 0. Weight 7
Kruskal's Alogrithm:
Vertex #A. Status:65
Vertex #B. Status:65
Vertex #C. Status:65
Vertex #D. Status:65
Vertex #E. Status:65
Vertex #F. Status:65
Vertex #G. Status:65
Arc connect from F to G. Status 0. Weight 11
Arc connect from E to G. Status 1. Weight 9
Arc connect from E to F. Status -2. Weight 8
Arc connect from D to F. Status 1. Weight 6
Arc connect from D to E. Status 0. Weight 15
Arc connect from A to D. Status 1. Weight 5
Arc connect from B to E. Status 1. Weight 7
Arc connect from B to C. Status 0. Weight 9
Arc connect from C to E. Status 1. Weight 5
Arc connect from B to C. Status -2. Weight 8
Arc connect from A to B. Status 1. Weight 7
Prim's Alogrithm:
Vertex #A. Status:1
Vertex #B. Status:1
Vertex #C. Status:1
Vertex #D. Status:1
Vertex #E. Status:1
Vertex #F. Status:1
Vertex #G. Status:1
Arc connect from F to G. Status 0. Weight 11
Arc connect from E to G. Status 1. Weight 9
Arc connect from E to F. Status -2. Weight 8
Arc connect from D to F. Status 1. Weight 6
Arc connect from D to E. Status 0. Weight 15
Arc connect from A to D. Status 1. Weight 5
Arc connect from B to E. Status 1. Weight 7
Arc connect from B to C. Status 0. Weight 9
Arc connect from C to E. Status 1. Weight 5
Arc connect from B to C. Status -2. Weight 8
Arc connect from A to B. Status 1. Weight 7
Cậu copy phần đầu bài post của tớ vào 2 file mygraph.h và mygraph.c (chắc cậu chỉ cần chịu khó đọc mấy dòng đầu là biết copy cái nào vào cái nào rồi chứ gì =.=") rồi cho biên dịch là chạy thôi.
Còn chuyện test, phần đồ thị tớ đã để nạp sẵn trong file chương trình rồi. Bạn có thể tự xây dựng đồ thị theo cách của mình =.="
Bạn có thể sửa chương trình của mình trong mygraph.c để tìm hiểu thêm...
Đầu tiên đặt một biến
+ GRAPH gNew;
Khởi tạo nó bằng hàm createGraph
+ createGraph(&gNew)
Sau đó khởi tạo danh sách đỉnh
+ nDummy = insertVertex(&gNew, 0, 'G');
+ ...
+ nDummy = insertVertex(&gNew, 0, 'A');
Mấy dòng đó có nghĩa là ta sẽ thêm 7 đỉnh có tên từ 'A' đến 'G' vào danh sách. Đừng chú ý số 0, vì nó là mục thêm. Khi phát triển về sau có thể sẽ có người dùng nó =.="
Tiếp tục khởi tạo danh sách cạnh:
+ nDummy = insertArc(&gNew, 7, 'A', 'B');
+ ...
+ nDummy = insertArc(&gNew, 11, 'F', 'G');
Dòng này nghĩa là thêm một cạnh có trọng số là 7 nối từ A đến B... etc.
Tớ đã xây dựng 2 hàm chủ lực gPrim(&gNew) và gKruskal(&gNew) áp dụng 2 thuật toán trên mà cậu được học. Hai hàm đó nằm trong file "mygraph.h"
Tớ cũng viết sẵn hàm printGraph(&gNew) để in ra những thông số cần thiết.
Khi nhìn vào output của chương trình, những đường nào có status = 1 là đã được chọn, nếu = 0 hay -2 thì nghĩa là không được.
Lưu ý:
+ sau khi thêm đầy đủ đỉnh rồi hãy thêm cạnh
+ trước khi kết thúc chương trình thì luôn phải dùng hàm deleteGraph(&gNew) để giải phóng bộ nhớ
YoYoHomeZone
27-01-2010, 04:57 PM
Đầu tiên, mình xin cảm ơn bạn Free wind.
Thứ 2, cho mình xin cái Y! ID của bạn Free Wind. Qua đây mình có thể nhờ bạn Free Wind giúp đỡ mình, cũng như là mình học hỏi những kinh nghiệm "đỉnh cao" của bạn Free Wind trong lập trình. (từ giờ đến cuối khóa học toàn là lập trình)
Cuối cùng, mình hứa sẽ mời bạn uống coffee nhé!
Bạn free wind add nick của tớ nhé! Boyvn.Epartner Tớ cần cậu giúp cái này một chút. Tớ không hiểu cái chỗ file MyGraph.h, .c là cái gì. Tớ thề với cậu là trong đời chưa ai chỉ tớ cách làm như thế nào để nạp, xuất file dữ liệu từ C++ cả. Ông thầy đang dạy tớ cũng không bao giờ hướng dẫn làm sao để làm điều đó. Ổng cứ nói gà bắt mình làm vịt. Ôi má ơi, chịu hết nổi rồi! oa oa oa
Powered by vBulletin® Version 4.1.8 Copyright © 2012 vBulletin Solutions, Inc. All rights reserved.