C++ 代码实现:
cpp
include
include
include <unordered_map>
using namespace std;
int main() {
int V, E;
cin >> V >> E;
// 错误处理:顶点个数为0
if (V == 0) {
cout << "error" << endl;
return 0;
}
// 错误处理:顶点个数为1,且边个数大于0
if (V == 1 && E > 0) {
cout << "error" << endl;
return 0;
}
vector<char> vertices(V);
unordered_map<char, int> vertex_index;
// 读取顶点并建立顶点到索引的映射
for (int i = 0; i < V; ++i) {
cin >> vertices[i];
vertex_index[vertices[i]] = i;
}
// 初始化邻接矩阵
vector<vector<int>> adjMatrix(V, vector<int>(V, 0));
// 处理每条边
for (int i = 0; i < E; ++i) {
char u, v;
cin >> u >> v;
// 将边 u -> v 设为 1
adjMatrix[vertex_index[u]][vertex_index[v]] = 1;
}
// 输出邻接矩阵
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
return 0;
}
代码解析:
输入部分:
通过 cin 读取输入的顶点数 V 和边数 E。
如果 V == 0,立即输出 "error"。
如果 V == 1 且 E > 0,输出 "error"。
使用 vector
邻接矩阵初始化:
使用二维 vector 初始化邻接矩阵,所有元素默认值为 0,表示没有边。
处理每条边:
对于每条边 (u, v),通过 vertex_index 查找顶点 u 和 v 的索引,然后在邻接矩阵中对应的位置设置为 1。
输出邻接矩阵:
遍历邻接矩阵并打印。
输入输出示例:
输入:
4 4
a b c d
a b
a c
c d
d a
输出:
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
错误输入示例:
输入:
0 0
输出:
error
输入:
1 1
a
a a
输出:
error
复杂度分析:
时间复杂度:O(V^2 + E),初始化邻接矩阵的时间复杂度是 O(V^2),处理每条边的时间复杂度是 O(1),因此总体时间复杂度为 O(V^2 + E)。
空间复杂度:O(V^2),主要是由于存储邻接矩阵的空间。
总结:
该程序能够正确处理邻接矩阵的生成,确保在遇到错误的输入时能进行适当的错误提示,并且能够高效地处理正常的输入数据