从图创建邻接矩阵

Question

我正在尝试从图形文件创建邻接矩阵。

我需要读入一个包含顶点数的文本文件，然后列出图形格式

例如:

5
0 3 2
1 0 2
1 2 2
1 4 1

第一列数字是源顶点的id，第二列是目标顶点的id，第三列是边的权重

所以这应该返回矩阵

0 2 0 2 0
2 0 2 0 1
0 2 0 0 0
2 0 0 0 0
0 1 0 0 0

到目前为止，我已经阅读了文本文件并获得了顶点数，但我不确定从这里开始做什么。

我当前的代码:

#include <stdio.h>
#include <stdlib.h>

int main (){

    printf("Enter the file contianing the graph\n");

    char filename[20];
    FILE *myFile;
    scanf("%s",filename);
    myFile = fopen (filename,"r");

    int number_of_nodes, number_of_edges;
    int source_id[100], target_id[100], weight[100];
    int matrix[100][100];
    int i;      
    if (myFile == NULL){
        printf("File not found! Exiting...\n");
        return -1;
    }
    else{
        fscanf(myFile, "%d", &number_of_nodes);
        printf("There are %d vertices.\n", number_of_nodes);
        for(i = 0; i < (sizeof (source_id) / sizeof ( source_id[0] )); i++)
        {
 if( fscanf(myFile, "%d %d %d", &source_id[i], &target_id[i], &weight[i]) != 3)
           break;

        }
        number_of_edges = i;  

        for (i = 0; i<99;i++){
        for (int j = 0; j< 99; i++){
        matrix[i][j]=0;
        }
        }

        for (i = 0;  i < number_of_edges; i++){
          int x = source_id[i];
          int y = target_id[i];
          matrix[x][y] = weight[i];
          matrix[y][x] = weight[i];
          }

          for (int y = 0; y < (number_of_nodes-1); y++){
            for (int x = 0; x < (number_of_nodes -1); x++){
              printf(matrix[x][y]);
              printf(" \n");
            } 
         } 

    }


    fclose(myFile);

    return 0;
}

Answer 1

因为你只贴了读取文件的代码，我就只评论和改进这部分。

首先，您可以更好地定义变量。在下面的代码中，我删除了您的 numberArray，而是定义了一个 number_of_nodes 和三个独立的源、目标和权重数组。这使得以后更容易引用这些数据。

其次，由于您不知道文件中的项(边)数，因此您必须通过查看 fscanf() 的返回值来检查读取是否成功。它返回成功读取的元素数。在你的例子中，你一次读取 3 个数字，所以你可以将返回值与 3 进行比较。你还想在退出循环后存储 i 的值，所以你稍后会知道实际读取了多少边。

第三，使用 scanf("%s") 与使用 gets() 一样糟糕(Why is it bad?)。您可能应该考虑限制输入长度，例如使用 scanf("%19s")。我没有在下面的代码中修复它，因为它不是一个直接的问题，但应该在您以后的开发中考虑到。

最后，为您的文件打开检查 +1。在继续之前确保先前的操作已成功完成是一种很好的做法。

这是我的固定代码:

#include <stdio.h>
#include <stdlib.h>

int main() {
    printf("Enter the file contianing the graph\n");

    char filename[20];
    FILE *myFile;
    scanf("%s", filename);
    myFile = fopen(filename, "r");

    int number_of_nodes, number_of_edges;
    int source_id[100], target_id[100], weight[100];

    int i;
    if (myFile == NULL) {
        printf("File not found! Exiting...\n");
        return -1;
    }
    else {
        fscanf(myFile, "%d", &number_of_nodes);
        printf("There are %d vertices.\n", number_of_nodes);
        for (i = 0; i < (sizeof(source_id) / sizeof(source_id[0])); i++) {
            if (fscanf(myFile, " %d %d %d", &source_id[i], &target_id[i], &weight[i]) != 3)
                break;
        }
        number_of_edges = i;
    }

    fclose(myFile);

    return 0;
}

---

接下来要做什么，我会给你一些提示，而不是直接写完整的代码。如果您明白了要点，那就相对容易了。

您想创建一个“矩阵”，或者用 C 的话来说，一个数组的数组。为了简单起见，它应该看起来像这样

int matrix[100][100];

然后您可以初始化矩阵并将其重置为零:

// This is pseudo-code
for i = 0 to 99
  for j = 0 to 99
    matrix[i][j] = 0

然后根据您从文件中读取的内容，您可以将值分配给归零矩阵。记住要分配两个值(x 到 y 和 y 到 x)

for edge in edges
  x = edge.source
  y = edge.target
  matrix[x][y] = edge.weight
  matrix[y][x] = edge.weight

要打印出矩阵，只需按行遍历即可。不要忘记在每行之后打印一个换行符。

for y = 0 to (number_of_nodes - 1)
  for x = 0 to (same as above)
    print matrix[x][y] and a space
  print a newline

如果你能理解以上所有的想法，那么你就可以开始了。