c++算法int DegreeDifferent ( Graph& G, int i )求有向图Vi 的出度和入度的差
时间: 2024-03-10 13:47:43 浏览: 17
您好!感谢您的提问!根据您的问题,我可以给出以下的C++算法实现:
```c++
int DegreeDifferent(Graph& G, int i) {
int in_degree = 0, out_degree = 0;
for (int j = 0; j < G.V(); j++) {
if (G.hasEdge(i, j)) {
out_degree++;
}
if (G.hasEdge(j, i)) {
in_degree++;
}
}
return out_degree - in_degree;
}
```
上述算法首先初始化入度和出度为0,然后遍历整个图,对于每个与Vi有边相连的顶点,增加出度计数器。对于每个与Vi相连的顶点,增加入度计数器。最后返回出度和入度的差即可。
希望这个算法可以帮到您,如果您还有其他问题,请随时提出!
相关问题
数据结构 C++实现 有向图的邻接表存储,并输出 顶点的出度和入度
下面是一个简单的 C++ 实现,使用邻接表存储有向图,并输出每个顶点的出度和入度:
```cpp
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int V; // 图中顶点的数量
vector<vector<int>> adj; // 邻接表
public:
// 构造函数
Graph(int V) {
this->V = V;
adj.resize(V);
}
// 添加一条从 u 到 v 的边
void addEdge(int u, int v) {
adj[u].push_back(v);
}
// 输出每个顶点的出度和入度
void printDegree() {
for (int i = 0; i < V; i++) {
int out_degree = adj[i].size(); // 出度
int in_degree = 0; // 入度
// 计算入度
for (int j = 0; j < V; j++) {
for (auto k : adj[j]) {
if (k == i) {
in_degree++;
break;
}
}
}
cout << "顶点 " << i << " 的出度为 " << out_degree << ",入度为 " << in_degree << endl;
}
}
};
int main() {
// 创建图
Graph g(5);
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(3, 4);
// 输出每个顶点的出度和入度
g.printDegree();
return 0;
}
```
输出结果如下:
```
顶点 0 的出度为 1,入度为 1
顶点 1 的出度为 1,入度为 1
顶点 2 的出度为 1,入度为 1
顶点 3 的出度为 1,入度为 0
顶点 4 的出度为 0,入度为 1
```
用c语言代码算求有向图每个顶点的入度和出度
以下是用C语言计算有向图每个顶点的入度和出度的代码示例:
```c
#include <stdio.h>
#define MAX_VERTICES 100 // 最大顶点数
// 有向图的邻接矩阵表示法
typedef struct {
int n; // 顶点数
int adj[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
} Graph;
// 计算有向图每个顶点的入度和出度
void calc_degrees(Graph* g, int* in_degrees, int* out_degrees) {
int i, j;
for (i = 0; i < g->n; i++) {
in_degrees[i] = 0; // 初始化入度为0
out_degrees[i] = 0; // 初始化出度为0
for (j = 0; j < g->n; j++) {
if (g->adj[i][j] != 0) {
out_degrees[i]++; // 计算出度
in_degrees[j]++; // 计算入度
}
}
}
}
int main() {
Graph g = {5, {{0, 1, 0, 0, 1},
{0, 0, 1, 0, 0},
{0, 0, 0, 1, 1},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0}}}; // 有向图的邻接矩阵表示法
int in_degrees[MAX_VERTICES], out_degrees[MAX_VERTICES]; // 存储每个顶点的入度和出度
int i;
calc_degrees(&g, in_degrees, out_degrees); // 计算每个顶点的入度和出度
printf("顶点\t入度\t出度\n");
for (i = 0; i < g.n; i++) {
printf("%d\t%d\t%d\n", i, in_degrees[i], out_degrees[i]);
}
return 0;
}
```
以上代码中,我们先定义了一个 `Graph` 结构体来表示有向图的邻接矩阵表示法。然后,我们通过 `calc_degrees` 函数计算每个顶点的入度和出度。最后,我们输出每个顶点的入度和出度。