C++實現(xiàn)圖的鄰接矩陣表示

更新時間：2020年04月27日 17:08:32 作者：ChanJose

這篇文章主要為大家詳細介紹了C++實現(xiàn)圖的鄰接矩陣表示，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了C++實現(xiàn)圖的鄰接矩陣表示代碼，供大家參考，具體內(nèi)容如下

1.遇到的問題：教材中寫著子類Graphmtx(我用GrapMatrix)繼承基類Graph

但是我在子類GraphMatrix中使用父類Graph的保護成員屬性：maxVertices 顯示沒有聲明（如下圖）。

原來，c++中聲明一個模板類及子類，在子類中如果需要訪問父類的protected變量，需要使用父類的類作用域限定符，否則會報“identifier not found”錯誤。如果不是模板類，可以直接訪問。

例如：要如下這樣使用父類的保護成員屬性，太麻煩了。

所以，我就不用繼承基類的方法了。直接把Graph父類的保護成員屬性放到GrapMatrix類中。

2.實現(xiàn)程序：

（1）GraphMatrix.h

#ifndef GraphMatrix_h
#define GraphMatrix_h
#include <iostream>
using namespace std;
 
const int DefaultVertices = 30; // 默認最大頂點數(shù)
 
template <class T, class E>
class GraphMatrix {
public:
 const E maxWeight = 100000; // 代表無窮大的值（=∞）
 GraphMatrix(int sz=DefaultVertices); // 構(gòu)造函數(shù)
 ~GraphMatrix(); // 析構(gòu)函數(shù)
 void inputGraph(); // 創(chuàng)建基于鄰接矩陣的圖
 void outputGraph(); // 輸出圖的所有頂點和邊信息
 T getValue(int i); // 取頂點i的值，i不合理返回0
 E getWeight(int v1, int v2); // 取邊(v1, v2)上的權(quán)值
 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)權(quán)值為cost
 bool removeVertex(int v); // 刪去頂點v和所有與它相關(guān)聯(lián)的邊
 bool removeEdge(int v1, int v2); // 在圖中刪去邊(v1, v2)
 int getVertexPos(T vertex); // 給出頂點vertice在圖中的位置
private:
 int maxVertices; // 圖中最大的頂點數(shù)
 int numEdges; // 當前邊數(shù)
 int numVertices; // 當前頂點數(shù)
 T *VerticesList; // 頂點表
 E **Edge; // 鄰接矩陣
};
 
// 構(gòu)造函數(shù)
template <class T, class E>
GraphMatrix<T, E>::GraphMatrix(int sz) {
 int i, j;
 
 maxVertices = sz;
 numVertices = 0;
 numEdges = 0;
 VerticesList = new T[maxVertices]; // 創(chuàng)建頂點表數(shù)組
 Edge = new E*[maxVertices]; // 創(chuàng)建鄰接矩陣數(shù)組
 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;
  }
 }
}
 
// 析構(gòu)函數(shù)
template <class T, class E>
GraphMatrix<T, E>::~GraphMatrix() {
 delete []VerticesList; // 釋放動態(tài)分配的空間
 delete []Edge;
}
 
// 創(chuàng)建基于鄰接矩陣的圖
template <class T, class E>
void GraphMatrix<T, E>::inputGraph() {
 int i, j, k;
 int n, m; // 要輸入的頂點數(shù)和邊數(shù)
 T e1, e2; // 邊的兩端頂點
 E weight; // 邊對應(yīng)的權(quán)值
 
 cout << "請輸入頂點數(shù)和邊數(shù):" << endl;
 cin >> n >> m;
 cout << "請輸入頂點：" << endl;
 for(i = 0; i < n; i++) { // 建立頂點表數(shù)據(jù)
  cin >> e1;
  insertVertex(e1); // 插入
 }
 cout << "請輸入邊的兩端頂點和權(quán)值:" << 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結(jié)束
}
 
// 輸出圖的所有頂點和邊信息
template <class T, class E>
void GraphMatrix<T, E>::outputGraph() {
 int i, j, n, m;
 T e1, e2;
 E w;
 
 n = numVertices;
 m = numEdges;
 cout << "頂點數(shù)為：" << n << "，邊數(shù)為：" << m << endl;
 for(i = 0; i < n; i++) {
  for(j = i+1; j < n; j++) {
   w = getWeight(i, j); // 取邊上權(quán)值
   if(w > 0 && w < maxWeight) { // 有效，即這兩頂點存在邊
    e1 = getValue(i);
    e2 = getValue(j);
    cout << "(" << e1 << "," << e2 << "," << w << ")" << endl;
   }
  }
 } // for
}
 
// 給出頂點vertice在圖中的位置
template <class T, class E>
int GraphMatrix<T, E>::getVertexPos(T vertex) {
 for(int i = 0; i < numVertices; i++)
  if(VerticesList[i] == vertex)
   return i;
 return -1;
}
 
// 取頂點i的值，i不合理返回NULL
template <class T, class E>
T GraphMatrix<T, E>::getValue(int i) {
 if(i >= 0 && i < numVertices)
  return VerticesList[i];
 return NULL;
}
 
// 取邊(v1, v2)上的權(quán)值
template <class T, class E>
E GraphMatrix<T, E>::getWeight(int v1, int v2) {
 if(v1 != -1 && v2 != -1) // 存在這兩個頂點
  return Edge[v1][v2];
 return 0;
}
 
// 取頂點v的第一個鄰接頂點
template <class T, class E>
int GraphMatrix<T, E>::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的下一個鄰接頂點
template <class T, class E>
int GraphMatrix<T, E>::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
template <class T, class E>
bool GraphMatrix<T, E>::insertVertex(const T& vertex) {
 if(numVertices == maxVertices) // 頂點表滿
  return false;
 VerticesList[numVertices++] = vertex;
 return true;
}
 
// 插入邊(v1, v2)權(quán)值為cost
template <class T, class E>
bool GraphMatrix<T, E>::GraphMatrix<T, E>::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和所有與它相關(guān)聯(lián)的邊
template <class T, class E>
bool GraphMatrix<T, E>::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相關(guān)聯(lián)邊數(shù)
 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--; // 頂點數(shù)減1
 // 用最后一行，填補第v行
 for(j = 0; j < numVertices; j++)
  Edge[v][j] = Edge[numVertices][j];
 return true;
}
 
// 在圖中刪去邊(v1, v2)
template <class T, class E>
bool GraphMatrix<T, E>::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--; // 邊數(shù)減1
  return true;
 }
 return false;
}
 
#endif /* GraphMatrix_h */

（2）main.cpp

// 測試數(shù)據(jù)：
/*
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[]) {
 GraphMatrix<char, int> st; // 聲明對象
 bool finished = false;
 int choice;
 char e1, e2, next;
 int weight;
 
 while(!finished) {
  cout << "[1]創(chuàng)建基于鄰接矩陣的圖" << 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;
}

測試結(jié)果：