用邻接矩阵存储的图的代码实现（创建、遍历以及各种基本操作）（附C++实现代码）

待我称王封你为后i 2023-06-18 15:57 13阅读 0赞

#### 一、图 ####

**图的定义：** 图G由两个集合E和V组成，记为G=(V,E)，其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。V(G)和E(G)通常用来表示顶点集合和边集合。E(G)可以为空集，如果E(G)为空，说明只有顶点而没有边。

##### 二、 图的分类 #####

**1、有向图：** 如果E(G)为有向边的集合，则该图就表示为有向图。  
**2、无向图：** 如果E(G)为无向边的集合，则该图就表示为无向图。  
**有向图的边又称为是弧，例如<x,y>为一条弧，且x为弧尾，y为弧头。**

##### 易混淆概念： #####

**1、** 路径：路径是指从顶点v到顶点v’的一个顶点序列  
**2、** 路径长度： 路径长度是指一条路径上经过的边或者弧的数目。  
**3、** 简单路径：指的是这条路径不会出现重复的顶点。  
**4、** 简单回路或者简单环：指的是除了第一个顶点和最后一个顶点外，路径上不出现重复的顶点的路径。  
**5、** **连通、连通图以及连通分量**

*  连通：指的是在图中，vi到vj有路径，就说明vi和vj是连通的
 *  连通图：值的是图的任意两个顶点都是连通的，就说明该图是连通的
 *  连通分量：所谓连通分量，指的就是无向图中的**极大连通子图**。
 *  至于啥是**极大连通子图** ，以下给出**极大连通子图和极小连通子图**的定义。
 *  **极大连通子图与极小连通子图：**
 *  1、极大连通子图，**所谓称为极大，意思是加入任意一个不属于图的点集的顶点都会变得不连通。** 并且对于**连通图而言**，就只有一个极大连通子图，就是它自己本身。而非连通图有多个极大连通子图。
 *  2、极小连通子图，**所谓是极小，意思是指不能删除其中的任意一条边，如果删除其中的任意一条边都会变得不连通。** 极小连通子图其实就是连通图的生成树。也因此**极小连通子图只存在于连通图中**。

如果觉得极大连通子图和极小连通子图的概念解释不够清楚，可以点击这里[点击传送][Link 1]。

#### 三、图的实现（邻接矩阵的形式以及基本操作的实现） ####

**一、** **邻接矩阵**  
**实现代码如下：** 代码附详细解释

#include<iostream>
    #include<iomanip>//内置输出对齐的函数
    #include"Node.h"
    using namespace std;
    
    #define MaxVexNum 100//定义最大的顶点数
    #define MaxInt de_num;//最大值
    
    typedef char VerTexType;//定义顶点的类型为char
    typedef int ArcType;//定义边的权值为int类型
    
    int de_num = 32767;//默认值
    //定义图的结构
    class MyGraph {
    public:
    	//顶点表
    	VerTexType vexs[MaxVexNum];
    	//邻接矩阵	
    	ArcType arcs[MaxVexNum][MaxVexNum];
    	//记录图的顶点数和边数
    	int curVexNum;
    	int curArcNum;
    };

##### 邻接矩阵的创建函数： #####

void creatUndirected_Graph(MyGraph &mygraph) {
    	cout << "请依次输入图的总顶点数，边数" << endl;
    	cin >> mygraph.curVexNum >> mygraph.curArcNum;
    
    	cout << "请依次输入顶点的信息" << endl;
    	for(int i = 0; i < mygraph.curVexNum; i++) {
    		cin >> mygraph.vexs[i];
    	}
    	
    	//初始化邻接矩阵
    	for (int i = 0; i < mygraph.curVexNum; i++) {
    		for (int j = 0; j < mygraph.curVexNum; j++) {
    			mygraph.arcs[i][j] = MaxInt;
    		}
    	}
    	
    	//输入一条边所依附的两个顶点以及对应的权值，无向图的权值全为1
    	char v1 = '0';
    	char v2 = '0';
    	int w = 0;
    	int temp_i = 0;
    	int temp_j = 0;
    	
    	for (int i = 0; i < mygraph.curArcNum; i++) {//循环边数次，总共需要输入curArcNum条边
    		cout << "请输入一条边所依附的两个顶点以及相应的权值" << endl;
    		cin >> v1 >> v2 >> w;
    		//找打这两个顶点在定点表中所对应的下标
    		temp_i = locateVex(mygraph, v1);
    		temp_j = locateVex(mygraph, v2);
    		if (temp_i != -1 && temp_j != -1) {
    			mygraph.arcs[temp_i][temp_j] = w;
    			mygraph.arcs[temp_j][temp_i] = w;
    			cout << "插入成功!" << endl;
    		}
    	}
    }

###### 遍历图 ######

//打印图的邻接矩阵的函数print\_graph

void print_graph(MyGraph mygraph) {
    	for (int i = 0; i < mygraph.curVexNum; i++) {
    		cout <<setw(3)<< mygraph.vexs[i]<<" ";
    	}
    	cout << endl;
    
    	for (int i = 0; i < mygraph.curVexNum; i++) {
    		cout << mygraph.vexs[i] << "|";
    		for (int j = 0; j < mygraph.curVexNum; j++) {
    			cout << left;//向左对齐打印
    			cout << setw(3) << mygraph.arcs[i][j] << " ";
    		}
    		cout << endl;
    	}
    }

##### 在图中返回顶点下标的函数 #####

//找到对应顶点在邻接矩阵中的下标
    int locateVex(MyGraph mygraph, char v1) {
    	for (int i = 0; i < mygraph.curVexNum; i++) {
    		if (mygraph.vexs[i] == v1) {//匹配就返回下标i
    			return i;
    		}
    	}
    	cout << "请检查你输入的顶点是否存在！" << endl;
    	return -1;
    }

##### 图是否为空 #####

//判断图是否为空
    bool mygraph_isEmpty(MyGraph mygraph) {
    	if (mygraph.curVexNum != 0) {
    		return false;
    	}
    	else {
    		cout << "图为空" << endl;
    		return true;
    	}
    }

##### 销毁图mygraph #####

bool DestrioyGraph(MyGraph &mygraph) {
    	if (mygraph.curVexNum != 0) {
    		//即图中存在节点，那么图非空
    		delete[] mygraph.vexs;
    		delete[] mygraph.arcs;
    		return true;
    	}
    	else {
    		return false;
    	}
    }

##### 返回第一个邻接顶点 #####

int firstAdjVex(MyGraph mygraph,char v) {
    	if (mygraph_isEmpty(mygraph)) {
    		return false;
    	}
    	//先找到v的位置
    	int temp_index = locateVex(mygraph, v);
    	
    	//然后到邻接矩阵中对应的行中，以行遍历，第一个就是第一个邻接顶点
    
    	for (int i = 0; i < mygraph.curVexNum; i++) {
    		if (mygraph.arcs[temp_index][i] != de_num && i!=temp_index) {
    			return i;
    		}
    	}
    	cout << "没有邻接顶点！" << endl;
    	return -1;
    }

##### v是图中的某个顶点， w是v的邻接顶点 返回w的的下一个邻接顶点 #####

int nextAdjVex(MyGraph mygraph, char v, char w) {
    	if (mygraph_isEmpty(mygraph)) {
    		return false;
    	}
    	int index_w = locateVex(mygraph, w);//w的下标
    	int index_v = locateVex(mygraph, v);//v的下标
    
    	for (int i = index_w + 1; i < mygraph.curVexNum; i++) {
    		if (mygraph.arcs[index_v][i] != de_num) {
    			return i;
    		}
    	}
    	return -1;//说明w已经是最后一个邻接点了
    }

##### 向图中添加一个顶点 #####

bool insertVex(MyGraph &mygraph, char v) {
    	if (mygraph_isEmpty(mygraph)) {//判断是否为空
    		return false;
    	}
    	
    	//向图中添加一个顶点
    	for (int i = 0; i < mygraph.curVexNum; i++) {
    		if (v == mygraph.vexs[i]) {
    			cout << "图中已经存在该节点！请检查" << endl;
    			return false;
    		}
    	}
    	
    	mygraph.curVexNum++;//新添加一个顶点，顶点数加一
    	//并且将矩阵的新增加的行列初始化为0
    	for (int i = 0; i < mygraph.curVexNum; i++) {
    		//将新增加的行列赋值为0
    		mygraph.arcs[mygraph.curVexNum - 1][i] = 0;//将行赋值为0
    		mygraph.arcs[i][mygraph.curVexNum - 1] = 0;//将列赋值为0
    	}
    
    	mygraph.vexs[mygraph.curVexNum - 1] = v;//将新顶点放入顶点集
    	cout << "插入成功！" << endl;
    	return true;
    }

##### 删除图中顶点v和与其相关的边 #####

//删除图G中顶点v及相关的边
    bool deleteVex(MyGraph &mygraph, char v) {
    	if (mygraph_isEmpty(mygraph)) {
    		return false;
    	}
    
    	int flag = 0;//判断是否找到
    
    	int count_arc = 0;//边的数目
    	
    	for (int i = 0; i < mygraph.curVexNum; i++) {
    		if (mygraph.vexs[i] == v) {
    			flag = 1;	
    			//找到了然后将他删除,需要将后面的几个节点向前移动
    			for (int j = i+1 ; j < mygraph.curVexNum; j++) {
    				mygraph.vexs[j-1] = mygraph.vexs[j];//将后面的一个节点往前移动
    			}
    			
    			//进行 行删除
    			for (int k = i+1; k < mygraph.curVexNum; k++) {
    				//将第i行后面的都向上覆盖
    				for (int x = 0; x < mygraph.curVexNum; x++) {
    					mygraph.arcs[k - 1][x] = mygraph.arcs[k][x];
    				}
    			}
    			//进行 列删除
    			for (int k = i + 1; k < mygraph.curVexNum; k++) {
    				//将第i列后面的都想左覆盖
    				for (int x = 0; x < mygraph.curVexNum; x++) {
    					mygraph.arcs[x][k - 1] = mygraph.arcs[x][k];
    				}
    			}	
    
    			//顶点数减一
    			mygraph.curVexNum--;
    			
    			//重新计算还有多少条边
    			for (int i = 0; i < mygraph.curVexNum; i++) {
    				for (int j = 0; j < mygraph.curVexNum; j++) {
    					if (mygraph.arcs[i][j] != 0) {
    						count_arc++;
    					}
    				}
    			}
    			mygraph.curArcNum = count_arc;
    			
    			cout << "此时图的顶点数为：" << mygraph.curVexNum << endl;
    			cout << "此时图额边数为" << mygraph.curArcNum << endl;
    			break;
    		}
    	}
    
    	if (flag == 0) {
    		cout << "不存在该节点，请检查" << endl;
    		return false;
    	}
    	else {
    		return true;
    	}
    }

##### 增加一条v和w之间的边 #####

bool insertArc(MyGraph &mygraph, char v, char w) {
    	//在v和w之间添加一条边
    	if (mygraph_isEmpty(mygraph)) {
    		return false;
    	}
    	//先找到v和w的下标
    	int index_v = 0;
    	int index_w = 0;
    	int flag_v = 0;
    	int flag_w = 0;
    	
    	//先进行查找是否存在v和w两个顶点
    	for (int i = 0; i < mygraph.curVexNum; i++) {
    		if (mygraph.vexs[i] == v) {
    			index_v = i;
    			flag_v = 1;
    		}
    		if (mygraph.vexs[i] == w) {
    			index_w = i;
    			flag_w = 1;
    		}
    	}
    
    	if (flag_v == 0) {
    		//说明不存在该节点
    		cout << "不存在" << v << "节点" << endl;
    		return false;
    	}
    	if (flag_w == 0) {
    		//说明不存在该节点
    		cout << "不存在" << w << "节点" << endl;
    		return false;
    	}
    	
    	int weight = 0;
    	cout << "请输入v和w的边的权值" << endl;
    	cin >> weight;
    
    	//到矩阵中进行更改
    	mygraph.arcs[index_v][index_w] = weight;
    	mygraph.curArcNum++;
    	return true;
    }

###### 删除图中 v 和 w 之间的一条边 ######

bool deleteArc(MyGraph &mygraph, char v, char w) {
    	if (mygraph_isEmpty(mygraph)) {//判断是否为空
    		return false;
    	}
    	
    	//找到下标
    	int index_v = locateVex(mygraph,v);
    	int index_w = locateVex(mygraph,w);
    
    	//在矩阵删除
    	mygraph.arcs[index_v][index_w] = de_num;
    	mygraph.curArcNum--;
    	return true;
    }

**接下来我会更新图的邻接表的实现，以及DFS和BFS的实现！**

[Link 1]: https://blog.csdn.net/qq_37134008/article/details/85325251