c++算法int DegreeDifferent ( Graph& G, int i )求有向图Vi 的出度和入度的差

您好！感谢您的提问！根据您的问题，我可以给出以下的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相连的顶点，增加入度计数器。最后返回出度和入度的差即可。

希望这个算法可以帮到您，如果您还有其他问题，请随时提出！

相关问题

采用邻接矩阵和邻接表对有向图进行出度和入度的计算。并实现深度和广度的遍历

好的,我很乐意为您介绍如何使用邻接矩阵和邻接表计算有向图的出度和入度,并实现深度优先和广度优先遍历。

1. 邻接矩阵:
- 出度: 邻接矩阵中第i行元素之和
- 入度: 邻接矩阵中第i列元素之和

2. 邻接表:
- 出度: 每个顶点对应的链表长度
- 入度: 遍历所有链表,统计指向该顶点的边数

3. 深度优先遍历(DFS):
使用栈或递归实现。从起始顶点开始,访问其第一个邻接顶点,然后递归访问该邻接顶点的第一个未被访问的邻接顶点,直到所有顶点都被访问。

4. 广度优先遍历(BFS):
使用队列实现。从起始顶点开始,将所有邻接顶点入队,然后依次访问队列中的顶点,每访问一个顶点就将其未被访问的邻接顶点入队。

下面是一个Python实现的示例:

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.adj_list = defaultdict(list)
        self.adj_matrix = []
        self.vertices = set()
    
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.vertices.update([u, v])
    
    def build_adj_matrix(self):
        self.adj_matrix = [[0] * len(self.vertices) for _ in self.vertices]
        vertex_index = {v: i for i, v in enumerate(self.vertices)}
        for u in self.adj_list:
            for v in self.adj_list[u]:
                self.adj_matrix[vertex_index[u]][vertex_index[v]] = 1
    
    def calculate_degrees(self):
        in_degree = {v: 0 for v in self.vertices}
        out_degree = {v: 0 for v in self.vertices}
        
        for u in self.adj_list:
            out_degree[u] = len(self.adj_list[u])
            for v in self.adj_list[u]:
                in_degree[v] += 1
        
        return in_degree, out_degree
    
    def dfs(self, start):
        visited = set()
        result = []
        
        def dfs_util(v):
            visited.add(v)
            result.append(v)
            for neighbor in self.adj_list[v]:
                if neighbor not in visited:
                    dfs_util(neighbor)
        
        dfs_util(start)
        return result
    
    def bfs(self, start):
        visited = set()
        queue = deque([start])
        result = []
        
        while queue:
            v = queue.popleft()
            if v not in visited:
                visited.add(v)
                result.append(v)
                for neighbor in self.adj_list[v]:
                    if neighbor not in visited:
                        queue.append(neighbor)
        
        return result

# 使用示例
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

g.build_adj_matrix()
in_degree, out_degree = g.calculate_degrees()
print("In-degree:", in_degree)
print("Out-degree:", out_degree)

print("DFS:", g.dfs(2))
print("BFS:", g.bfs(2))

这个实现包含了邻接表和邻接矩阵的构建,以及出度和入度的计算。同时也实现了深度优先搜索(DFS)和广度优先搜索(BFS)算法。

数据结构 C+＋实现 有向图的邻接表存储，并输出 顶点的出度和入度

下面是一个简单的 C++ 实现，使用邻接表存储有向图，并输出每个顶点的出度和入度：

#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