歡迎您光臨本站 註冊首頁

C++實現圖的鄰接矩陣表示

←手機掃碼閱讀     madbeef @ 2020-05-03 , reply:0

本文實例為大家分享了C++實現圖的鄰接矩陣表示代碼,供大家參考,具體內容如下
1.遇到的問題:教材中寫著子類Graphmtx(我用GrapMatrix)繼承基類Graph
但是我在子類GraphMatrix中使用父類Graph的保護成員屬性:maxVertices 顯示沒有聲明(如下圖)。
原來,c++中聲明一個模板類及子類,在子類中如果需要訪問父類的protected變量,需要使用父類的類作用域限定符,否則會報“identifier not found”錯誤。如果不是模板類,可以直接訪問。
例如:要如下這樣使用父類的保護成員屬性,太麻煩了。
所以,我就不用繼承基類的方法了。直接把Graph父類的保護成員屬性放到GrapMatrix類中。
2.實現程序:
(1)GraphMatrix.h
#ifndef GraphMatrix_h #define GraphMatrix_h #include

using namespace std; const int DefaultVertices = 30; // 默認最大頂點數 templateclass GraphMatrix { public: const E maxWeight = 100000; // 代表無窮大的值(=∞) GraphMatrix(int sz=DefaultVertices); // 構造函數 ~GraphMatrix(); // 析構函數 void inputGraph(); // 創建基於鄰接矩陣的圖 void outputGraph(); // 輸出圖的所有頂點和邊信息 T getValue(int i); // 取頂點i的值,i不合理返回0 E getWeight(int v1, int v2); // 取邊(v1, v2)上的權值 int getFirstNeighbor(int v); // 取頂點v的第一個鄰接頂點 int getNextNeighbor(int v, int w); // 取v的鄰接頂點w的下一個鄰接頂點 bool insertVertex(const T& vertex); // 插入頂點vertice bool insertEdge(int v1, int v2, E cost); // 插入邊(v1, v2)權值為cost bool removeVertex(int v); // 刪去頂點v和所有與它相關聯的邊 bool removeEdge(int v1, int v2); // 在圖中刪去邊(v1, v2) int getVertexPos(T vertex); // 給出頂點vertice在圖中的位置 private: int maxVertices; // 圖中最大的頂點數 int numEdges; // 當前邊數 int numVertices; // 當前頂點數 T *VerticesList; // 頂點表 E **Edge; // 鄰接矩陣 }; // 構造函數 templateGraphMatrix::GraphMatrix(int sz) { int i, j; maxVertices = sz; numVertices = 0; numEdges = 0; VerticesList = new T[maxVertices]; // 創建頂點表數組 Edge = new E*[maxVertices]; // 創建鄰接矩陣數組 for(i = 0; i < maxVertices; i++) Edge[i] = new E[maxVertices]; for(i = 0; i < maxVertices; i++) { // 鄰接矩陣初始化 for(j = 0; j < maxVertices; j++) { if(i == j) // 矩陣對角處,即為同一頂點 Edge[i][j] = 0; else // 不是同一頂點的,即兩頂點一開始沒有邊相連,為無窮大∞ Edge[i][j] = maxWeight; } } } // 析構函數 templateGraphMatrix::~GraphMatrix() { delete []VerticesList; // 釋放動態分配的空間 delete []Edge; } // 創建基於鄰接矩陣的圖 templatevoid GraphMatrix::inputGraph() { int i, j, k; int n, m; // 要輸入的頂點數和邊數 T e1, e2; // 邊的兩端頂點 E weight; // 邊對應的權值 cout << "請輸入頂點數和邊數:" << endl; cin >> n >> m; cout << "請輸入頂點:" << endl; for(i = 0; i < n; i++) { // 建立頂點表數據 cin >> e1; insertVertex(e1); // 插入 } cout << "請輸入邊的兩端頂點和權值:" << endl; i = 0; while(i < m){ // 輸入邊 cin >> e1 >> e2 >> weight; // 輸入端點信息 j = getVertexPos(e1); // 查頂點號 k = getVertexPos(e2); if(j == -1 || k == -1) cout << "邊兩端點信息有誤,重新輸入!" << endl; else { insertEdge(j, k, weight); i++; } } // for結束 } // 輸出圖的所有頂點和邊信息 templatevoid GraphMatrix::outputGraph() { int i, j, n, m; T e1, e2; E w; n = numVertices; m = numEdges; cout << "頂點數為:" << n << ",邊數為:" << m << endl; for(i = 0; i < n; i++) { for(j = i+1; j < n; j++) { w = getWeight(i, j); // 取邊上權值 if(w > 0 && w < maxWeight) { // 有效,即這兩頂點存在邊 e1 = getValue(i); e2 = getValue(j); cout << "(" << e1 << "," << e2 << "," << w << ")" << endl; } } } // for } // 給出頂點vertice在圖中的位置 templateint GraphMatrix::getVertexPos(T vertex) { for(int i = 0; i < numVertices; i++) if(VerticesList[i] == vertex) return i; return -1; } // 取頂點i的值,i不合理返回NULL templateT GraphMatrix::getValue(int i) { if(i >= 0 && i < numVertices) return VerticesList[i]; return NULL; } // 取邊(v1, v2)上的權值 templateE GraphMatrix::getWeight(int v1, int v2) { if(v1 != -1 && v2 != -1) // 存在這兩個頂點 return Edge[v1][v2]; return 0; } // 取頂點v的第一個鄰接頂點 templateint GraphMatrix::getFirstNeighbor(int v) { if(v != -1) { for(int col = 0; col < numVertices; col++) if(Edge[v][col] > 0 && Edge[v][col]<maxWeight) return col; } return -1; } // 取v的鄰接頂點w的下一個鄰接頂點 templateint GraphMatrix::getNextNeighbor(int v, int w) { if(v != -1 && w != -1) { for(int col = w+1; col < numVertices; col++) { if(Edge[v][col] > 0 && Edge[v][col] < maxWeight) return col; } } return -1; } // 插入頂點vertice templatebool GraphMatrix::insertVertex(const T& vertex) { if(numVertices == maxVertices) // 頂點表滿 return false; VerticesList[numVertices++] = vertex; return true; } // 插入邊(v1, v2)權值為cost templatebool GraphMatrix::GraphMatrix::insertEdge(int v1, int v2, E cost) { if(v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices && Edge[v1][v2] == maxWeight) { // 頂點v1,v2都存在,並且v1,v2沒有邊 Edge[v1][v2] = Edge[v2][v1] = cost; numEdges++; return true; } return false; } // 刪去頂點v和所有與它相關聯的邊 templatebool GraphMatrix::removeVertex(int v) { if(v < 0 && v > numVertices) // v不在圖中,不刪除 return false; if(numVertices == 1) // 只剩一個頂點,不刪除 return false; int i, j; VerticesList[v] = VerticesList[numVertices-1]; // 用最後一個頂點替代當前要刪的頂點 // 刪除與v相關聯邊數 for(i = 0; i < numVertices; i++) { if(Edge[i][v] > 0 && Edge[i][v] < maxWeight) numEdges--; } // 用最後一列,填補第v列 for(i = 0; i < numVertices; i++) Edge[i][v] = Edge[i][numVertices-1]; numVertices--; // 頂點數減1 // 用最後一行,填補第v行 for(j = 0; j < numVertices; j++) Edge[v][j] = Edge[numVertices][j]; return true; } // 在圖中刪去邊(v1, v2) templatebool GraphMatrix::removeEdge(int v1, int v2) { if(v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices && Edge[v1][v2] < maxWeight) { Edge[v1][v2] = Edge[v2][v1] = maxWeight; numEdges--; // 邊數減1 return true; } return false; } #endif /* GraphMatrix_h */
(2)main.cpp
// 測試數據: /* 5 7 A B C D E A B 24 A C 46 B C 15 B E 67 C B 37 C D 53 E D 31 */ #include "GraphMatrix.h" int main(int argc, const char * argv[]) { GraphMatrixst; // 聲明對象 bool finished = false; int choice; char e1, e2, next; int weight; while(!finished) { cout << "[1]創建基於鄰接矩陣的圖" << endl; cout << "[2]輸出圖的所有頂點和邊信息" << endl; cout << "[3]取頂點v的第一個鄰接頂點" << endl; cout << "[4]取v的鄰接頂點w的下一個鄰接頂點" << endl; cout << "[5]插入頂點" << endl; cout << "[6]插入邊" << endl; cout << "[7]刪除頂點" << endl; cout << "[8]刪除邊" << endl; cout << "[9]退出" << endl; cout << "請輸入選擇[1-9]:"; cin >> choice; switch(choice) { case 1: st.inputGraph(); break; case 2: st.outputGraph(); break; case 3: cout << "請輸入頂點:"; cin >> e1; e2 = st.getValue(st.getFirstNeighbor(st.getVertexPos(e1))); if(e2) cout << "頂點" << e1 << "的第一個鄰接頂點為:" << e2 << endl; else cout << "頂點" << e1 << "沒有鄰接頂點!" << endl; break; case 4: cout << "請輸入頂點v和鄰接頂點w:"; cin >> e1 >> e2; next = st.getValue(st.getNextNeighbor(st.getVertexPos(e1), st.getVertexPos(e2))); if(next) cout << "頂點" << e1 << "的鄰接頂點" << e2 << "的下一個鄰接頂點為:" << next << endl; else cout << "頂點" << e1 << "的鄰接頂點" << e2 << "沒有下一個鄰接頂點!" << endl; break; case 5: cout << "請輸入要插入的頂點:"; cin >> e1; if(st.insertVertex(e1)) cout << "插入成功!" << endl; else cout << "表已滿,插入失敗!" << endl; break; case 6: cout << "請輸入要插入的邊的信息:" << endl; cin >> e1 >> e2 >> weight; st.insertEdge(st.getVertexPos(e1), st.getVertexPos(e2), weight); break; case 7: cout << "請輸入要刪除的頂點:"; cin >> e1; if(st.removeVertex(st.getVertexPos(e1))) cout << "頂點" << e1 << "已刪除!" << endl; else cout << "頂點" << e1 << "不在圖中!" << endl; break; case 8: cout << "請輸入要刪除的邊的兩個端點:" << endl; cin >> e1 >> e2; st.removeEdge(st.getVertexPos(e1), st.getVertexPos(e2)); break; case 9: finished = true; break; default: cout << "選擇輸入錯誤,請重新輸入!" << endl; } } return 0; }

[madbeef ] C++實現圖的鄰接矩陣表示已經有133次圍觀

http://coctec.com/docs/c/language/show-post-232645.html