使用存储图结构的领接表的创建算法,设计算法求顶点的入度
时间: 2024-02-24 16:00:07 浏览: 121
采用连接表存储有向图,设计算法判断任意两个顶点间是否存在路径.doc
以下是使用领接表实现的求顶点入度的算法:
1. 定义一个数组inDegree[],用于存储每个顶点的入度。
2. 遍历图中所有的边,对于每条边(u, v),将v的入度加1,即inDegree[v]++。
3. 遍历inDegree[]数组,输出指定顶点的入度。
具体实现代码如下:
```C++
void getInDegree(vector<vector<int>>& graph, int vertex) {
int n = graph.size();
int inDegree[n];
memset(inDegree, 0, sizeof(inDegree)); // 初始化所有顶点的入度为0
// 遍历所有边,更新每个顶点的入度
for (int i = 0; i < n; i++) {
for (auto v : graph[i]) {
inDegree[v]++;
}
}
// 输出指定顶点的入度
cout << "Vertex " << vertex << " has in-degree: " << inDegree[vertex] << endl;
}
```
其中,graph是一个存储图结构的领接表,vertex是指定的顶点编号。在遍历图中的边时,我们使用了一个auto循环,遍历了每个顶点的邻接表,这里需要注意的是,领接表中存储的是每个顶点的邻居列表,因此我们需要将邻居的入度加1。最后,输出指定顶点的入度即可。
阅读全文