數據結構-圖（圖的基本實現C++）

​一、圖的概念

圖是一種比較複雜的非線性數據結構

圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。

圖區分有向圖和無向圖

1、無向圖（Undirected graphs）

如果圖中任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖。

無向圖相關概念：頂點、邊

圖1-無向圖

2、有向圖（Directed graphs）

如果圖中任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖

有向圖相關概念：頂點、弧（弧頭、弧尾 出度、入度）

圖2-有向圖

另外，有些圖的邊或弧具有與它相關的數值，這種與圖的邊或弧相關的數值叫做權（Weight），這是一個求最小生成樹的關鍵值。

二、圖的存儲

圖的存儲結構要存儲圖中的各個頂點本身的信息，以及存儲頂點與頂點之間的關係，比較複雜。圖的存儲結構有鄰接矩陣、鄰接表、十字鏈表、鄰接多重表等。

三、圖的遍歷

圖的遍歷思想是從指定一個頂點出發，開始訪問其他頂點，不能重複訪問（每個頂點只能訪問一次），直至所有點被訪問。

1.深度優先遍歷（depth_first_search）

思想：從指定的第一個點開始，沿著向下的頂點不重複的一直遍歷下去，若走到盡頭，退到上一個頂點，尋找附近有沒有頂點，有而且不重複的話，接著遍歷，否則退到上一個頂點。

2.廣度優先遍歷（breadth_first_search）

思想：從指定的第一點開始，先尋找跟它直接相連的所有頂點，然後繼續這幾個頂點再次深入，每次搜尋的都是同一級別的。

四、最小生成樹

1、普利姆（Prim）算法

思路：首先就是從圖中的一個起點a開始，把a加入U集合，然後，尋找從與a有關聯的邊中，權重最小的那條邊並且該邊的終點b在頂點集合：（V-U）中，我們也把b加入到集合U中，並且輸出邊（a，b）的信息，這樣我們的集合U就有：{a,b}，然後，我們尋找與a關聯和b關聯的邊中，權重最小的那條邊並且該邊的終點在集合：（V-U）中，我們把c加入到集合U中，並且輸出對應的那條邊的信息，這樣我們的集合U就有：{a,b,c}這三個元素了，一次類推，直到所有頂點都加入到了集合U

2、克魯斯卡爾(Kruskal)算法

思路：1.將圖中的所有邊都去掉；2.將邊按權值從小到大的順序添加到圖中，保證添加的過程中不會形成環；3.重複上一步直到連接所有頂點，此時就生成了最小生成樹。這是一種貪心策略。

終於到了最興奮的代碼時候，代碼說明一切！奧利給！

樹的鄰接矩陣表示法C++基本實現：

<code>#ifndef _CMAP_H_
#define _CMAP_H_ 



#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

//頂點
class Node
{
public:
\tNode(char data = 0)
\t{
\t\tm_cData = data;
\t\tm_bVisited = false;
\t}
\tNode(const Node& node)
\t{
\t\tif (this == &node)
\t\t\treturn;
\t\t*this = node;
\t}


\tNode& operator=(const Node& node)
\t{
\t\tif (this == &node)
\t\t\treturn *this;
\t\tthis->m_cData = node.m_cData;
\t\tthis->m_bVisited = node.m_bVisited;
\t\treturn *this;
\t}
public:
\tchar m_cData; //數據
\tbool m_bVisited; //是否訪問
};

//邊
class Edge
{
public:
\tEdge(int nodeIndexA = 0, int nodeIndexB = 0, int weightValue = 0) :
\t\tm_iNodeIndexA(nodeIndexA),
\t\tm_iNodeIndexB(nodeIndexB),
\t\tm_iWeightValue(weightValue),
\t\tm_bSelected(false) {}
\tEdge(const Edge& edge)
\t{
\t\tif (this == &edge)
\t\t\treturn; 

\t\t*this = edge;
\t}

\tEdge& operator=(const Edge& edge)
\t{
\t\tif (this == &edge)
\t\t\treturn *this;
\t\tthis->m_iNodeIndexA = edge.m_iNodeIndexA;
\t\tthis->m_iNodeIndexB = edge.m_iNodeIndexB;
\t\tthis->m_iWeightValue = edge.m_iWeightValue;
\t\tthis->m_bSelected = edge.m_bSelected;
\t\treturn *this;
\t}

public:
\tint m_iNodeIndexA; //頭頂點
\tint m_iNodeIndexB; //尾頂點
\tint m_iWeightValue; //權重
\tbool m_bSelected; //是否被選中
};


\t//圖
class CMap
{

private:
\tint m_iCapacity; //頂點總數
\tint m_iNodeCount; //當前頂點數量
\tNode *m_pNodeArray; //頂點集合
\tint *m_pMatrix; //鄰接距陣
\tEdge *m_pEdgeArray; //最小生成樹邊集合
public:
\tCMap(int iCapacity)
\t{
\t\tm_iCapacity = iCapacity;
\t\tm_iNodeCount = 0;
\t\tm_pNodeArray = new Node[m_iCapacity];
\t\tm_pMatrix = new int[m_iCapacity*m_iCapacity];
\t\tmemset(m_pMatrix, 0, m_iCapacity*m_iCapacity * sizeof(int));
\t\tm_pEdgeArray = new Edge[m_iCapacity - 1];
\t}
\t~CMap(void)
\t{
\t\tdelete[]m_pNodeArray;
\t\tdelete[]m_pMatrix; 

\t\tdelete[]m_pEdgeArray;
\t}

private:
\t//廣度遍歷具體實現
\tvoid breadthFirstTraverseImpl(vector preVec)
\t{
\t\tint val = 0;
\t\tvector curVec;
\t\tfor (int i = 0; i < (int)preVec.size(); i++)
\t\t{
\t\t\tfor (int j = 0; j < m_iCapacity; j++)
\t\t\t{
\t\t\t\tgetValueFromMatrix(preVec[i], j, val);
\t\t\t\tif (/*1 == val*/0 != val)
\t\t\t\t{
\t\t\t\t\tif (m_pNodeArray[j].m_bVisited)
\t\t\t\t\t\tcontinue;
\t\t\t\t\tcout << m_pNodeArray[j].m_cData << " ";
\t\t\t\t\tm_pNodeArray[j].m_bVisited = true;
\t\t\t\t\tcurVec.push_back(j);
\t\t\t\t}
\t\t\t\telse
\t\t\t\t\tcontinue;
\t\t\t}
\t\t}

\t\tif (curVec.empty())
\t\t\treturn;
\t\telse
\t\t\tbreadthFirstTraverseImpl(curVec);
\t}

\t//取最小邊
\tint getMinEdge(const vector<edge>& edgeVec)
\t{
\t\tint min = 0, minEdge = 0;

\t\tfor (int i = 0; i < (int)edgeVec.size(); i++)
\t\t{
\t\t\tif (edgeVec[i].m_bSelected)
\t\t\t\tcontinue;
\t\t\tmin = edgeVec[i].m_iWeightValue;
\t\t\tminEdge = i;
\t\t}

\t\tfor (int i = 0; i < (int)edgeVec.size(); i++) 

\t\t{
\t\t\tif (edgeVec[i].m_bSelected)
\t\t\t\tcontinue;
\t\t\tif (min > edgeVec[i].m_iWeightValue)
\t\t\t{
\t\t\t\tmin = edgeVec[i].m_iWeightValue;
\t\t\t\tminEdge = i;
\t\t\t}
\t\t}

\t\tif (0 == min)
\t\t\treturn -1;

\t\treturn minEdge;
\t}

\tbool isInSet(const vector& nodeSet, int target)
\t{
\t\tfor (int i = 0; i < (int)nodeSet.size(); i++)
\t\t{
\t\t\tif (nodeSet[i] == target)
\t\t\t\treturn true;
\t\t}

\t\treturn false;
\t}

\tvoid mergeNodeSet(vector& nodeSetA, const vector& nodeSetB)
\t{
\t\tfor (size_t i = 0; i < (int)nodeSetB.size(); i++)
\t\t{
\t\t\tnodeSetA.push_back(nodeSetB[i]);
\t\t}
\t}
public:
\t//添加頂點
\tvoid addNode(Node *node)
\t{
\t\tassert(node);
\t\tm_pNodeArray[m_iNodeCount].m_cData = node->m_cData;
\t\tm_iNodeCount++;
\t}
\t//將頂點訪問設置默認
\tvoid resetNode()
\t{
\t\tfor (int i = 0; i < m_iNodeCount; i++) 

\t\t\tm_pNodeArray[i].m_bVisited = false;
\t}
\t//設置權重-有向圖
\tbool setValueToMatrixForDirectedGraph(int row, int col, int val = 1)
\t{
\t\tif (row < 0 || row >= m_iCapacity)
\t\t\treturn false;
\t\tif (col < 0 || col >= m_iCapacity)
\t\t\treturn false;
\t\tm_pMatrix[row*m_iCapacity + col] = val;
\t\treturn true;
\t}

\t//設置權重-無向圖
\tbool setValueToMatrixForUndirectedGraph(int row, int col, int val = 1)
\t{
\t\tif (row < 0 || row >= m_iCapacity)
\t\t\treturn false;
\t\tif (col < 0 || col >= m_iCapacity)
\t\t\treturn false;
\t\tm_pMatrix[row*m_iCapacity + col] = val;
\t\tm_pMatrix[col*m_iCapacity + row] = val;
\t\treturn true;
\t}
\t//獲取權重
\tbool getValueFromMatrix(int row, int col, int& val)
\t{
\t\tif (row < 0 || row >= m_iCapacity)
\t\t\treturn false;
\t\tif (col < 0 || col >= m_iCapacity)
\t\t\treturn false;
\t\tval = m_pMatrix[row*m_iCapacity + col];
\t\treturn true;
\t}
\t//打印矩陣
\tvoid printMatrix()
\t{
\t\tfor (int i = 0; i < m_iCapacity; i++)
\t\t{
\t\t\tfor (int j = 0; j < m_iCapacity; j++)
\t\t\t\tcout << m_pMatrix[i*m_iCapacity + j] << " ";
\t\t\tcout << endl;
\t\t}
\t}

\t//深度遍歷
\tvoid depthFirstTraverse(int index)
\t{ 

\t\tint val = 0;
\t\tcout << m_pNodeArray[index].m_cData << " ";
\t\tm_pNodeArray[index].m_bVisited = true;

\t\tfor (int i = 0; i < m_iCapacity; i++)
\t\t{
\t\t\tgetValueFromMatrix(index, i, val);
\t\t\tif (/*1 == val*/0 != val)
\t\t\t{
\t\t\t\tif (m_pNodeArray[i].m_bVisited)
\t\t\t\t\tcontinue;
\t\t\t\tdepthFirstTraverse(i);
\t\t\t}
\t\t\telse
\t\t\t\tcontinue;
\t\t}
\t}

\t//廣度遍歷
\tvoid breadthFirstTraverse(int index)
\t{
\t\tcout << m_pNodeArray[index].m_cData << " ";
\t\tm_pNodeArray[index].m_bVisited = true;

\t\tvector curVec;
\t\tcurVec.push_back(index);

\t\tbreadthFirstTraverseImpl(curVec);
\t}

\t//求最小生成樹-普里斯算法
\tvoid primTree(int index)
\t{
\t\tint val = 0;
\t\tint iEdgeCount = 0;
\t\tvector<edge> edgeVec;//待選邊集合

\t\t//從傳入點開始找
\t\tvector nodeIndexVec;
\t\tnodeIndexVec.push_back(index);

\t\t//結束條件：邊數=頂點數-1
\t\twhile (iEdgeCount < m_iCapacity - 1)
\t\t{
\t\t\t//查找傳入點的符合要求（權重不為0且目的點沒有被訪問）邊 

\t\t\tint row = nodeIndexVec.back();
\t\t\tcout << m_pNodeArray[row].m_cData << endl;
\t\t\tm_pNodeArray[row].m_bVisited = true;

\t\t\tfor (int i = 0; i < m_iCapacity; i++)
\t\t\t{
\t\t\t\tgetValueFromMatrix(row, i, val);
\t\t\t\tif (0 == val)
\t\t\t\t\tcontinue;
\t\t\t\tif (m_pNodeArray[i].m_bVisited)
\t\t\t\t\tcontinue;
\t\t\t\tEdge edge(row, i, val);
\t\t\t\tedgeVec.push_back(edge);
\t\t\t}

\t\t\t//取出最小邊
\t\t\tint retIndex = getMinEdge(edgeVec);
\t\t\tif (-1 != retIndex)
\t\t\t{
\t\t\t\t//存儲選中邊
\t\t\t\tedgeVec[retIndex].m_bSelected = true;
\t\t\t\tm_pEdgeArray[iEdgeCount] = edgeVec[retIndex];
\t\t\t\tcout << m_pNodeArray[m_pEdgeArray[iEdgeCount].m_iNodeIndexA].m_cData << " - ";
\t\t\t\tcout << m_pNodeArray[m_pEdgeArray[iEdgeCount].m_iNodeIndexB].m_cData << " (";
\t\t\t\tcout << m_pEdgeArray[iEdgeCount].m_iWeightValue << ") " << endl;
\t\t\t\tiEdgeCount++;

\t\t\t\tint iNodeIndex = edgeVec[retIndex].m_iNodeIndexB;
\t\t\t\t//設置點被訪問
\t\t\t\tm_pNodeArray[iNodeIndex].m_bVisited = true;
\t\t\t\t//存入目的點遞歸查找
\t\t\t\tnodeIndexVec.push_back(iNodeIndex);
\t\t\t}
\t\t}

\t}

\t//最小生成樹-克魯斯卡爾算法
\tvoid kruskalTree()
\t{
\t\tint val = 0;
\t\tint edgeCount = 0;

\t\t//定義存放節點集合數組
\t\tvector<vector> > nodeSets;
 

\t\t//第一步、取出所有邊
\t\tvector<edge> edgeVec;
\t\tfor (int i = 0; i < m_iCapacity; i++)
\t\t{
\t\t\tfor (int j = i + 1; j < m_iCapacity; j++)
\t\t\t{
\t\t\t\tgetValueFromMatrix(i, j, val);
\t\t\t\tif (0 == val)
\t\t\t\t\tcontinue;
\t\t\t\tif (m_pNodeArray[i].m_bVisited)
\t\t\t\t\tcontinue;
\t\t\t\tEdge edge(i, j, val);
\t\t\t\tedgeVec.push_back(edge);
\t\t\t}
\t\t}

\t\t//第二步、從所有邊中取出組成最小生成樹的邊
\t\t//1、算法結束條件：邊數=頂點數-1
\t\twhile (edgeCount < m_iCapacity - 1)
\t\t{
\t\t\t//2、從邊集合中找出最小邊
\t\t\tint retIndex = getMinEdge(edgeVec);
\t\t\tif (-1 != retIndex)
\t\t\t{
\t\t\t\tedgeVec[retIndex].m_bSelected = true;

\t\t\t\t//3、找出最小邊連接點
\t\t\t\tint nodeAIndex = edgeVec[retIndex].m_iNodeIndexA;
\t\t\t\tint nodeBIndex = edgeVec[retIndex].m_iNodeIndexB;

\t\t\t\t//4、找出點所在集合
\t\t\t\tbool nodeAInSet = false;
\t\t\t\tbool nodeBInSet = false;
\t\t\t\tint nodeAInSetLabel = -1;
\t\t\t\tint nodeBInSetLabel = -1;

\t\t\t\tfor (int i = 0; i < (int)nodeSets.size(); i++)
\t\t\t\t{
\t\t\t\t\tnodeAInSet = isInSet(nodeSets[i], nodeAIndex);
\t\t\t\t\tif (nodeAInSet)
\t\t\t\t\t\tnodeAInSetLabel = i;
\t\t\t\t}
 

\t\t\t\tfor (int i = 0; i < (int)nodeSets.size(); i++)
\t\t\t\t{
\t\t\t\t\tnodeBInSet = isInSet(nodeSets[i], nodeBIndex);
\t\t\t\t\tif (nodeBInSet)
\t\t\t\t\t\tnodeBInSetLabel = i;
\t\t\t\t}

\t\t\t\t//5、根據點集合的不同做不同處理
\t\t\t\tif (nodeAInSetLabel == -1 && nodeBInSetLabel == -1)
\t\t\t\t{
\t\t\t\t\tvector vec;
\t\t\t\t\tvec.push_back(nodeAIndex);
\t\t\t\t\tvec.push_back(nodeBIndex);
\t\t\t\t\tnodeSets.push_back(vec);
\t\t\t\t}
\t\t\t\telse if (nodeAInSetLabel == -1 && nodeBInSetLabel != -1)
\t\t\t\t{
\t\t\t\t\tnodeSets[nodeBInSetLabel].push_back(nodeAIndex);
\t\t\t\t}
\t\t\t\telse if (nodeAInSetLabel != -1 && nodeBInSetLabel == -1)
\t\t\t\t{
\t\t\t\t\tnodeSets[nodeAInSetLabel].push_back(nodeBIndex);
\t\t\t\t}
\t\t\t\telse if (-1 != nodeAInSetLabel && -1 != nodeBInSetLabel && nodeAInSetLabel != nodeBInSetLabel)
\t\t\t\t{
\t\t\t\t\t//mergeNodeSet(nodeSets[nodeAInSetLabel], nodeSets[nodeBInSetLabel]);
\t\t\t\t\tnodeSets[nodeAInSetLabel].insert(nodeSets[nodeAInSetLabel].end(),
\t\t\t\t\t\tnodeSets[nodeBInSetLabel].begin(),
\t\t\t\t\t\tnodeSets[nodeBInSetLabel].end());
\t\t\t\t\tfor (int k = nodeBInSetLabel; k < (int)nodeSets.size() - 1; k++)
\t\t\t\t\t{
\t\t\t\t\t\tnodeSets[k] = nodeSets[k + 1];
\t\t\t\t\t}
\t\t\t\t}
\t\t\t\telse if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel == nodeBInSetLabel)
\t\t\t\t{
\t\t\t\t\tcontinue;
\t\t\t\t}

\t\t\t\tm_pEdgeArray[edgeCount] = edgeVec[retIndex];
\t\t\t\tedgeCount++;

\t\t\t\tcout << m_pNodeArray[edgeVec[retIndex].m_iNodeIndexA].m_cData << " - ";
\t\t\t\tcout << m_pNodeArray[edgeVec[retIndex].m_iNodeIndexB].m_cData << " (";
\t\t\t\tcout << edgeVec[retIndex].m_iWeightValue << ") " << endl;
\t\t\t}
\t\t}
\t} 

};

#endif // !_CMAP_H_

/<edge>/<vector>/<edge>/<edge>/<assert.h>/<vector>/<iostream>/<code>

測試圖結構：

圖3-測試圖結構

測試函數main.cpp：

<code>#include "CMap.hpp"
#include <iostream>
using namespace std;
int main(int argc, char**argv)
{

\tCMap *pMap = new CMap(6);

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

\tpMap->addNode(pNodeA);
\tpMap->addNode(pNodeB);
\tpMap->addNode(pNodeC);
\tpMap->addNode(pNodeD);
\tpMap->addNode(pNodeE);
\tpMap->addNode(pNodeF);

\tpMap->setValueToMatrixForUndirectedGraph(0, 1, 7);
\tpMap->setValueToMatrixForUndirectedGraph(0, 2, 1);
\tpMap->setValueToMatrixForUndirectedGraph(0, 3, 9);
\tpMap->setValueToMatrixForUndirectedGraph(1, 2, 2);
\tpMap->setValueToMatrixForUndirectedGraph(1, 4, 3);
\tpMap->setValueToMatrixForUndirectedGraph(2, 3, 11);
\tpMap->setValueToMatrixForUndirectedGraph(2, 4, 8);
\tpMap->setValueToMatrixForUndirectedGraph(2, 5, 4);
\tpMap->setValueToMatrixForUndirectedGraph(3, 5, 5);
\tpMap->setValueToMatrixForUndirectedGraph(4, 5, 15);

\tcout << "打印矩陣: " << endl;
\tpMap->printMatrix();
\tcout << endl;

\tpMap->resetNode();

\tcout << "深度優先遍歷: " << endl;
\tpMap->depthFirstTraverse(0);
\tcout << endl;

\tpMap->resetNode();

\tcout << "廣度優先遍歷: " << endl; 

\tpMap->breadthFirstTraverse(0);
\tcout << endl;

\tpMap->resetNode();

\tcout << "普里姆算法: " << endl;
\tpMap->primTree(0);
\tcout << endl;

\tpMap->resetNode();

\tcout << "克魯斯卡爾算法: " << endl;
\tpMap->kruskalTree();
\tcout << endl;

\tpMap->resetNode();

\tsystem("pause");
\treturn 0;
}/<iostream>/<code>

執行結果：

圖4-執行結果

--|END|--

閱讀更多 changlvso 的文章

關鍵字: 算法 數據結構 頂點