#include <iostream>

#include<iomanip>

#include<queue>

using namespace std;

?

const int DefaultVertices = 30; // 默認(rèn)最大頂點(diǎn)數(shù)

const int maxWeight = 100000; // 代表無(wú)窮大的值（=∞

template <class T, class E>

class GraphMatrix {

public:

??

? ? GraphMatrix(int sz=DefaultVertices); // 構(gòu)造函數(shù)

? ? ~GraphMatrix(); // 析構(gòu)函數(shù)

? ? void inputGraph(); // 創(chuàng)建基于鄰接矩陣的圖

? ? void outputGraph(); // 輸出圖的所有頂點(diǎn)和邊信息

? ? T getValue(int i); // 取頂點(diǎn)i的值，i不合理返回0

? ? E getWeight(int v1, int v2); // 取邊(v1, v2)上的權(quán)值

? ? int getFirstNeighbor(int v); // 取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)

? ? int getNextNeighbor(int v, int w); // 取v的鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)

? ? bool insertVertex(const T& vertex); // 插入頂點(diǎn)vertice

? ? bool insertEdge(int v1, int v2, E cost); // 插入邊(v1, v2)權(quán)值為cost

? ? bool removeVertex(int v); // 刪去頂點(diǎn)v和所有與它相關(guān)聯(lián)的邊

? ? bool removeEdge(int v1, int v2); // 在圖中刪去邊(v1, v2)

? ? int getVertexPos(T vertex); // 給出頂點(diǎn)vertice在圖中的位置

? ? void display( );?

? ? void DFS(int v);

? ? void reset(){int i;for(i=0;i<numVertices;i++)visited[i]=false;}

void BFS(int v );

private:

? ? int maxVertices; // 圖中最大的頂點(diǎn)數(shù)

? ? int numEdges; // 當(dāng)前邊數(shù)

? ? int numVertices; // 當(dāng)前頂點(diǎn)數(shù)

? ? T *VerticesList; // 頂點(diǎn)表

? ? bool * visited;

? ? E **Edge; // 鄰接矩陣

};

template <class T, class E>

void GraphMatrix<T, E>::DFS(int v){ //基于鄰接矩陣的深度優(yōu)先遍歷

cout << VerticesList[v]<< "\t";

visited[v] = true;

for(int i = 0 ; i < numVertices ; i++)

{ //依次檢查v 的所有鄰接點(diǎn)

if(Edge[v][i] ==1&& !visited[i]){ //v、w 鄰接并且w 未被訪問(wèn)

DFS(i ); //從節(jié)點(diǎn)w 出發(fā)，遞歸深度優(yōu)先遍歷

}

}

?

}

?

?template <class T, class E>

void GraphMatrix<T, E>::display()

{

int i,j;

cout<<"鄰接矩陣是:\n";

for(i=0;i<numVertices;i++)

{

?

? for(j=0;j<numVertices;j++)

? ? cout<<setw(8)<<Edge[i][j];

cout<<endl;

? ? ?}

}

template <class T, class E>

void GraphMatrix<T, E>::BFS(int v ){

int u,w;

cout <<VerticesList[v]<< "\t"; //輸入某個(gè)頂點(diǎn)在一維數(shù)組中的下標(biāo)

visited[v]=true; //訪問(wèn)第v個(gè)頂點(diǎn)，并置訪問(wèn)標(biāo)志數(shù)組相應(yīng)值為true

queue<int> q; //初始化隊(duì)列

? ? q.push(v);

while(!q.empty()){ //隊(duì)列非空

u=q.front();q.pop(); //隊(duì)頭頂點(diǎn)出隊(duì)并將其置為u

// 取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)

? ? ? ??

? ? ? ? ?

for( w=getFirstNeighbor(u); w!=-1; w=getNextNeighbor(u,w))//依次檢查u的所有鄰接點(diǎn)w

{

? ? ? ? if(!visited[w]){ //w為u的尚未訪問(wèn)的鄰接頂點(diǎn)

cout <<VerticesList[w]<< "\t"; //輸出已訪問(wèn)過(guò)的頂點(diǎn)下標(biāo)

visited[w]=true; //將訪問(wèn)過(guò)的頂點(diǎn)標(biāo)記為true

q.push(w); //下標(biāo)為w的頂點(diǎn)進(jìn)隊(duì)

}

}

//getFirstNeighbor表示u的第一個(gè)鄰接點(diǎn)

//w>=0表示存在鄰接點(diǎn)

//getNextNeighbor表示u的相對(duì)于w的下一個(gè)鄰接點(diǎn)

}

}

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)建頂點(diǎn)表數(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) // 矩陣對(duì)角處，即為同一頂點(diǎn)

? ? ? ? ? ? ? ? Edge[i][j] = 0;

? ? ? ? ? ? else // 不是同一頂點(diǎn)的，即兩頂點(diǎn)一開始沒(méi)有邊相連，為無(wú)窮大∞

? ? ? ? ? ? ? ? Edge[i][j] = maxWeight;

? ? ? ? }

? ? }

}

?

// 析構(gòu)函數(shù)

template <class T, class E>

GraphMatrix<T, E>::~GraphMatrix() {

? ? delete []VerticesList; // 釋放動(dòng)態(tài)分配的空間

? ? delete []Edge;

}

?

// 創(chuàng)建基于鄰接矩陣的圖

template <class T, class E>

void GraphMatrix<T, E>::inputGraph() {

? ? int i, j, k;

? ? int n, m; // 要輸入的頂點(diǎn)數(shù)和邊數(shù)

? ? T e1, e2; // 邊的兩端頂點(diǎn)

? ? E weight; // 邊對(duì)應(yīng)的權(quán)值

? ??

? ? cout << "請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):" << endl;

? ? cin >> n >> m;

? ? visited=new bool[n];

? ? cout << "請(qǐng)輸入頂點(diǎn)：" << endl;

? ? for(i = 0; i < n; i++) { // 建立頂點(diǎn)表數(shù)據(jù)

? ? ? ? cin >> e1;

? ? ? ? insertVertex(e1); // 插入

? ? ? ? visited[i]=false;

? ? }

? ? cout << "請(qǐng)輸入邊的兩端頂點(diǎn)和權(quán)值:" << endl;

? ? i = 0;

? ? while(i < m){ // 輸入邊

? ? ? ? cin >> e1 >> e2 >> weight; // 輸入端點(diǎn)信息

? ? ? ? j = getVertexPos(e1); // 查頂點(diǎn)號(hào)

? ? ? ? k = getVertexPos(e2);

? ? ? ? if(j == -1 || k == -1)

? ? ? ? ? ? cout << "邊兩端點(diǎn)信息有誤，重新輸入!" << endl;

? ? ? ? else {

? ? ? ? ? ? insertEdge(j, k, weight);

? ? ? ? ? ? i++;

? ? ? ? }

? ? } // for結(jié)束

}

?

// 輸出圖的所有頂點(diǎn)和邊信息

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 << "頂點(diǎn)數(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) { // 有效，即這兩頂點(diǎn)存在邊

? ? ? ? ? ? ? ? e1 = getValue(i);

? ? ? ? ? ? ? ? e2 = getValue(j);

? ? ? ? ? ? ? ? cout << "(" << e1 << "," << e2 << "," << w << ")" << endl;

? ? ? ? ? ? }

? ? ? ? }

? ? } // for

}

?

// 給出頂點(diǎn)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;

}

?

// 取頂點(diǎn)i的值，i不合理返回NULL

template <class T, class E>

T GraphMatrix<T, E>::getValue(int i) {

? ? if(i >= 0 && i < numVertices)

? ? ? ? return VerticesList[i];

? ?// return 0;

}

?

// 取邊(v1, v2)上的權(quán)值

template <class T, class E>

E GraphMatrix<T, E>::getWeight(int v1, int v2) {

? ? if(v1 != -1 && v2 != -1) // 存在這兩個(gè)頂點(diǎn)

? ? ? ? return Edge[v1][v2];

? ? return 0;

}

?

// 取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)

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的鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)

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;

}

?

// 插入頂點(diǎn)vertice

template <class T, class E>

bool GraphMatrix<T, E>::insertVertex(const T& vertex) {

? ? if(numVertices == maxVertices) // 頂點(diǎn)表滿

? ? ? ? return false;

? ? VerticesList[numVertices++] = vertex;

? ? return true;

}

?

// 插入邊(v1, v2)權(quán)值為cost

template <class T, class E>

bool GraphMatrix<T, E>::insertEdge(int v1, int v2, E cost)?

{

? ? if(v1 > -1 && v1 < numVertices && v2 > -1 && v2 < numVertices && Edge[v1][v2] == maxWeight) { // 頂點(diǎn)v1,v2都存在，并且v1，v2沒(méi)有邊

? ? ? ? Edge[v1][v2] = cost;//Edge[v2][v1] = cost;

? ? ? ? numEdges++;

? ? ? ? return true;

? ? }

? ? return false;

}

?

// 刪去頂點(diǎn)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) // 只剩一個(gè)頂點(diǎn)，不刪除

? ? ? ? return false;

? ? int i, j;

? ??

? ? VerticesList[v] = VerticesList[numVertices-1]; // 用最后一個(gè)頂點(diǎn)替代當(dāng)前要?jiǎng)h的頂點(diǎn)

? ? // 刪除與v相關(guān)聯(lián)邊數(shù)

? ? for(i = 0; i < numVertices; i++) {

? ? ? ? if(Edge[i][v] > 0 && Edge[i][v] < maxWeight)

? ? ? ? ? ? numEdges--;

? ? }

? ? // 用最后一列，填補(bǔ)第v列

? ? for(i = 0; i < numVertices; i++)

? ? ? ? Edge[i][v] = Edge[i][numVertices-1];

? ? numVertices--; // 頂點(diǎn)數(shù)減1

? ? // 用最后一行，填補(bǔ)第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;

}

?

int main(int argc, const char * argv[]) {

? ? GraphMatrix<char, int> st; // 聲明對(duì)象

? ? bool finished = false;

? ? int choice;

? ? char e1, e2, next;

? ? int weight;

? ??

? ? while(!finished) {

? ? ? ? cout << "[1]創(chuàng)建基于鄰接矩陣的圖" << endl;

? ? ? ? cout << "[2]輸出圖的所有頂點(diǎn)和邊信息" << endl;

? ? ? ? cout << "[3]取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)" << endl;

? ? ? ? cout << "[4]取v的鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)" << endl;

? ? ? ? cout << "[5]插入頂點(diǎn)" << endl;

? ? ? ? cout << "[6]插入邊" << endl;

? ? ? ? cout << "[7]刪除頂點(diǎn)" << endl;

? ? ? ? cout << "[8]刪除邊" << endl;

? ? ? ? cout<<? "[9]深度優(yōu)先搜索 "<<endl;

? ? ? ? cout<<? "[10]廣度優(yōu)先搜索 "<<endl;

? ? ? ? cout << "[11]退出" << endl;

? ? ? ? cout << "請(qǐng)輸入選擇[1-11]：";

? ? ? ? cin >> choice;

? ? ? ? switch(choice) {

? ? ? ? ? ? case 1:

? ? ? ? ? ? ? ? st.inputGraph();

? ? ? ? ? ? ? ? st.display();

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? case 2:

? ? ? ? ? ? ? ? st.outputGraph();

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? case 3:

? ? ? ? ? ? ? ? cout << "請(qǐng)輸入頂點(diǎn):";

? ? ? ? ? ? ? ? cin >> e1;

? ? ? ? ? ? ? ? e2 = st.getValue(st.getFirstNeighbor(st.getVertexPos(e1)));

? ? ? ? ? ? ? ? if(e2)

? ? ? ? ? ? ? ? ? ? cout << "頂點(diǎn)" << e1 << "的第一個(gè)鄰接頂點(diǎn)為:" << e2 << endl;

? ? ? ? ? ? ? ? else

? ? ? ? ? ? ? ? ? ? cout << "頂點(diǎn)" << e1 << "沒(méi)有鄰接頂點(diǎn)！" << endl;

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? case 4:

? ? ? ? ? ? ? ? cout << "請(qǐng)輸入頂點(diǎn)v和鄰接頂點(diǎn)w:";

? ? ? ? ? ? ? ? cin >> e1 >> e2;

? ? ? ? ? ? ? ? next = st.getValue(st.getNextNeighbor(st.getVertexPos(e1), st.getVertexPos(e2)));

? ? ? ? ? ? ? ? if(next)

? ? ? ? ? ? ? ? ? ? cout << "頂點(diǎn)" << e1 << "的鄰接頂點(diǎn)" << e2 << "的下一個(gè)鄰接頂點(diǎn)為:" << next << endl;

? ? ? ? ? ? ? ? else

? ? ? ? ? ? ? ? ? ? cout << "頂點(diǎn)" << e1 << "的鄰接頂點(diǎn)" << e2 << "沒(méi)有下一個(gè)鄰接頂點(diǎn)！" << endl;

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? case 5:

? ? ? ? ? ? ? ? cout << "請(qǐng)輸入要插入的頂點(diǎn)：";

? ? ? ? ? ? ? ? cin >> e1;

? ? ? ? ? ? ? ? if(st.insertVertex(e1))

? ? ? ? ? ? ? ? ? ? cout << "插入成功！" << endl;

? ? ? ? ? ? ? ? else

? ? ? ? ? ? ? ? ? ? cout << "表已滿，插入失??！" << endl;

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? case 6:

? ? ? ? ? ? ? ? cout << "請(qǐng)輸入要插入的邊的信息:" << endl;

? ? ? ? ? ? ? ? cin >> e1 >> e2 >> weight;

? ? ? ? ? ? ? ? st.insertEdge(st.getVertexPos(e1), st.getVertexPos(e2), weight);

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? case 7:

? ? ? ? ? ? ? ? cout << "請(qǐng)輸入要?jiǎng)h除的頂點(diǎn)：";

? ? ? ? ? ? ? ? cin >> e1;

? ? ? ? ? ? ? ? if(st.removeVertex(st.getVertexPos(e1)))

? ? ? ? ? ? ? ? ? ? cout << "頂點(diǎn)" << e1 << "已刪除!" << endl;

? ? ? ? ? ? ? ? else

? ? ? ? ? ? ? ? ? ? cout << "頂點(diǎn)" << e1 << "不在圖中!"? << endl;

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? case 8:

? ? ? ? ? ? ? ? cout << "請(qǐng)輸入要?jiǎng)h除的邊的兩個(gè)端點(diǎn)：" << endl;

? ? ? ? ? ? ? ? cin >> e1 >> e2;

? ? ? ? ? ? ? ? st.removeEdge(st.getVertexPos(e1), st.getVertexPos(e2));

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? case 9:

? ? ? ? ? ? st.reset();

st.DFS(0);

cout<<endl;

break;

case 10:

st.reset();

st.BFS(0);

cout<<endl;

break;

break;

? ? ? ? ? ? case 11:

? ? ? ? ? ? ? ? finished = true;

? ? ? ? ? ? ? ? break;

? ? ? ? ? ? default:

? ? ? ? ? ? ? ? cout << "選擇輸入錯(cuò)誤，請(qǐng)重新輸入!" << endl;

? ? ? ? }

? ? }

? ? return 0;

}