Graph

图的邻接矩阵存储结构的定义、实现、输出、遍历。(未完待续)..

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

#define MAX_VERTEX_NUM 20 //最大顶点数
const int infinity = INT_MAX;//无穷大

struct ArcCell{
	int adj;//对无权图用1,0表示是否相邻，对带权图为权值类型
	char *info;//该弧的相关信息
};

struct MGraph {
	string vexs[MAX_VERTEX_NUM];//顶点表
	ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵，即边表
	int vexnum;//顶点数
	int arcnum;//边数
	int kind;//邻接矩阵存储的图的种类
};

class Graph {
	//图的数组存储表示
private:
	MGraph mgraph;
	bool visited[MAX_VERTEX_NUM] = { 0 };
public:
	int LocateVex(string u);//图存在，图中存在顶点u则返回顶点在图中的位置
	bool CreateDG();//构造有向图
	bool CreateUDG();//构造无向图
	bool CreateDN();//构造有向网
	bool CreateUDN();//构造无向网
	void DisPlay();//输出邻接矩阵
	void DFSTraverse(int v);//深度优先遍历
	void BFSTraverse(int v);//广度优先遍历
	void clearVis();//清空访问数组
};

int Graph::LocateVex(string u) {
	for (int i = 0; i < MAX_VERTEX_NUM; i++) {
		if (u == mgraph.vexs[i]) return i;
	}
	return -1;
}
//构造有向图
bool Graph::CreateDG() {
	int i, j;
	string v1, v2;
	cout << "请输入有向图的顶点个数，边的个数：";
	cin >> mgraph.vexnum >> mgraph.arcnum;
	cout << "请输入各个顶点：";
	for (i = 0; i < mgraph.vexnum; i++) cin >> mgraph.vexs[i];//构造顶点向量
	for (i = 0; i < mgraph.vexnum; i++) {
		for (j = 0; j < mgraph.vexnum; j++) {
			mgraph.arcs[i][j].adj = 0;
			mgraph.arcs[i][j].info = false;
		}
	}
	for (i = 0; i < mgraph.arcnum; i++) {//构造邻接矩阵
		cout << "请输入一条边的起点与终点：";
		cin >> v1 >> v2;
		int m = LocateVex(v1);
		int n = LocateVex(v2);
		mgraph.arcs[m][n].adj = 1;
	}
	mgraph.kind = 1;
	return true;
}
//构造无向图
bool Graph::CreateUDG() {
	int i, j;
	string v1, v2;
	cout << "请输入无向图的顶点个数，边的个数：";
	cin >> mgraph.vexnum >> mgraph.arcnum;
	cout << "请输入各个顶点：";
	for (i = 0; i < mgraph.vexnum; i++) cin >> mgraph.vexs[i];//构造顶点向量
	for (i = 0; i < mgraph.vexnum; i++) {
		for (j = 0; j < mgraph.vexnum; j++) {
			mgraph.arcs[i][j].adj = 0;
			mgraph.arcs[i][j].info = false;
		}
	}
	for (i = 0; i < mgraph.arcnum; i++) {//构造邻接矩阵
		cout << "请输入一条边依附的两个顶点：";
		cin >> v1 >> v2;
		int m = LocateVex(v1);
		int n = LocateVex(v2);
		mgraph.arcs[m][n].adj = 1;
		mgraph.arcs[n][m].adj = 1;
	}
	mgraph.kind = 2;
	return true;
}
//构造有向网
bool Graph::CreateDN() {
	int i, j;
	string v1, v2;
	cout << "请输入有向网的顶点个数，边的个数：";
	cin >> mgraph.vexnum >> mgraph.arcnum;
	cout << "请输入各个顶点：";
	for (i = 0; i < mgraph.vexnum; i++) cin >> mgraph.vexs[i];//构造顶点向量
	for (i = 0; i < mgraph.vexnum; i++) {
		for (j = 0; j < mgraph.vexnum; j++) {
			mgraph.arcs[i][j].adj = 0;
			mgraph.arcs[i][j].info = false;
		}
	}
	for (i = 0; i < mgraph.arcnum; i++) {//构造邻接矩阵
		cout << "请输入一条边的起点与终点：";
		cin >> v1 >> v2;
		int m = LocateVex(v1);
		int n = LocateVex(v2);
		cout << "请输入该边的权值：";
		cin >> mgraph.arcs[m][n].adj;
	}
	mgraph.kind = 3;
	return true;
}
//构造无向网
bool Graph::CreateUDN() {
	int i, j;
	string v1, v2;
	cout << "请输入无向网的顶点个数，边的个数：";
	cin >> mgraph.vexnum >> mgraph.arcnum;
	cout << "请输入各个顶点：";
	for (i = 0; i < mgraph.vexnum; i++) cin >> mgraph.vexs[i];//构造顶点向量
	for (i = 0; i < mgraph.vexnum; i++) {
		for (j = 0; j < mgraph.vexnum; j++) {
			mgraph.arcs[i][j].adj = 0;
			mgraph.arcs[i][j].info = false;
		}
	}
	for (i = 0; i < mgraph.arcnum; i++) {//构造邻接矩阵
		cout << "请输入一条边依附的两个顶点：";
		cin >> v1 >> v2;
		int m = LocateVex(v1);
		int n = LocateVex(v2);
		cout << "请输入该边的权值：";
		cin >> mgraph.arcs[m][n].adj;
		mgraph.arcs[n][m].adj = mgraph.arcs[m][n].adj;
	}
	mgraph.kind = 4;
	return true;
}
//输出邻接矩阵
void Graph::DisPlay() {
	cout << "图的邻接矩阵为：" << endl;
	for (int i = 0; i < mgraph.vexnum; i++) {
		for (int j = 0; j < mgraph.vexnum; j++) {
			cout << mgraph.arcs[i][j].adj << " ";
		}
		cout << endl;
	}
}

void Graph::DFSTraverse(int v) {
	cout << mgraph.vexs[v] << " ";
	visited[v] = 1;
	for (int j = 0; j < mgraph.vexnum; j++) {
		if (mgraph.arcs[v][j].adj != 0 && visited[j] == 0) DFSTraverse(j);
	}
}

void Graph::BFSTraverse(int v) {
	int front = -1, rear = -1;//初始化队列，假设队列采用顺序存储且不会发生溢出
	int Q[MAX_VERTEX_NUM];
	cout << mgraph.vexs[v] << " ";
	visited[v] = 1;
	Q[++rear] = v;//被访问顶点入队
	while (front != rear) {
		v = Q[++front];//将队头元素出队并送到v中
		for (int j = 0; j < mgraph.vexnum; j++) {
			if (mgraph.arcs[v][j].adj != 0 && visited[j] == 0) {
				cout << mgraph.vexs[j] << " ";
				visited[j] = 1;
				Q[++rear] = j;
			}
		}
	}
}

void Graph::clearVis() {
	memset(visited, 0, sizeof(visited));
}

int main() {
	Graph GA;//有向图
	GA.CreateDG();
	GA.DisPlay();
	cout << "DFS:";
	GA.DFSTraverse(0);
	GA.clearVis();
	cout << endl << "BFS:";
	GA.BFSTraverse(0);
	cout << endl;

	Graph GB;//无向图
	GB.CreateUDG();
	GB.DisPlay();
	cout << "DFS:";
	GB.DFSTraverse(0);
	GB.clearVis();
	cout << endl << "BFS:";
	GB.BFSTraverse(0);
	cout << endl;

	Graph GC;//有向网
	GC.CreateDN();
	GC.DisPlay();
	cout << "DFS:";
	GC.DFSTraverse(0);
	GC.clearVis();
	cout << endl << "BFS:";
	GC.BFSTraverse(0);
	cout << endl;

	Graph GD;//无向网
	GD.CreateUDN();
	GD.DisPlay();
	cout << "DFS:";
	GD.DFSTraverse(0);
	GD.clearVis();
	cout << endl << "BFS:";
	GD.BFSTraverse(0);
	cout << endl;
	return 0;
}