圖
圖在資料結構中是多對多的關系，一個頂點可以和多個頂點有聯系，其通常表示為：G(V,E)，其中G表示一個圖，V表示圖的頂點集合，E表示圖的邊集合，
1.圖的定義
有向圖：
圖中任意兩個頂點間的邊都是有向邊，則稱該圖為有向圖，連接兩個頂點間的有向邊稱為弧，弧起點稱為弧頭，終點稱為弧尾，表示方法為<A,B>，A為弧尾，B為弧頭，
如果圖中任意兩個頂點間都存在互為來往的有向邊，則稱該圖為有向完全圖，有向完全圖的邊長總數為\(n*(n-1)\)，其中n是頂點個數，
有向圖頂點的度和弧的關系：\(e=\sum_{i=1}^{n}ID(v_i)=\sum_{i=1}^{n}OD(v_i)\)，其中e是圖的邊長總數，n為圖的頂點總數，\(ID(v_i)\)是頂點的入度，\(OD(v_i)\)是頂點的出度，
無向圖：
圖中任意兩個頂點間的邊都是無向的，則稱該圖為無向圖，無向邊表示方法為(A,B)，
如果圖中任意兩個頂點間都存在無向邊，則稱該圖為無向完全圖，無向完全圖的邊長總數是\(n*(n-1)/2\)，其中n是頂點個數，
無向圖頂點的度和邊長的關系：\(e=\frac{1}{2}\sum_{i=1}^{n}TD(v_i)\)，其中\(TD(v_i)\)是頂點\(v_i\)的度，e是圖的邊長總數，n為圖的頂點總數，
網：
邊或弧帶權的圖稱為網，
2.圖的存盤結構
鄰接矩陣：
圖的鄰接矩陣存盤方式是將圖的頂點和圖的邊或弧分開存盤，將圖的頂點存入到一個一維陣列，圖的邊或弧存盤到二維陣列，
鄰接矩陣是一個\(n*n\)的方陣，表示方法如下：
\(arc[i][j]=\left\{\begin{array}{}1,若(v_i,v_j)\in\textbf{E}或<v_i,v_j>\in\textbf{E}, \\ 0,反之\end{array}\right.\)
定義資料結構為：
const int MAXVEX=100;//頂點的最大個數
template<class VertexType,class EdgeType>
class MGraph
{
//成員資料私有化
private:
VertexType vexs[MAXVEX]; //頂點表
EdgeType arc[MAXVEX][MAXVEX];//鄰接矩陣
int numVertexs,numEdges;
};
構造一個圖：
void Creat
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30646.html
標籤：C++
上一篇：二叉排序樹
下一篇：二叉樹