邻接矩阵构造图C++实现

邻接矩阵

图类的定义

template<typename T>
class MyGraph {
public:
	MyGraph(T a[], int b[][2], int n, int e);//构造函数，初始化具有n个顶点e条边的图，b是一个e×2的二维数组，存储了边的坐标信息
	~MyGraph() { }//析构函数
	T GetVex(int i);//取图中第i个顶点数据信息
	void PutVex(int i, T value);//将图中第i个顶点的数据域置为value 
	void InsertVex(T value);//在图中插入一个顶点，值为value 
	void DeleteVex(int i);//删除图中第i个顶点
	void InsertSide(int i, int j);//在图中插入一条边，其依附的两个顶点的编号为i和j 
	void DeleteSide(int i, int j);//在图中删除一条边，其依附的两个顶点的编号为i和j 
	void PrintSide();//打印边数组
	void DFSTraverse(int v);//深度优先遍历图，从第v个节点开始
	void BFSTraverse(int v);//广度优先遍历图，从第v个节点开始
private:
	void _dfs(const vector<vector<int>>& side, vector<bool>& visit, int v);
	vector<T> vertex;//存放图中顶点的数组	
	vector< vector<int> > side;//存放图中边的数组	
	int vertexNum, sideNum;//图的顶点数和边数
};

图的初始化

初始化具有n个顶点e条边的图，b是一个e×2的二维数组，存储了边的坐标信息，例如b[][2] = { {0,1},{0,2},{0,4},{1,2},{1,3},{1,4},{2,3},{3,4} }，说明在边数组side在这些坐标里面的值都为1。这里我的图仅仅是无向图，没有提及有向图，如需变成有向图，仅需在边数组side初始化后不进行对称性赋值即可，其余地方不用变。

//构造函数
template<typename T>
MyGraph<T>::MyGraph(T a[], int b[][2], int n, int e)
{
	vertexNum = n;
	sideNum = e;
	for (int i = 0; i < n; i++)//顶点数组初始化
		vertex.push_back(a[i]);
	//side.push_back(vertexNum,vector<int>(vertexNum, 0)); 吐了，这个一会报错一会不报错
	for (int i = 0; i < vertexNum; i++)//边数组初始化为0，然后再将边数组内的坐标处的值置为1
		side.push_back(vector<int>(vertexNum, 0));
	for (int i = 0; i < sideNum; i++) {
		side.at(b[i][0]).at(b[i][1]) = 1;
		side.at(b[i][1]).at(b[i][0]) = 1;//如果需要有向图的话，将该行注释
	}
}

插入和删除图的顶点

这里使用的vector数组进行了插入和删除

//在图中插入一个顶点，值为value 
template<typename T>
void MyGraph<T>::InsertVex(T value)
{
	vertex.push_back(value);
	vertexNum = vertex.size();
	side.push_back(vector<int>(vertexNum, 0));//边数组添加一行元素
	for (int i = 0; i < vertexNum - 1; i++)//边数组添加一列元素
		side[i].push_back(0);
}

//删除图中第i个顶点
template<typename T>
void MyGraph<T>::DeleteVex(int i)
{
	vertex.erase(vertex.begin() + i);
	vertexNum = vertex.size();
	side.erase(side.begin() + i);//边数组删除该行元素
	for (int j = 0; j < vertexNum; j++)//边数组删除该列元素
		side[j].erase(side[j].begin() + i);
}

深度优先遍历

类似二叉树的前序遍历，唯一不同的是这里多了一个visit数组，用来记录顶点是否被访问过，防止重复访问，如果不是很懂，建议再看看二叉树前序遍历的实现，伪代码如下：

//深度优先遍历图，从第v个节点开始
template<typename T>
void MyGraph<T>::DFSTraverse(int v)
{
	vector<bool> visit(vertexNum, false);
	_dfs(side, visit, v);
}

template<typename T>
void MyGraph<T>::_dfs(const vector<vector<int>>& side, vector<bool>& visit, int v)
{
	cout << vertex.at(v) << " ";
	visit.at(v) = true;
	for (int i = 0; i < vertexNum; i++)
		if (side[v][i] == 1 && visit.at(i) == false)
			_dfs(side, visit, i);
}

广度优先遍历

其实广度优先遍历就是二叉树的层序遍历的演化，唯一不同就是加入了visit数组，防止重复访问，伪代码如下：

//广度优先遍历图，从第v个节点开始
template<typename T>
void MyGraph<T>::BFSTraverse(int v)
{
	vector<bool> visit(vertexNum, false);
	queue<int> myqueue;
	myqueue.push(v);
	visit.at(v) = true;
	while (!myqueue.empty())
	{
		int front = myqueue.front();
		cout << vertex.at(front) << " ";
		for (int i = 0; i < vertexNum; i++) {
			if (visit.at(i) == false && side[front][i] == 1) {
				myqueue.push(i);
				visit.at(i) = true;
			}
		}
		myqueue.pop();
	}
}

全部代码

mygraph.h

#pragma once
#ifndef MYGRAPH_H
#define MAGRAPH_H
#include<iostream>
#include<vector>
#include<queue>
using std::cout;
using std::endl;
using std::vector;
using std::queue;

template<typename T>
class MyGraph {
public:
	MyGraph(T a[], int b[][2], int n, int e);//构造函数，初始化具有n个顶点e条边的图，b是一个e×2的二维数组，存储了边的坐标信息
	~MyGraph() { }//析构函数
	T GetVex(int i);//取图中第i个顶点数据信息
	void PutVex(int i, T value);//将图中第i个顶点的数据域置为value 
	void InsertVex(T value);//在图中插入一个顶点，值为value 
	void DeleteVex(int i);//删除图中第i个顶点
	void InsertSide(int i, int j);//在图中插入一条边，其依附的两个顶点的编号为i和j 
	void DeleteSide(int i, int j);//在图中删除一条边，其依附的两个顶点的编号为i和j 
	void PrintSide();//打印边数组
	void DFSTraverse(int v);//深度优先遍历图，从第v个节点开始
	void BFSTraverse(int v);//广度优先遍历图，从第v个节点开始
private:
	void _dfs(const vector<vector<int>>& side, vector<bool>& visit, int v);
	vector<T> vertex;//存放图中顶点的数组	
	vector< vector<int> > side;//存放图中边的数组	
	int vertexNum, sideNum;//图的顶点数和边数
};

//构造函数
template<typename T>
MyGraph<T>::MyGraph(T a[], int b[][2], int n, int e)
{
	vertexNum = n;
	sideNum = e;
	for (int i = 0; i < n; i++)//顶点数组初始化
		vertex.push_back(a[i]);
	//side.push_back(vertexNum,vector<int>(vertexNum, 0)); 吐了，这个一会报错一会不报错
	for (int i = 0; i < vertexNum; i++)//边数组初始化为0，然后再将边数组内的坐标处的值置为1
		side.push_back(vector<int>(vertexNum, 0));
	for (int i = 0; i < sideNum; i++) {
		side.at(b[i][0]).at(b[i][1]) = 1;
		side.at(b[i][1]).at(b[i][0]) = 1;//如果需要有向图的话，将该行注释
	}
}

//取图中第i个顶点数据信息
template<typename T>
T MyGraph<T>::GetVex(int i)
{
	return vertex.at(i-1);
}

//将图中第i个顶点的数据域置为value 
template<typename T>
void MyGraph<T>::PutVex(int i, T value)
{
	vertex.at(i - 1) = value;
}

//在图中插入一个顶点，值为value 
template<typename T>
void MyGraph<T>::InsertVex(T value)
{
	vertex.push_back(value);
	vertexNum = vertex.size();
	side.push_back(vector<int>(vertexNum, 0));//边数组添加一行元素
	for (int i = 0; i < vertexNum - 1; i++)//边数组添加一列元素
		side[i].push_back(0);
}

//删除图中第i个顶点
template<typename T>
void MyGraph<T>::DeleteVex(int i)
{
	vertex.erase(vertex.begin() + i);
	vertexNum = vertex.size();
	side.erase(side.begin() + i);//边数组删除该行元素
	for (int j = 0; j < vertexNum; j++)//边数组删除该列元素
		side[j].erase(side[j].begin() + i);
}

//在图中插入一条边，其依附的两个顶点的编号为i和j
template<typename T>
void MyGraph<T>::InsertSide(int i, int j)
{
	if (side.at(i).at(j) == 0) {
		sideNum += 1;
		side.at(i).at(j) = 1;
		side.at(j).at(i) = 1;
	}
}

//在图中删除一条边，其依附的两个顶点的编号为i和j 
template<typename T>
void MyGraph<T>::DeleteSide(int i, int j)
{
	if (side.at(j).at(i) != 0){
		sideNum -= 1;
		side.at(i).at(j) = 0;
		side.at(j).at(i) = 0;
	}
}

template<typename T>
void MyGraph<T>::PrintSide()
{
	for (int i = 0; i < vertexNum; i++) {
		for (int j = 0; j < vertexNum; j++)
			cout << side.at(i).at(j) << " ";
		cout << endl;
	}
}

//深度优先遍历图，从第v个节点开始
template<typename T>
void MyGraph<T>::DFSTraverse(int v)
{
	vector<bool> visit(vertexNum, false);
	_dfs(side, visit, v);
}

//广度优先遍历图，从第v个节点开始
template<typename T>
void MyGraph<T>::BFSTraverse(int v)
{
	vector<bool> visit(vertexNum, false);
	queue<int> myqueue;
	myqueue.push(v);
	visit.at(v) = true;
	while (!myqueue.empty())
	{
		int front = myqueue.front();
		cout << vertex.at(front) << " ";
		for (int i = 0; i < vertexNum; i++) {
			if (visit.at(i) == false && side[front][i] == 1) {
				myqueue.push(i);
				visit.at(i) = true;
			}
		}
		myqueue.pop();
	}
}

template<typename T>
void MyGraph<T>::_dfs(const vector<vector<int>>& side, vector<bool>& visit, int v)
{
	cout << vertex.at(v) << " ";
	visit.at(v) = true;
	for (int i = 0; i < vertexNum; i++)
		if (side[v][i] == 1 && visit.at(i) == false)
			_dfs(side, visit, i);
}

#endif // !MYGRAPH_H

测试代码：

#include"mygraph.h"


int main() 
{
	int b[][2] = { {0,1},{0,2},{0,4},{1,2},{1,3},{1,4},{2,3},{3,4} };//边的坐标
	char a[] = { 'A','B','C','D','E' };
	MyGraph<char> mygraph(a, b, 5, 8);
	mygraph.PrintSide();

	cout << endl;
	mygraph.BFSTraverse(0);

	cout << endl;
	mygraph.DFSTraverse(0);

	cout << endl;
	mygraph.InsertVex('F');
	mygraph.PrintSide();

	cout << endl;
	mygraph.DeleteVex(1);
	mygraph.PrintSide();
	return 1;
}

结果：