通过c++实现利用二维数组、Map或Graph类存储有向图,创建一个有向图,并完成如下操作:1. 输入:图的任意一个节点编号; 2. 输出:该节点的入度、出度、入度边邻居和出度边邻居的编号。
时间: 2024-03-11 11:47:28 浏览: 85
好的,以下是利用邻接矩阵存储有向图,并完成操作的C++代码示例:
```c++
#include <iostream>
#include <vector>
#include <map>
using namespace std;
class DirectedGraph {
private:
vector<vector<int>> adjMatrix;
public:
DirectedGraph(int numNodes) {
adjMatrix.resize(numNodes, vector<int>(numNodes, 0));
}
void addEdge(int src, int dest) {
adjMatrix[src][dest] = 1;
}
void printNodeInfo(int node) {
cout << "Node " << node << " Info:" << endl;
cout << "In-degree: " << getInDegree(node) << endl;
cout << "Out-degree: " << getOutDegree(node) << endl;
cout << "In-neighbor nodes: ";
vector<int> inNeighbors = getInNeighbors(node);
for (int i = 0; i < inNeighbors.size(); i++) {
cout << inNeighbors[i] << " ";
}
cout << endl;
cout << "Out-neighbor nodes: ";
vector<int> outNeighbors = getOutNeighbors(node);
for (int i = 0; i < outNeighbors.size(); i++) {
cout << outNeighbors[i] << " ";
}
cout << endl;
}
private:
int getInDegree(int node) {
int inDegree = 0;
for (int i = 0; i < adjMatrix.size(); i++) {
if (adjMatrix[i][node] == 1) {
inDegree++;
}
}
return inDegree;
}
int getOutDegree(int node) {
int outDegree = 0;
for (int i = 0; i < adjMatrix[node].size(); i++) {
if (adjMatrix[node][i] == 1) {
outDegree++;
}
}
return outDegree;
}
vector<int> getInNeighbors(int node) {
vector<int> inNeighbors;
for (int i = 0; i < adjMatrix.size(); i++) {
if (adjMatrix[i][node] == 1) {
inNeighbors.push_back(i);
}
}
return inNeighbors;
}
vector<int> getOutNeighbors(int node) {
vector<int> outNeighbors;
for (int i = 0; i < adjMatrix[node].size(); i++) {
if (adjMatrix[node][i] == 1) {
outNeighbors.push_back(i);
}
}
return outNeighbors;
}
};
int main() {
DirectedGraph graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
graph.printNodeInfo(2);
return 0;
}
```
在上述代码中,我们首先创建了一个`DirectedGraph`类,其中`adjMatrix`变量是一个二维向量,用于存储有向图的邻接矩阵。`addEdge`方法用于向图中添加边。`printNodeInfo`方法用于打印节点的入度、出度、入度边邻居和出度边邻居的编号。
在`getInDegree`方法中,我们遍历所有节点的入度邻接矩阵,如果邻接矩阵中对应位置为1,则目标节点的入度加1。在`getOutDegree`方法中,我们遍历目标节点的出度邻接矩阵,如果邻接矩阵中对应位置为1,则目标节点的出度加1。在`getInNeighbors`方法中,我们遍历所有节点的入度邻接矩阵,如果邻接矩阵中对应位置为1,则将当前节点加入到目标节点的入度边邻居向量中。在`getOutNeighbors`方法中,我们遍历目标节点的出度邻接矩阵,如果邻接矩阵中对应位置为1,则将该节点加入到目标节点的出度边邻居向量中。
在`main`函数中,我们创建了一个有向图,并对节点2进行了操作。你可以将上述代码复制到C++编译器中运行,查看结果。
阅读全文