图的邻接矩阵表示c++

时间:2024-03-31 22:48:27
#include<iostream>
#include<queue>
using namespace std;
enum graphtype { undigraph, digraph, undinetwork, dinetwork };//枚举
template<class T>
struct edgetype
{
	T head, tail;
	int cost;
	edgetype(T h, T t, int c)
	{
		head = h;
		tail = t;
		cost = c;
	}
};
template<class T>
class graph//图的邻接矩阵表示
{
private:
	int vexnum, edgenum;//顶点数,边数;
	graphtype kind;//图的类型
	int **edges;//邻接矩阵
	T *vexs;//顶点表
	void DFS(int v, bool *visited);//连通分量的深度优先遍历
public:
	graph(graphtype t, T v[], int n, int e);//解释见定义处
	~graph() {}
	int VertexNum();//返回图中的顶点数量
	int EdgeNum();//返回边的数量
	void DFSTreverse();//深度优先遍历
	void BFSTreverse();//广度优先遍历
	void printEdges();//遍历邻接矩阵
	void pringVexs();//遍历顶点表
};
template<class T>
graph<T>::graph(graphtype t, T v[], int n, int e)//t表示图的类型,v为储存各顶点值的数组,参数n和e分别为顶点数和边数
{
	vexnum = n;
	edgenum = e;
	kind = t;
	vexs = new T[vexnum];//调整数组大小
	for (int i = 0; i < n; i++)//赋值
		vexs[i] = v[i];
	edges = new int*[vexnum];//以下为边的二维数组创建
	for (int i = 0; i < n; i++)
	{
		edges[i] = new int[vexnum];
		for (int j = 0; j < n; j++)
			edges[i][j] = 0;//网图邻接矩阵对角线元素为0
	}
	for (int i = 0; i < e; i++)
	{
		int va, vb;
		int w;
		cout << "请输入每条边的两个端点的序号和边的权值" << endl;
		cin >> va >> vb;//输入一条边的两个端点的序号和边的权值
		cin >> w;
		edges[va][vb] = edges[vb][va] = w;//无向图网
	}
}
template<class T>
void graph<T>::DFS(int v, bool *visited)//递归深度优先
{
	cout << vexs[v];//访问第v个顶点
	visited[v] = true;//标记已访问
	for (int i = 0; i < vexnum; i++)
		if (edges[v][i] == 1 && !visited[i])
			DFS(i, visited);
}
template<class T>
void graph<T>::DFSTreverse()
{
	cout << "深度优先搜索结果为:";
	bool *visited = new bool[vexnum];
	for (int v = 0; v < vexnum; v++)
		visited[v] = false;
	for (int v = 0; v < vexnum; v++)
		if (!visited[v])
			DFS(v, visited);
	delete[] visited;
	cout << endl;
}
template<class T>
void graph<T>::BFSTreverse()
{
	cout << "广度优先搜索结果:";
	queue<int> seq;//构造seq队列长度为10
	bool *visited = new bool[vexnum];
	for (int i = 0; i < vexnum; i++)
		visited[i] = false;
	for (int i = 0; i < vexnum; i++)
	{
		if (!visited[i])
		{
			cout << vexs[i];
			visited[i] = true;
		}
		seq.push(i);
		while (!seq.empty())
		{
			int u = seq.front();
			seq.pop();
			for (int j = 0; j < vexnum; j++)
			{
				if (edges[u][i] == 1 && !visited[j])
				{
					cout << vexs[j];
					visited[j] = true;
					seq.push(j);
				}
			}
		}
	}
	delete[] visited;
	cout << endl;
}
template<class T>
void graph<T>::pringVexs()
{
	cout << "顶点表为:";
	for (int i = 0; i < vexnum; i++)
		cout << vexs[i] << " ";
	cout << endl;
}
template<class T>
void graph<T>::printEdges()
{
	cout << "邻接矩阵为:" << endl;
	for (int i = 0; i < vexnum; i++)
	{
		for (int j = 0; j < vexnum; j++)
			cout << edges[i][j] << " ";
		cout << endl;
	}
	cout << endl;
}
int main()
{
	char t[7] = { 'a','b','c','d','e','f','g' };
	graph<char> test(undigraph, t, 7, 7);
	test.DFSTreverse();
	test.BFSTreverse();
	test.pringVexs();
	test.printEdges();
	system("pause");
	return 0;
}

测试结果:
图的邻接矩阵表示c++

相关文章