鄰接矩陣有兩種, 不帶權圖和網的鄰接矩陣. 不帶權圖的鄰接矩陣元素為0或1, 網的鄰接矩陣中包含0, INF, 和邊上的權值, 權值類型T可為整型, 實型. 三元組(u, v, w)代表一條邊, u, v是邊的兩個定點, w表示u v的關系:? a[u][u] = 0, 兩種鄰接矩陣的主對角元素都是0. a[u][v] = w, 若<u, v> 在E中, 則w = 1(不帶權圖)或w = w(i, j)(網). 若<u, v>不在E中,? 則w = noEdge, noEdge = 0(不帶權圖)或noEdge = INF(網). 保護數據成員T **a指向動態生成的二維數組, 用來存儲鄰接矩陣. 包含的函數Exist(): 若輸入參數u, v無效或a[u][v] == noEdge, 則不存在邊<u, v>, 返回false, 否則返回true. 函數Insert(): 若輸入參數u, v無效返回Failure. 若a[u][v] != noEdge, 表示邊<u, v>已經存在, 函數返回Duplicate. 否則添加邊<u, v>, 返回Success, 具體做法: a[u][v] = w, e++. 函數Remove(): 若輸入參數u, v無效, 不能執行刪除運算, 返回Failure. 若a[u][v] == noEdge, 表示圖中不存在邊<u, v>, 函數返回Notpresent. 否則從鄰接矩陣中刪除邊<u, v>, 返回Success, 具體做法: a[u][v] = noEdge, e--. 實現代碼: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" #include "queue" #include "stack" #include "cmath" #include "utility" #include "map" #include "set" #include "vector" #include "list" #include "string" using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent, Failure }; template <class T> class Graph { public: virtual ~Graph() {}; virtual ResultCode Insert(int u, int v, T &w) = 0; virtual ResultCode Remove(int u, int v) = 0; virtual bool Exist(int u, int v) const = 0; /* data */ }; template <class T> class MGraph: public Graph<T> { public: MGraph(int mSize, const T& noedg); ~MGraph(); ResultCode Insert(int u, int v, T &w); ResultCode Remove(int u, int v); bool Exist(int u, int v) const; int Vertices() const { return n; } void Output(); protected: T **a; T noEdge; int n, e; /* data */ }; template <class T> void MGraph<T>::Output() { for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) if(a[i][j] == noEdge) cout << "NE\t"; else cout << a[i][j] << "\t"; cout << endl; } cout << endl << endl << endl; } template <class T> MGraph<T>::MGraph(int mSize, const T &noedg) { n = mSize, e = 0, noEdge = noedg; a = new T *[n]; for(int i = 0; i < n; ++i) { a[i] = new T[n]; for(int j = 0; j < n; ++j) a[i][j] = noEdge; a[i][i] = 0; } } template <class T> MGraph<T>::~MGraph() { for(int i = 0; i < n; ++i) delete []a[i]; delete []a; } template <class T> bool MGraph<T>::Exist(int u, int v) const { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v || a[u][v] == noEdge) return false; return true; } template <class T> ResultCode MGraph<T>::Insert(int u, int v, T &w) { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure; if(a[u][v] != noEdge) return Duplicate; a[u][v] = w; e++; return Success; } template <class T> ResultCode MGraph<T>::Remove(int u, int v) { if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure; if(a[u][v] == noEdge) return NotPresent; a[u][v] = noEdge; e--; return Success; } int main(int argc, char const *argv[]) { MGraph<int> mg(4, 99); int w = 4; mg.Insert(1, 0, w); mg.Output(); w = 5; mg.Insert(1, 2, w); mg.Output(); w = 3; mg.Insert(2, 3, w); mg.Output(); w = 1; mg.Insert(3, 0, w); mg.Output(); w = 1; mg.Insert(3, 1, w); mg.Output(); return 0; } ~~~