OJ刷题记录：无向图的邻接矩阵表示法验证程序 题目编号:515

#include <iostream>
#include <queue>

#define MAXSIZE 100

using namespace std;

int visited[MAXSIZE];

class Graph {
	public:
		Graph(int vNum, int eNum);

	public:
		void initVisited();
		void printVertex();
		void printMGraph();
		void DFS(int origin);
		void BFS(int origin);

	private:
		int vNum_;
		int eNum_;
		char vertex_[MAXSIZE];
		int MGraph_[MAXSIZE][MAXSIZE];
};

Graph::Graph(int vNum, int eNum) {
	vNum_ = vNum;
	eNum_ = eNum;

	for (int i = 0; i < vNum; i++) {
		for (int j = 0; j < vNum; j++) {
			MGraph_[i][j] = 0;
		}
	}

	for (int i = 0; i < vNum; i++) {
		cin >> vertex_[i];
	}

	int x, y;

	for (int i = 0; i < eNum; i++) {
		cin >> x >> y;
		MGraph_[x][y] = 1;
		MGraph_[y][x] = 1;
	}
}

void Graph::initVisited() {
	for (int i = 0; i < vNum_; i++) {
		visited[i] = 0;
	}
}

void Graph::printVertex() {
	for (int i = 0; i  < vNum_; i++) {
		cout << vertex_[i] << ' ';
	}
	cout << endl;
}

void Graph::printMGraph() {
	for (int i = 0; i < vNum_; i++) {
		for (int j = 0; j < vNum_; j++) {
			cout << MGraph_[i][j] << ' ';
		}
		cout << endl;
	}
}

void Graph::DFS(int origin) {
	cout << vertex_[origin] << ' ';
	visited[origin] = 1;
	for (int i = 0; i < vNum_; i++) {
		if (MGraph_[origin][i] == 1 && visited[i] == 0) {
			DFS(i);
		}
	}
}

void Graph::BFS(int origin) {
	queue<int> q;

	cout << vertex_[origin] << ' ';
	visited[origin] = 1;

	q.push(origin);

	while (!q.empty()) {
		int v = q.front();
		q.pop();

		for (int i = 0; i < vNum_; i++) {
			if (MGraph_[v][i] == 1 && visited[i] == 0) {
				cout << vertex_[i] << ' ';
				visited[i] = 1;
				q.push(i);
			}
		}
	}
	
}

int main() {
	int vNum, eNum;

	cin >> vNum >> eNum;

	Graph img(vNum, eNum);

	img.printVertex();
	img.printMGraph();
	
	for (int i = 0; i < vNum; i++) {
		if (visited[i] == 0) {
			img.DFS(i);
		}
	}
	cout << endl;
	
	img.initVisited();
	for (int i = 0; i < vNum; i++) {
		if (visited[i] == 0) {
			img.BFS(i);
		}
	}
	cout << endl;

	return 0;
}