无向图的邻接矩阵表示法验证程序 题目编号: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;
}