圖
介紹
??圖是相較于樹更復雜的一種資料結構型別，它表示了多對多的對應關系，圖的結構其實就是一些頂點和一些邊的集合，圖又分為有向圖和無向圖，存盤圖的方法有很多，比如使用鄰接矩陣，鄰接表，十字鏈表和鄰接多重表等等，下面我們一一介紹一下這些內容，
圖的結構：
無向圖：
無向圖其實就是說頂點與頂點之間的關系沒有方向，只有說是連接的還是斷開的，
有向圖：
相對的，有向圖就是頂點與頂點之間不僅有斷開還是連接的關系，還要明確到是誰指向誰，
對頂點和邊的定義
先是頂點
class Node //頂點類
{
public:
char m_cdata; //頂點資料
bool m_bIsVisited; //判斷此頂點是否被訪問過，這是為了后面實作某些功能設定的
Node() {} //無參建構式
Node(char data) //含參建構式
{
m_cdata = https://www.cnblogs.com/vfdxvffd/p/data;
m_bIsVisited = false; //默認沒有被訪問過
}
};
再是邊
class Edge
{
public:
int m_iNodeIndexA; //邊連接的A頂點
int m_iNodeIndexB; //邊連接的B頂點
int m_iWeightValue; //邊上的權值，這也是為了后面某些功能設定的
bool m_bIs_Selected;//標記這個邊是否被選過
Edge(int nodeIndexA, int nodeIndexB, int weightValue) //建構式
{
m_iNodeIndexA = nodeIndexA;
m_iNodeIndexB = nodeIndexB;
m_iWeightValue = https://www.cnblogs.com/vfdxvffd/p/weightValue;
m_bIs_Selected = false; //初始默認這個邊沒有被選擇過
}
Edge(){} //無參建構式
};
圖的存盤方法
??這里只介紹一種鄰接矩陣，剩下的以后再補充，顧名思義，鄰接矩陣其實就是一個矩陣，用一個二維陣列來定義它，我們將頂點存盤在一個陣列里面，假如有5個頂點，那么鄰接矩陣就應該是一個5*5的二維陣列，
???????????
??對于無向圖來說，我們用1表示連接，用0表示未連接，設陣列名為Maritx,那么Matrix[1][3] = 0表示頂點陣列中下標為1的頂點和下標為3的頂點沒有連接關系，Matrix[1][0] = 1表示下標為1的頂點和下標為0的頂點連接在了一起，通過觀察可以發現，無向圖的鄰接矩陣是一個上三角和下三角對稱的矩陣，而其主對角線上元素全為0，比較不能自己和自己連接在一起，
??而對于有向圖，如果下標為1的元素指向了下標為2的元素，而下標為2的元素卻沒有指向下標為1的元素，那么Matrix[1][2] = 1且Matrix[2][1] = 0
對圖的定義（代碼實作）
??定義里面有些一下資料成員是為了后面實作某些演算法才加的，
class CMap
{
private:
int m_iCapacity; //圖中最多可以容納的頂點數
int m_iNodeCount; //已經添加的頂點數
Node* m_pNodeArray; //用來存放頂點陣列
int* m_pMatrix; //用來存放鄰接矩陣
Edge* m_pEdge; //用來存最小生成樹的邊
public:
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));//將m_pMatrix所有元素初始化為0
m_pEdge = new Edge[m_iCapacity - 1]; //最小生成樹邊的個數就等于頂點個數減一
}
~CMap()
{
delete[]m_pNodeArray;
delete[]m_pMatrix;
delete[]m_pEdge;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/95039.html
標籤：C++