-
图的遍历分为：深度优先遍历（就是指前序遍历）和广度优先遍历 最小生成树算法：普利姆算法和克鲁斯卡尔算法 普利姆算法：点，边，待选边集合 克鲁斯卡尔算法：待选边集合，已选边集合，已涉及点集合（只有所有点都涉及，并且点之间已经被边连接了，此算法才算是结束）查看全部
-
顶点结构体：包括顶点索引和顶点数据就行 图的结构体：包括顶点数组（记录顶点）和邻接矩阵（记录边，并且顶点和边的关系）就行 邻接表与逆邻接表：相对于弧的出入顶点说的，如果存储的是弧出顶点的就是邻接表，如果存储的是弧进顶点就是逆邻接表查看全部
-
无向图：顶点和边组成 有向图：顶点和弧组成 图的存储结构：邻接矩阵（数组来表达的），邻接表（链表的方式表达，主要用来表达有向图），十字链表（链表的方式表达，主要用来表达有向图），邻接多重表（链表的方式表达的，表达无向图） 权值：是一个抽象的数据，用来表示弧或者是边上的数据，从而为后续的算法提供算法依据查看全部
-
连通图：对于任何一个顶点， 都有通往其他顶点的路劲（即任意两个点之间都是连通的，无论间接还是直接） 在一个无向图中，如果所有的顶点，与任意的其他顶点都有直接的连线，这样的图就是完全图 完全图与顶点之间的关系为：边数=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
提交
取消