写c++程序,用二维数组Map或Graph类存储有向图,并完成,输入:图任意一个结点编号;输出:该结点入度、出度,入度边领居和出度边领居的编号
时间: 2024-03-14 08:47:48 浏览: 119
好的,我可以帮助您解决这个问题。以下是C++程序的代码:
```c++
#include<iostream>
#include<vector>
using namespace std;
class Graph {
private:
vector<vector<int>> adjList;
int numVertices;
public:
Graph(int numVertices) {
this->numVertices = numVertices;
adjList.resize(numVertices);
}
void addEdge(int src, int dest) {
adjList[src].push_back(dest);
}
int getIndegree(int vertex) {
int indegree = 0;
for(int i=0; i<numVertices; i++) {
for(auto it=adjList[i].begin(); it!=adjList[i].end(); it++) {
if(*it==vertex) {
indegree++;
}
}
}
return indegree;
}
int getOutdegree(int vertex) {
return adjList[vertex].size();
}
vector<int> getInNeighbors(int vertex) {
vector<int> inNeighbors;
for(int i=0; i<numVertices; i++) {
for(auto it=adjList[i].begin(); it!=adjList[i].end(); it++) {
if(*it==vertex) {
inNeighbors.push_back(i);
}
}
}
return inNeighbors;
}
vector<int> getOutNeighbors(int vertex) {
return adjList[vertex];
}
};
int main() {
int numVertices, vertex;
cout<<"Enter the number of vertices in the graph: ";
cin>>numVertices;
Graph g(numVertices);
int src, dest;
cout<<"Enter the edges in the graph (source destination): ";
while(cin>>src>>dest) {
g.addEdge(src, dest);
}
cout<<"Enter the vertex for which you want to find the degree and neighbors: ";
cin>>vertex;
cout<<"Indegree of "<<vertex<<": "<<g.getIndegree(vertex)<<endl;
cout<<"Outdegree of "<<vertex<<": "<<g.getOutdegree(vertex)<<endl;
cout<<"In-neighbors of "<<vertex<<": ";
vector<int> inNeighbors = g.getInNeighbors(vertex);
for(auto it=inNeighbors.begin(); it!=inNeighbors.end(); it++) {
cout<<*it<<" ";
}
cout<<endl;
cout<<"Out-neighbors of "<<vertex<<": ";
vector<int> outNeighbors = g.getOutNeighbors(vertex);
for(auto it=outNeighbors.begin(); it!=outNeighbors.end(); it++) {
cout<<*it<<" ";
}
cout<<endl;
return 0;
}
```
这个程序使用了一个 `Graph` 类来存储有向图,其中 `adjList` 是一个二维向量,表示每个节点的邻居节点。`getIndegree` 函数计算给定节点的入度,`getOutdegree` 函数计算给定节点的出度,`getInNeighbors` 函数返回所有入度邻居节点的编号,`getOutNeighbors` 函数返回所有出度邻居节点的编号。
在主函数中,程序首先要求用户输入图的顶点数,然后输入每个边的源节点和目标节点。然后程序要求用户输入一个节点,计算该节点的入度、出度、入度邻居节点和出度邻居节点,并将它们输出到屏幕上。
希望这个程序能够帮到您!
阅读全文