第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

great

看！虎頭虎尾

prim算法是：假設(shè)從頂點A開始， 先選距離A最近的頂點（比如F），然后把把F點放入已涉及頂點集合當(dāng)中，A-F邊放入已選邊的集合中。之后將A和F看作一個整體，再去找理這個整體最近的點和邊。

kruskal算法是：先把所有的邊找到，每一次都去找所有邊中最短的那一條。不斷的把頂點連接起來，直到所有的頂點都放入頂點集合中 并且通過邊形成同一個集合為止。

2種算法都要在選邊的過程中不斷判斷選擇的邊是否會和已有邊形成閉環(huán)，如果形成閉環(huán)就要舍棄

十字鏈表方式存儲圖的數(shù)據(jù)結(jié)構(gòu)和存儲內(nèi)容

鏈?zhǔn)酱鎯D的一些表示方法。

存儲的數(shù)據(jù)比較多

鄰接表-鏈?zhǔn)酱鎯?/p>

• 頂點的表示：頂點索引+出弧鏈表頭指針+頂點數(shù)據(jù)

• ?。夯☆^頂點索引+下一條弧指針+弧數(shù)據(jù)

• 逆鄰接表：記錄的是 入弧鏈表頭指針 和 弧尾頂點索引

• struct Node{頂點索引；該頂點弧鏈表的頭結(jié)點；頂點數(shù)據(jù)；}

• struct Arc{指向的頂點索引；指向下一條弧的指針；弧信息；}

• struct Map{頂點數(shù)組；}

頂點：??

頂點索引? ? ? ? ? ? ? ?出弧鏈表頭指針? ? ? ? ? ? ? ? ? ? ? ? ?頂點數(shù)據(jù)

? ? |? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?|

頂點索引? ? ? 第一個出弧的指針(可以是NULL)? ? ? ? ?頂點數(shù)據(jù)

弧的表示方法：

弧頭頂點索引? ? ? ? ? ? ? ? 下一條弧指針? ? ? ? ? ? ? ? ? 弧數(shù)據(jù)

????? ? ?|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |

弧頭頂點(指向的點)? ? ? ? 一個點有多個弧? ? ? ? ? ? ? 弧數(shù)據(jù)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?每個弧保存下一條弧的指針

連通圖：對于任何頂點都有通往其它頂點的邊，即任意兩個點之間都是連通的

完全圖：任意頂點與其它頂點之間都能直接連接，邊數(shù)與頂點間的數(shù)量關(guān)系：n(n-1)/2

生成樹：頂點和僅能夠連接這些頂點的邊組成的，邊數(shù)與頂點間的數(shù)量關(guān)系：n-1

main.cpp:


#include?<iostream>
#include?"CMap.h"

int?main()?{
????CMap?*pMap?=?new?CMap(6);

????Node?*pNodeA?=?new?Node('A');
????Node?*pNodeB?=?new?Node('B');
????Node?*pNodeC?=?new?Node('C');
????Node?*pNodeD?=?new?Node('D');
????Node?*pNodeE?=?new?Node('E');
????Node?*pNodeF?=?new?Node('F');


????pMap->addNode(pNodeA);
????pMap->addNode(pNodeB);
????pMap->addNode(pNodeC);
????pMap->addNode(pNodeD);
????pMap->addNode(pNodeE);
????pMap->addNode(pNodeF);


????//設(shè)置鄰接矩陣
????pMap->setValueToMatrixForUndirectedGraph(0,1,6);
????pMap->setValueToMatrixForUndirectedGraph(0,4,5);
????pMap->setValueToMatrixForUndirectedGraph(0,5,1);
????pMap->setValueToMatrixForUndirectedGraph(1,2,3);
????pMap->setValueToMatrixForUndirectedGraph(1,5,2);
????pMap->setValueToMatrixForUndirectedGraph(2,5,8);
????pMap->setValueToMatrixForUndirectedGraph(2,3,7);
????pMap->setValueToMatrixForUndirectedGraph(3,5,4);
????pMap->setValueToMatrixForUndirectedGraph(3,4,2);
????pMap->setValueToMatrixForUndirectedGraph(4,5,9);

????pMap->primTree(0);




//????pMap->printMatrix();
//
//????cout<<endl;
//
//????pMap->depthFirstTraverse(0);
//????cout<<endl;
//????//廣度遍歷之前，由于之前的點都被表示為已經(jīng)訪問過
//????pMap->resetNode();
//????pMap->breadthFirstTraverse(0);
????return?0;
}

CMap.h:


#ifndef?INC_0214_CMAP_H
#define?INC_0214_CMAP_H

#include?<vector>
#include?"Node.h"
#include?"Edge.h"
using?namespace?std;

class?CMap{
public:
????CMap(int?capacity);
????~CMap();
????bool?addNode(Node?*pNode);??//向圖中加入頂點（結(jié)點）
????void?resetNode();???????????//重置頂點
????bool?setValueToMatrixForDirectedGraph(int?row,int?col,int?val?=?1);?????//為有向圖設(shè)置鄰接矩陣
????bool?setValueToMatrixForUndirectedGraph(int?row,int?col,int?val?=?1);???//為無向圖設(shè)置鄰接矩陣

????void?printMatrix();?????????????????????????//打印鄰接矩陣

????void?depthFirstTraverse(int?nodeIndex);??????//深度優(yōu)先遍歷
????void?breadthFirstTraverse(int?nodeIndex);???//廣度優(yōu)先遍歷

????void?primTree(int?nodeIndex);//Prim生成樹

private:
????bool?getValueFromMatrix(int?row,int?col,int?&val);??//從矩陣中獲取權(quán)值
????void?breadthFirstTraverseImp(vector<int>?preVec);????//廣度優(yōu)先遍歷實現(xiàn)函數(shù)
????int?getMinEdge(vector<Edge>?edgeVec);//找最小邊函數(shù)
private:
????int?m_iCapacity;????//圖中最多可以容納的頂點數(shù)
????int?m_iNodeCount;???//已經(jīng)添加的頂點（結(jié)點）個數(shù)
????Node?*m_pNodeArray;?//用來指向一段內(nèi)存，這段內(nèi)存用來存放頂點數(shù)組
????int?*m_pMatrix;?????//用來存放鄰接矩陣

????Edge?*m_pEdge;//用于保存最小邊，需要在cpp文件中申請一段內(nèi)存
};

#endif?//INC_0214_CMAP_H

CMap.cpp:
#include?"CMap.h"
#include?"Node.h"
#include?<iostream>
#include?<vector>
using?namespace?std;

CMap::CMap(int?capacity)?{
????m_iCapacity?=?capacity;
????m_iNodeCount?=?0;
????m_pNodeArray?=?new?Node[m_iCapacity];
????m_pMatrix?=?new?int[m_iCapacity?*?m_iCapacity];
????memset(m_pMatrix,0,m_iCapacity?*?m_iCapacity?*?sizeof(int));//需要初始化將這個矩陣的各元素初始化為0；
//也可以用for循環(huán)進行初始化：但是注意m_pMatrix是一個一維數(shù)組
//????for(int?i?=?0;i?<?m_pMatrix*m_pMatrix;i++){
//????????m_pMatrix[i]?=?0;
//????}
????//存放最小邊的空間大小
????m_pEdge?=?new?Edge[m_iCapacity?-?1];

}

CMap::~CMap()?{//針對析構(gòu)函數(shù)中申請的內(nèi)存進行釋放
????delete?[]m_pNodeArray;
????delete?[]m_pMatrix;
}


bool?CMap::addNode(Node?*pNode)?{??//向圖中加入頂點（結(jié)點）
????if(pNode?==?NULL){
????????return?NULL;
????}
????m_pNodeArray[m_iNodeCount].m_cData?=?pNode->m_cData;//內(nèi)存在構(gòu)造函數(shù)時就已經(jīng)申請好了，只需要付值了
????m_iNodeCount++;
????return?true;
}

void?CMap::resetNode()?{???????????//重置頂點
????for(int?i?=?0;i?<?m_iNodeCount;i++){
????????m_pNodeArray[i].m_bIsVisited?=?false;
????}
}

bool?CMap::setValueToMatrixForDirectedGraph(int?row,int?col,int?val)?{?????//為有向圖設(shè)置鄰接矩陣,函數(shù)聲明時是int?val?=?1，但是定義時不加=1
????if(row?<?0?||?row?>=?m_iCapacity){
????????return?false;
????}
????if(col?<?0?||?col?>=?m_iCapacity){
????????return?false;
????}
????m_pMatrix[row?*?m_iCapacity?+?col]?=?val;
????return?true;
}

bool?CMap::setValueToMatrixForUndirectedGraph(int?row,int?col,int?val)?{???//為無向圖設(shè)置鄰接矩陣
????if(row?<?0?||?row?>=?m_iCapacity){
????????return?false;
????}
????if(col?<?0?||?col?>=?m_iCapacity){
????????return?false;
????}
????m_pMatrix[row?*?m_iCapacity?+?col]?=?val;
????m_pMatrix[col?*?m_iCapacity?+?row]?=?val;
????return?true;
}

void?CMap::printMatrix(){
????for(int?i?=?0;i?<?m_iCapacity;i++){
????????for(int?k?=?0;?k?<?m_iCapacity;k++){
????????????cout?<<?m_pMatrix[i*m_iCapacity+k]?<<?"?";
????????}
????????cout?<<?endl;
????}
}

bool?CMap::getValueFromMatrix(int?row,int?col,int?&val){
????if(row?<?0?||?row?>=?m_iCapacity){
????????return?false;
????}
????if(col?<?0?||?col?>=?m_iCapacity){
????????return?false;
????}
????val?=?m_pMatrix[row?*?m_iCapacity?+?col];
????return?true;
}

void?CMap::depthFirstTraverse(int?nodeIndex){//需要用深度優(yōu)先遍歷實現(xiàn)
????int?value?=?0;
????cout?<<?m_pNodeArray[nodeIndex].m_cData?<<?"?";
????m_pNodeArray[nodeIndex].m_bIsVisited?=?true;

????for(int?i?=?0;?i?<?m_iCapacity;i++){
????????getValueFromMatrix(nodeIndex,i,value);//注意引用的寫法
????????if(value?==?1){
????????????if(m_pNodeArray[i].m_bIsVisited){
????????????????continue;
????????????}?else{
????????????????depthFirstTraverse(i);
????????????}
????????}?else{
????????????continue;
????????}
????}
}

void?CMap::breadthFirstTraverse(int?nodeIndex){
????cout?<<?m_pNodeArray[nodeIndex].m_cData?<<?"?";
????m_pNodeArray[nodeIndex].m_bIsVisited?=?true;

????//需要用數(shù)組來保存被訪問過的結(jié)點的索引，這里使用vector,標(biāo)準(zhǔn)模板庫需要將頭文件加入
????vector<int>?curVec;
????curVec.push_back(nodeIndex);

????breadthFirstTraverseImp(curVec);
}


void?CMap::breadthFirstTraverseImp(vector<int>?preVec){
????int?value?=?0;//用于去鄰接矩陣取值，看是否為0
????vector<int>?curVec;//用來保存當(dāng)前這一層的所有節(jié)點

????for(int?j?=?0;j?<?(int)preVec.size();j++){
????????for(int?i?=?0;?i?<?m_iCapacity;i++){
????????????getValueFromMatrix(preVec[j],i,value);
????????????if(value?!=?0){//如果邊存在，還要看對應(yīng)頂點被訪問過沒
????????????????if(m_pNodeArray[i].m_bIsVisited){
????????????????????continue;
????????????????}?else{//如果存在且沒又被訪問過
????????????????????cout?<<?m_pNodeArray[i].m_cData<<"?";
????????????????????m_pNodeArray[i].m_bIsVisited?=?true;

????????????????????curVec.push_back(i);
????????????????}
????????????}
????????}
????}
????//還需要判斷這一層是否為空，為空則不必向下進行遍歷
????if(curVec.size()?==?0){
????????return;
????}?else{
????????breadthFirstTraverseImp(curVec);
????}
}

void?CMap::primTree(int?nodeIndex)?{//Prim生成樹
????int?value?=?0;
????int?edgeCount?=0;
????vector<int>?nodeVec;//存儲點的集合
????vector<Edge>?edgeVec;//存儲邊的集合
????//打印
????cout?<<?m_pNodeArray[nodeIndex].m_cData?<<endl;

????nodeVec.push_back(nodeIndex);
????m_pNodeArray[nodeIndex].m_bIsVisited?=?true;

????//
????while?(edgeCount?<?m_iCapacity?-?1){
????????int?temp?=?nodeVec.back();
????????//尋找與該結(jié)點連接的所有的邊
????????for(int?i?=?0;?i?<?m_iCapacity;i++){
????????????getValueFromMatrix(temp,i,value);
????????????if(value?!=?0){
????????????????if(m_pNodeArray[i].m_bIsVisited)?{//看點被訪問過沒，而不是邊
????????????????????continue;
????????????????}?else{
????????????????????//若這條邊還沒有被訪問過，放進數(shù)組
????????????????????Edge?edge(temp,i,value);//用構(gòu)造函數(shù)實例化一個邊的對象
????????????????????edgeVec.push_back(edge);
????????????????}
????????????}
????????}
????????//此時與temp連接的邊都放入了備選邊中，不會重復(fù)放入同一條邊

????????//從可選邊集合中找出最小的邊，連著這條邊的另一個頂點就放入點的集合中
????????//從可選邊集合中找出最小的邊函數(shù)：
????????int?edgeIndex?=?getMinEdge(edgeVec);
????????edgeVec[edgeIndex].m_bSelected?=?true;//把選中的邊置為true

????????//打印一下這個邊
????????cout?<<?edgeVec[edgeIndex].m_iNodeIndexA?<<?"----"?<<?edgeVec[edgeIndex].m_iNodeIndexB;
????????cout?<<?"?"?<<?edgeVec[edgeIndex].m_iWeightValue?<<?endl;

????????//再把這條邊放入最小生成樹邊的集合中
????????m_pEdge[edgeCount]?=?edgeVec[edgeIndex];
????????edgeCount++;
????????//連著這條邊的另一個頂點就放入點的集合中
????????int?nextNodeIndex?=?edgeVec[edgeIndex].m_iNodeIndexB;

????????nodeVec.push_back(nextNodeIndex);//放入點時需要將訪問置為true
????????m_pNodeArray[nextNodeIndex].m_bIsVisited?=?true;
????????//打印下一個點
????????cout<<m_pNodeArray[nextNodeIndex].m_cData?<<?endl;
????}
}

int?CMap::getMinEdge(vector<Edge>?edgeVec){
????int?minWeight?=?0;
????int?edgeIndex?=?0;
????int?i?=?0;
????for(;?i?<?edgeVec.size();i++){

????????if(!edgeVec[i].m_bSelected){//先看selected是不是為假
????????????minWeight?=?edgeVec[i].m_iWeightValue;
????????????//還需要記錄最小邊的索引
????????????edgeIndex?=?i;
????????????break;//找到第一個點之后就要跳出循環(huán)
????????}
????}

????if(minWeight?==?0){//找最小邊失敗，返回-1
????????return?-1;
????}

????for(;i?<?edgeVec.size();i++){
????????if(edgeVec[i].m_bSelected){//若為true
????????????continue;
????????}?else{
????????????if(minWeight?>?edgeVec[i].m_iWeightValue){
????????????????minWeight?=?edgeVec[i].m_iWeightValue;
????????????????edgeIndex?=?i;
????????????}
????????}
????}

????return?edgeIndex;
}

Node.h:



#ifndef?INC_0214_NODE_H
#define?INC_0214_NODE_H

class?Node{
public:
????Node(char?data?=0);
????char?m_cData;
????bool?m_bIsVisited;//訪問過了是true
};

#endif?//INC_0214_NODE_H

Node.cpp:



#include?"Node.h"

Node::Node(char?data)?{
????m_cData?=?data;
????m_bIsVisited?=?false;
}

Edge.h:

#ifndef?INC_0214_EDGE_H
#define?INC_0214_EDGE_H


class?Edge{
public:
????Edge(int?nodeIndexA?=?0,int?nodeIndexB?=?0,int?weightValue?=?0);
????int?m_iNodeIndexA;
????int?m_iNodeIndexB;
????int?m_iWeightValue;
????bool?m_bSelected;

};

#endif?//INC_0214_EDGE_H

Edge.cpp:



#include?"Edge.h"
Edge::Edge(int?nodeIndexA,int?nodeIndexB,int?weightValue){
????m_iNodeIndexA?=?nodeIndexA;
????m_iNodeIndexB?=?nodeIndexB;
????m_iWeightValue?=?weightValue;
????m_bSelected?=?false;//false為未訪問過
}

Prim算法：

選了F點后：

Kruskal算法：（最先選最小的邊，再選次笑的邊，前提是選邊后不要造成閉環(huán)）

因為選的邊沒有交集，所以點集合分為兩個集合

圖的遍歷：深度搜索（前序遍歷）和廣度搜索

深度搜索（前序遍歷）：

廣度搜索（較好理解，一層一層地搜索）

不同的搜索方式得到的生成樹不同，上述較為簡單，未涉及到權(quán)的問題。

若有權(quán)：最小生成樹

兩種算法：Prim算法 & Kruskal算法

十字鏈表：https://www.cnblogs.com/wkfvawl/p/9985083.html

十字鏈表，用結(jié)構(gòu)體來存儲：

鄰接多重表—鏈?zhǔn)酱鎯Γo向圖）

鄰接矩陣用數(shù)組進行表達，相對來說比較簡單。

鄰接表和十字鏈表都是用鏈表表達，主要用于表示有向圖。

鄰接多重表則用于表示無向圖。

領(lǐng)接矩陣：

自身不能到達自身，所以為0，以上是有向圖，無向圖的矩陣是對稱的，所以克制抵只記錄上或者下三角矩陣

數(shù)據(jù)結(jié)構(gòu)用代碼進行表示：

鄰接表（記錄出弧的鏈表的頭指針）：逆-入弧

這樣的數(shù)據(jù)結(jié)構(gòu)方式如何通過數(shù)據(jù)結(jié)構(gòu)的代碼來實現(xiàn)呢？

可以把無向圖中每一條連線當(dāng)成有向圖中的兩條連線（去、回）

有向圖中：

出度：一個頂點發(fā)出去的箭頭數(shù)量

無向圖中：

對于無向圖來說，如果滿足每一個頂點，都有通往其他頂點的連線（直接或間接）這樣的圖稱為連通圖。

在無向圖中，如果任意頂點 與其他頂點都有連線，這樣的圖稱為完全圖。