-
圖的遍歷分為：深度優先遍歷（就是指前序遍歷）和廣度優先遍歷 最小生成樹算法：普利姆算法和克魯斯卡爾算法 普利姆算法：點，邊，待選邊集合 克魯斯卡爾算法：待選邊集合，已選邊集合，已涉及點集合（只有所有點都涉及，并且點之間已經被邊連接了，此算法才算是結束）查看全部
-
頂點結構體：包括頂點索引和頂點數據就行 圖的結構體：包括頂點數組（記錄頂點）和鄰接矩陣（記錄邊，并且頂點和邊的關系）就行 鄰接表與逆鄰接表：相對于弧的出入頂點說的，如果存儲的是弧出頂點的就是鄰接表，如果存儲的是弧進頂點就是逆鄰接表查看全部
-
無向圖：頂點和邊組成 有向圖：頂點和弧組成 圖的存儲結構：鄰接矩陣（數組來表達的），鄰接表（鏈表的方式表達，主要用來表達有向圖），十字鏈表（鏈表的方式表達，主要用來表達有向圖），鄰接多重表（鏈表的方式表達的，表達無向圖） 權值：是一個抽象的數據，用來表示弧或者是邊上的數據，從而為后續的算法提供算法依據查看全部
-
連通圖：對于任何一個頂點， 都有通往其他頂點的路勁（即任意兩個點之間都是連通的，無論間接還是直接） 在一個無向圖中，如果所有的頂點，與任意的其他頂點都有直接的連線，這樣的圖就是完全圖 完全圖與頂點之間的關系為：邊數=n(n-1)/2查看全部
-
bool Cmap::isInSet(int node, vector<int> nodeVec) { for (int i = 0; i < nodeVec.size(); i++) { if (node == nodeVec[i])return true; } return false; } void Cmap::combineNodeSet(vector<int> set1, vector<int> set2) { for (int i = 0; i < set2.size(); i++) { set1.push_back(set2[i]); } }查看全部
-
if (labelA == -1 && labelB == -1) { vector<int> tempNodeVec; tempNodeVec.push_back(edgeVec[miniIndex].nodeA); tempNodeVec.push_back(edgeVec[miniIndex].nodeB); nodeSets.push_back(tempNodeVec); edgeMini.push_back(edgeVec[miniIndex]); edgeCount++; } if (labelA == -1 && labelB != -1) { nodeSets[labelB].push_back(indexNodeA); edgeMini.push_back(edgeVec[miniIndex]); edgeCount++; } if (labelA != -1 && labelB == -1) { nodeSets[labelA].push_back(indexNodeB); edgeMini.push_back(edgeVec[miniIndex]); edgeCount++; } if (labelA != -1 && labelB != -1 && labelA != labelB) { combineNodeSet(nodeSets[labelA], nodeSets[labelB]); edgeMini.push_back(edgeVec[miniIndex]); edgeCount++; } if (labelA != -1 && labelB != -1 && labelA == labelB) { continue; } cout << indexNodeA << "----" << indexNodeB; cout << " " << edgeVec[miniIndex].value << endl; } }查看全部
-
while (edgeCount < campacity - 1) { int miniIndex = getMiniEdge(edgeVec); edgeVec[miniIndex].visited = true; int indexNodeA = edgeVec[miniIndex].nodeA; int indexNodeB = edgeVec[miniIndex].nodeB; int labelA = -1; int labelB = -1; for (int i = 0; i < nodeSets.size(); i++) { if (isInSet(indexNodeA, nodeSets[i])){ labelA = i; } if (isInSet(indexNodeB, nodeSets[i])){ labelB = i; } }查看全部
-
void Cmap::kruskalTree(int index) { vector<edge> edgeVec; vector<vector<int>> nodeSets; int edgeCount = 0; vector<edge> edgeMini; for (int i = 0; i < campacity; i++) { for (int j = 0; j < campacity; j++) { int tempVal; getValue(i, j, tempVal); if (tempVal != 0) { edge tempEdge(i, j, tempVal); edgeVec.push_back(tempEdge); } } }查看全部
-
void Cmap::primTree(int index) { int edgeCount = 0; int val = 0; vector<int> nodeVec; vector<edge> edgeVec; nodeVec.push_back(index); nodeArray[index].visited = true; cout << nodeArray[index].Data << endl; while (edgeCount < campacity - 1) { int temp = nodeVec.back(); for (int i = 0; i < campacity; i++) { getValue(temp, i, val); if (val != 0) { if (nodeArray[i].visited) { continue; } else { //nodeVec.push_back(i); //nodeArray[i].visited = true; edge edgeTemp(temp, i, val); edgeVec.push_back(edgeTemp); } } } int edgeIndex = getMiniEdge(edgeVec); edgeVec[edgeIndex].visited=true; cout << edgeVec[edgeIndex].nodeA << "---" << edgeVec[edgeIndex].nodeB ; cout <<" "<< edgeVec[edgeIndex].value << endl; edgeArray[edgeCount++] = edgeVec[edgeIndex]; int nextNode = edgeVec[edgeIndex].nodeB; nodeVec.push_back(nextNode); nodeArray[nextNode].visited = true; cout << nodeArray[nextNode].Data << endl; } }查看全部
-
int Cmap::getMiniEdge(vector<edge> edgeVec) { int index=0; int val = edgeVec[0].value; for (int i = 0; i < edgeVec.size(); i++) { if (!edgeVec[i].visited) { if (val > edgeVec[i].value) { index = i; val = edgeVec[i].value; } } } return index; }查看全部
-
背下來 明天默寫！查看全部
-
記住 記住查看全部
-
十字鏈表查看全部
-
連通圖，任意兩個點之間都是連通的（無論是直接還是間接）查看全部
-
樹是節點的有限集合查看全部
舉報
0/150
提交
取消