OJ刷題記錄：圖的鄰接表示法驗證程式

無向圖的鄰接矩陣表示法驗證程式 題目編號:515

題目描述：
采用鄰接矩陣表示無向圖，完成圖的創建、圖的深度優先遍歷、圖的廣度優先遍歷操作，其中圖的頂點資訊是字符型，圖中頂點序號按字符順序排列，本輸入樣例中所用的圖如下所示：

輸入描述
第一行輸入兩個值，第一個是圖中頂點的個數，第二個是圖中邊的條數
第二行輸入各頂點的資訊，即輸入每個頂點字符
第三行開始輸入每條邊，每條邊的形式為兩個頂點的序號，中間以空格隔開，輸入完一條邊換行
輸出描述
首先輸出圖的頂點資訊，輸出完畢換行
接著輸出圖的鄰接矩陣，假如圖中有n個頂點，則輸出形式為n行n列的鄰接矩陣，輸出完畢換行
接下來一行輸出從圖的第一個頂點開始進行深度優先遍歷的序列，中間以空格隔開，輸出完畢換行
最后一行輸出從圖的第一個頂點開始進行廣度優先遍歷的序列，中間以空格隔開，輸出完畢換行
輸入樣例
5 7
A B C D E
0 1
0 2
0 3
1 2
1 3
2 4
3 4
輸出樣例
A B C D E
0 1 1 1 0
1 0 1 1 0
1 1 0 0 1
1 1 0 0 1
0 0 1 1 0
A B C E D
A B C D E

解題思路：
坑點：輸入的圖可能含有多個連通分量，所以僅僅從一個頂點出發搜索可能不能完成所有頂點的遍歷，需要依次對所有頂點進行搜索（每次以當前頂點為起點搜索），

通關代碼：

#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;
}

有向圖的鄰接表表示法驗證程式 題目編號:516

題目描述：
用鄰接表表示有向圖，完成圖的創建、圖的深度優先遍歷、圖的廣度優先遍歷操作，其中圖的頂點資訊是字符型，圖中頂點序號按字符順序排列，邊的輸入按照邊的頂點序號從小到大的順序排列，如下圖的邊的輸入順序為0 1，0 2，0 3，1 2，1 3，2 4，3 4共七條邊，鄰接表的邊結點采用頭插法，本輸入樣例中所用的圖如下所示：

輸入描述

第一行輸入兩個值，第一個是圖中頂點的個數，第二個是圖中邊的條數
第二行輸入各頂點的資訊，即輸入每個頂點字符
第三行開始輸入每條邊，每條邊的形式為兩個頂點的序號，中間以空格隔開，輸入完一條邊換行

輸出描述

首先輸出圖的頂點資訊，輸出完畢換行
接著輸出圖的鄰接表，格式為首先輸出第一個頂點，接著輸出該頂點的所有的臨界點的序號，換行，然后輸出下一個頂點及鄰接點，以此類推
接下來一行輸出從圖的第一個頂點開始進行深度優先遍歷的序列，中間以空格隔開，輸出完畢換行
最后一行輸出從圖的第一個頂點開始進行廣度優先遍歷的序列，中間以空格隔開，輸出完畢換行

輸入樣例

5 7
A B C D E
0 1
0 2
0 3
1 2
1 3
2 4
3 4

輸出樣例

A B C D E
A 3 2 1
B 3 2
C 4
D 4
E
A D E C B
A D C B E

解題思路：
同上，

通關代碼：

#include <iostream>
#include <queue>

#define MAXSIZE 100

using namespace std;

int visited[MAXSIZE] = {0};

struct eNode {
	int _edge;
	eNode* _next;
	eNode(int edge):_edge(edge), _next(NULL) {}
};

struct vNode {
	char _vertex;
	eNode* _first;
	vNode():_first(NULL) {}
	vNode(char vertex):_vertex(vertex), _first(NULL) {}
};

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

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

	private:
		vNode vertexArr_[MAXSIZE];
		int vNum_;
		int eNum_;
};

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

	char ch;
	int x, y;

	for (int i = 0; i < vNum; i++) {
		cin >> ch;
		vNode temp(ch);
		vertexArr_[i] = temp;
	}

	for (int i = 0; i < eNum; i++) {
		cin >> x >> y;
		eNode* temp = new eNode(y);
		temp->_next = vertexArr_[x]._first;
		vertexArr_[x]._first = temp;
	}
}

Graph::~Graph() {
	for (int i = 0; i < vNum_; i++) {
		eNode* temp;
		for (eNode* p = vertexArr_[i]._first; p != NULL; p = temp) {
			temp = p->_next;
			delete p;
		}
	}
}

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

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

void Graph::printMGraph() {
	for (int i = 0; i < vNum_; i++) {
		cout << vertexArr_[i]._vertex << ' ';
		for (eNode* p = vertexArr_[i]._first; p != NULL; p = p->_next) {
			cout << p->_edge << ' ';
		}
		cout << endl;
	}
}

void Graph::DFS(int origin) {
	cout << vertexArr_[origin]._vertex << ' ';
	visited[origin] = 1;

	for (eNode* p = vertexArr_[origin]._first; p != NULL; p = p->_next) {
		if (visited[p->_edge] == 0) {
			DFS(p->_edge);
		}
	}
}

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

	cout << vertexArr_[origin]._vertex << ' ';
	visited[origin] = 1;
	q.push(origin);

	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (eNode* p = vertexArr_[v]._first; p != NULL; p = p->_next) {
			if (visited[p->_edge] == 0) {
				cout << vertexArr_[p->_edge]._vertex << ' ';
				visited[p->_edge] = 1;
				q.push(p->_edge);
			}
		}
	}
	
}

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;
}