求有向图的度

问题描述：已知有向图G用邻接矩阵存储，设计算法以分别求解顶点vi的入度、出度和度。

【算法设计思想】

1. 出度的计算 (getOutDegree)

• 遍历法：通过遍历邻接矩阵中顶点vi所在行的所有元素来计算vi的出度。对于每个元素matrix[vi][j]，如果其值不为0（表示存在从顶点vi到顶点j的边），则出度计数增加1。
• 直观理解：顶点vi的所有出边都在其对应的行中表示，因此行遍历能准确计算出度。

2. 入度的计算 (getInDegree)

• 遍历法：通过遍历邻接矩阵中顶点vi所在列的所有元素来计算vi的入度。对于每个元素matrix[i][vi]，如果其值不为0（表示存在从顶点i到顶点vi的边），则入度计数增加1。
• 直观理解：顶点vi的所有入边都在其对应的列中表示，因此列遍历能准确计算入度。

3. 度的计算 (getDegree)

• 度的合成：顶点vi的度是其入度和出度之和。这反映了有向图中，顶点的总连接数由其入边和出边数量共同决定。

• 函数复用：通过调用getOutDegree和getInDegree函数分别计算出度和入度，然后将它们相加得到总度，这样的设计避免了重复代码，提高了代码的复用性和清晰度。

• 【算法描述】

• // 求顶点vi的出度
  int getOutDegree(int matrix[N][N], int vi) {
      int outDegree = 0;
      for (int j = 0; j < N; j++) {
          if (matrix[vi][j] != 0) {
              outDegree++;
          }
      }
      return outDegree;
  }
  
  // 求顶点vi的入度
  int getInDegree(int matrix[N][N], int vi) {
      int inDegree = 0;
      for (int i = 0; i < N; i++) {
          if (matrix[i][vi] != 0) {
              inDegree++;
          }
      }
      return inDegree;
  }
  
  // 求顶点vi的度
  int getDegree(int matrix[N][N], int vi) {
      int outDegree = getOutDegree(matrix, vi);
      int inDegree = getInDegree(matrix, vi);
      return outDegree + inDegree;
  }
  

  【测试程序】

  #include <stdio.h>
  
  #define N 5 // 假设图中有N个顶点
  
  // 函数原型声明
  int getOutDegree(int matrix[N][N], int vi);
  int getInDegree(int matrix[N][N], int vi);
  
  int main() {
      // 示例邻接矩阵
      int matrix[N][N] = {
          {0, 1, 1, 0, 0},
          {0, 0, 1, 1, 0},
          {0, 0, 0, 1, 1},
          {0, 0, 0, 0, 1},
          {1, 0, 0, 0, 0}
      };
      int vi = 2; // 指定顶点索引（从0开始计数）
  
      int outDegree = getOutDegree(matrix, vi);
      int inDegree = getInDegree(matrix, vi);
      int degree = outDegree + inDegree; // 顶点的度是入度和出度之和
  
      printf("顶点%d的出度是: %d\n", vi, outDegree);
      printf("顶点%d的入度是: %d\n", vi, inDegree);
      printf("顶点%d的度是: %d\n", vi, degree);
  
      return 0;
  }
  
  // 求顶点vi的出度
  int getOutDegree(int matrix[N][N], int vi) {
      int outDegree = 0;
      for (int j = 0; j < N; j++) {
          if (matrix[vi][j] != 0) {
              outDegree++;
          }
      }
      return outDegree;
  }
  
  // 求顶点vi的入度
  int getInDegree(int matrix[N][N], int vi) {
      int inDegree = 0;
      for (int i = 0; i < N; i++) {
          if (matrix[i][vi] != 0) {
              inDegree++;
          }
      }
      return inDegree;
  }
  
  // 求顶点vi的度
  int getDegree(int matrix[N][N], int vi) {
      int outDegree = getOutDegree(matrix, vi);
      int inDegree = getInDegree(matrix, vi);
      return outDegree + inDegree;
  }