1. 克魯斯卡算法介紹 克魯斯卡爾(Kruskal)算法，是用來求加權(quán)連通圖的最小生成樹的算法。 基本思想：按照權(quán)值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構(gòu)成回路。
具體做法：首先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中，并使森林中不產(chǎn)生回路，直至森林變成一棵樹為止。 2. 克魯斯卡算法圖解
第1步：將邊加入R中。 邊的權(quán)值最小，因此將它加入到最小生成樹結(jié)果R中。 第2步：將邊加入R中。 上一步操作之后，邊的權(quán)值最小，因此將它加入到最小生成樹結(jié)果R中。 第3步：將邊加入R中。 上一步操作之后，邊的權(quán)值最小，因此將它加入到最小生成樹結(jié)果R中。 第4步：將邊加入R中。 上一步操作之后，邊的權(quán)值最小，但會(huì)和已有的邊構(gòu)成回路；因此，跳過邊。同理，跳過邊。將邊加入到最小生成樹結(jié)果R中。 第5步：將邊加入R中。 上一步操作之后，邊的權(quán)值最小，因此將它加入到最小生成樹結(jié)果R中。 第6步：將邊加入R中。 上一步操作之后，邊的權(quán)值最小，但會(huì)和已有的邊構(gòu)成回路；因此，跳過邊。同理，跳過邊。將邊加入到最小生成樹結(jié)果R中。 此時(shí)，最小生成樹構(gòu)造完成！它包括的邊依次是： 。 3. 代碼實(shí)現(xiàn)（1）根據(jù)圖鏈表頂點(diǎn)信息得到所有邊信息EData* listUDG::GetEdage(){ EData *pEdata = new EData[m_nEdgNum]; ENode *pTemp = NULL; int nEdgNum = 0; for (int i = 0; i < m_nvexnum;="" i="">) { pTemp = m_mVexs[i].pFirstEdge; while(pTemp != NULL) { if (pTemp->nVindex > i) // 可以不需要改代碼，但是為了嚴(yán)謹(jǐn)和效率 { pEdata[nEdgNum].nStart = m_mVexs[i].data; pEdata[nEdgNum].nEnd = m_mVexs[pTemp->nVindex].data; pEdata[nEdgNum].nWeight = pTemp->nWeight; nEdgNum ++; } pTemp = pTemp->pNext; } } return pEdata;} （2）對(duì)所有邊根據(jù)權(quán)重值大小進(jìn)行排序void listUDG::SortEdges(EData* edges, int elen) { int i,j; for (i=0; i) { for (j=i+1; j) { if (edges[i].nWeight > edges[j].nWeight) { // 交換'邊i'和'邊j' swap(edges[i], edges[j]); } } } } （3）判斷選取的邊是否構(gòu)成回路 若0->1->2->3->4 5->3 則a[0]=1;a[1]=2;a[2]=3;a[3]=4; a[5]=3; 因?yàn)閍[5]和a[2]的尾頂點(diǎn)都是3，則構(gòu)成回路 int listUDG::GetEnd(int *vends, int i){ while(vends[i] != 0) { i = vends[i]; } return i;} （4）Kruskal算法// kruska最小生成樹void listUDG::Kruskal(){ // 得到所有的邊 EData *pEdata = GetEdage(); // 根據(jù)邊的權(quán)重進(jìn)行排序 SortEdges(pEdata,m_nEdgNum); int vends[MAX] = {0}; // 用于保存'已有最小生成樹'中每個(gè)頂點(diǎn)在該最小樹中的終點(diǎn)。 EData rets[MAX]; // 結(jié)果數(shù)組，保存kruskal最小生成樹的邊 int nStartIndex,nEndIndex; int nIndex = 0; int m,n; for (int i = 0; i < m_nedgnum;="" i="">) { nStartIndex = GetVIndex(pEdata[i].nStart); nEndIndex = GetVIndex(pEdata[i].nEnd); m = GetEnd(vends, nStartIndex); n = GetEnd(vends, nEndIndex); if (m != n) { vends[m] = n; // 設(shè)置m在'已有的最小生成樹'中的終點(diǎn)為n rets[nIndex++] = pEdata[i]; // 保存結(jié)果 } } delete[] pEdata; int nSum = 0; for (int i = 0; i < nindex;="">) nSum += rets[i].nWeight; cout <>'Kruskal=' < nsum=""><>': '; for (int i = 0; i < nindex;="">) cout <>'(' < rets[i].nstart=""><>',' < rets[i].nend=""><>') '; cout endl; } （5）全部代碼  #include 'stdio.h'#include using namespace std;#define MAX 100#define INF (~(0x1<31))>// 最大值(即0X7FFFFFFF)class EData{public: EData(){} EData(char start, char end, int weight) : nStart(start), nEnd(end), nWeight(weight){} char nStart; char nEnd; int nWeight;};// 邊struct ENode{ int nVindex; // 該邊所指的頂點(diǎn)的位置 int nWeight; // 邊的權(quán)重 ENode *pNext; // 指向下一個(gè)邊的指針};struct VNode{ char data; // 頂點(diǎn)信息 ENode *pFirstEdge; // 指向第一條依附該頂點(diǎn)的邊};// 無向鄰接表class listUDG{public: listUDG(); listUDG(char *vexs, int vlen, EData **pEData, int elen); ~listUDG(); void PrintUDG(); // Prim最小生成樹 void Prim(int nStart); // 得到所有的邊 EData* GetEdage(); // kruska最小生成樹 void Kruskal();private: // 獲取的權(quán)值，若start和end不是連接的，則返回?zé)o窮大 int GetWeight(int start, int end); // 返回頂點(diǎn)的索引 int GetVIndex(char ch); void LinkLast(ENode *pFirstNode, ENode *pNode); void QuickSort(EData* pEdata, int nEdgNum); void SortEdges(EData* edges, int elen); int GetEnd(int *vends, int i);private: int m_nVexNum; // 頂點(diǎn)數(shù)目 int m_nEdgNum; // 邊數(shù)目 VNode m_mVexs[MAX]; VNode m_PrimVexs[MAX];};listUDG::listUDG(){}listUDG::listUDG(char *vexs, int vlen, EData **pEData, int elen){ m_nVexNum = vlen; m_nEdgNum = elen; // 初始化'鄰接表'的頂點(diǎn) for (int i = 0; i < vlen;="" i="">) { m_mVexs[i].data = vexs[i]; m_mVexs[i].pFirstEdge = NULL; } char c1,c2; int p1,p2; ENode *node1, *node2; // 初始化'鄰接表'的邊 for (int j = 0; j < elen;="" j="">) { // 讀取邊的起始頂點(diǎn)和結(jié)束頂點(diǎn) c1 = pEData[j]->nStart; c2 = pEData[j]->nEnd; p1 = GetVIndex(c1); p2 = GetVIndex(c2); node1 = new ENode(); node1->nVindex = p2; node1->nWeight = pEData[j]->nWeight; if (m_mVexs[p1].pFirstEdge == NULL) { m_mVexs[p1].pFirstEdge = node1; } else { LinkLast(m_mVexs[p1].pFirstEdge, node1); } node2 = new ENode(); node2->nVindex = p1; node2->nWeight = pEData[j]->nWeight; if (m_mVexs[p2].pFirstEdge == NULL) { m_mVexs[p2].pFirstEdge = node2; } else { LinkLast(m_mVexs[p2].pFirstEdge, node2); } }}listUDG::~listUDG(){ ENode *pENode = NULL; ENode *pTemp = NULL; for (int i = 0; i < m_nvexnum;="" i="">) { pENode = m_mVexs[i].pFirstEdge; if (pENode != NULL) { pTemp = pENode; pENode = pENode->pNext; delete pTemp; } delete pENode; }}void listUDG::PrintUDG(){ ENode *pTempNode = NULL; cout <>'鄰接無向表:' endl; for (int i = 0; i < m_nvexnum;="" i="">) { cout <>'頂點(diǎn):' <><>'-' <><>'->'; pTempNode = m_mVexs[i].pFirstEdge; while (pTempNode) { cout nVindex <>'->'; pTempNode = pTempNode->pNext; } cout endl; }}// Prim最小生成樹void listUDG::Prim(int nStart){ int i = 0; int nIndex=0; // prim最小樹的索引，即prims數(shù)組的索引 char cPrims[MAX]; // prim最小樹的結(jié)果數(shù)組 int weights[MAX]; // 頂點(diǎn)間邊的權(quán)值 cPrims[nIndex++] = m_mVexs[nStart].data; // 初始化'頂點(diǎn)的權(quán)值數(shù)組'， // 將每個(gè)頂點(diǎn)的權(quán)值初始化為'第start個(gè)頂點(diǎn)'到'該頂點(diǎn)'的權(quán)值。 for (i = 0; i < m_nvexnum;="">) { weights[i] = GetWeight(nStart, i); } for (i = 0; i < m_nvexnum;="" i="">) { if (nStart == i) { continue; } int min = INF; int nMinWeightIndex = 0; for (int k = 0; k < m_nvexnum;="" k="">) { if (weights[k]!= 0 && weights[k] min) { min = weights[k]; nMinWeightIndex = k; } } // 找到下一個(gè)最小權(quán)重值索引 cPrims[nIndex++] = m_mVexs[nMinWeightIndex].data; // 以找到的頂點(diǎn)更新其他點(diǎn)到該點(diǎn)的權(quán)重值 weights[nMinWeightIndex]=0; int nNewWeight = 0; for (int ii = 0; ii < m_nvexnum;="">) { nNewWeight = GetWeight(nMinWeightIndex, ii); // 該位置需要特別注意 if (0 != weights[ii] && weights[ii] > nNewWeight) { weights[ii] = nNewWeight; } } } // 計(jì)算最小生成樹的權(quán)重值 int nSum = 0; for (i = 1; i < nindex;="" i="">) { int min = INF; int nVexsIndex = GetVIndex(cPrims[i]); for (int kk = 0; kk < i;="" kk="">) { int nNextVexsIndex = GetVIndex(cPrims[kk]); int nWeight = GetWeight(nVexsIndex, nNextVexsIndex); if (nWeight min) { min = nWeight; } } nSum += min; } // 打印最小生成樹 cout <>'PRIM(' < m_mvexs[nstart].data="">')=' < nsum=""><>': '; for (i = 0; i < nindex;="">) cout < cprims[i]=""><>' '; cout endl; }// 得到所有的邊EData* listUDG::GetEdage(){ EData *pEdata = new EData[m_nEdgNum]; ENode *pTemp = NULL; int nEdgNum = 0; for (int i = 0; i < m_nvexnum;="" i="">) { pTemp = m_mVexs[i].pFirstEdge; while(pTemp != NULL) { if (pTemp->nVindex > i) // 可以不需要改代碼，但是為了嚴(yán)謹(jǐn)和效率 { pEdata[nEdgNum].nStart = m_mVexs[i].data; pEdata[nEdgNum].nEnd = m_mVexs[pTemp->nVindex].data; pEdata[nEdgNum].nWeight = pTemp->nWeight; nEdgNum ++; } pTemp = pTemp->pNext; } } return pEdata;}// 根據(jù)權(quán)重值對(duì)所有的邊進(jìn)行排序void listUDG::SortEdges(EData* edges, int elen) { int i,j; for (i=0; i) { for (j=i+1; j) { if (edges[i].nWeight > edges[j].nWeight) { // 交換'邊i'和'邊j' swap(edges[i], edges[j]); } } } } int listUDG::GetEnd(int *vends, int i){ while(vends[i] != 0) { i = vends[i]; } return i;}// kruska最小生成樹void listUDG::Kruskal(){ // 得到所有的邊 EData *pEdata = GetEdage(); // 根據(jù)邊的權(quán)重進(jìn)行排序 SortEdges(pEdata,m_nEdgNum); int vends[MAX] = {0}; // 用于保存'已有最小生成樹'中每個(gè)頂點(diǎn)在該最小樹中的終點(diǎn)。 EData rets[MAX]; // 結(jié)果數(shù)組，保存kruskal最小生成樹的邊 int nStartIndex,nEndIndex; int nIndex = 0; int m,n; for (int i = 0; i < m_nedgnum;="" i="">) { nStartIndex = GetVIndex(pEdata[i].nStart); nEndIndex = GetVIndex(pEdata[i].nEnd); m = GetEnd(vends, nStartIndex); n = GetEnd(vends, nEndIndex); if (m != n) { vends[m] = n; // 設(shè)置m在'已有的最小生成樹'中的終點(diǎn)為n rets[nIndex++] = pEdata[i]; // 保存結(jié)果 } } delete[] pEdata; int nSum = 0; for (int i = 0; i < nindex;="">) nSum += rets[i].nWeight; cout <>'Kruskal=' < nsum=""><>': '; for (int i = 0; i < nindex;="">) cout <>'(' < rets[i].nstart=""><>',' < rets[i].nend=""><>') '; cout endl; }// 獲取的權(quán)值，若start和end不是連接的，則返回?zé)o窮大int listUDG::GetWeight(int start, int end){ if (start == end) { return 0; } ENode *pTempNode = m_mVexs[start].pFirstEdge; while (pTempNode) { if (end == pTempNode->nVindex) { return pTempNode->nWeight; } pTempNode = pTempNode->pNext; } return INF;}// 返回頂點(diǎn)的索引int listUDG::GetVIndex(char ch){ int i = 0; for (; i < m_nvexnum;="" i="">) { if (m_mVexs[i].data == ch) { return i; } } return -1;}void listUDG::LinkLast(ENode *pFirstNode, ENode *pNode){ if (pFirstNode == NULL || pNode == NULL) { return; } ENode *pTempNode = pFirstNode; while (pTempNode->pNext != NULL) { pTempNode = pTempNode->pNext; } pTempNode->pNext = pNode;}void main(){ char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; // 邊 EData *edges[] = { // 起點(diǎn) 終點(diǎn) 權(quán) new EData('A', 'B', 12), new EData('A', 'F', 16), new EData('A', 'G', 14), new EData('B', 'C', 10), new EData('B', 'F', 7), new EData('C', 'D', 3), new EData('C', 'E', 5), new EData('C', 'F', 6), new EData('D', 'E', 4), new EData('E', 'F', 2), new EData('E', 'G', 8), new EData('F', 'G', 9) }; int vlen = sizeof(vexs)/sizeof(vexs[0]); int elen = sizeof(edges)/sizeof(edges[0]); listUDG* pG = new listUDG(vexs, vlen, edges, elen); pG->PrintUDG(); // 打印圖 pG->Prim(0); pG->Kruskal(); for (int i = 0; i < elen;="" i="">) { delete edges[i]; } return; }
注：感謝skywang12345博主提供的內(nèi)容分析，要了解更多詳細(xì)信息可參考原博http://www.cnblogs.com/skywang12345/p/3711500.html
|
