C语言用二维数组的邻接矩阵表示图表

可以使用一个二维数组来表示邻接矩阵。假设图中有N个节点，则定义一个N * N的二维数组来表示邻接矩阵。如果节点i和节点j之间有一条边，则邻接矩阵中的第i行第j列的元素为1，否则为0。

以下是一个C语言实现的例子：

#include <stdio.h>

#define MAX_NODES 100

int adjMatrix[MAX_NODES][MAX_NODES];

int main() {
    int n, m;
    scanf("%d %d", &n, &m); // 输入节点数和边数
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b); // 输入边的两个节点
        adjMatrix[a][b] = 1; // 标记邻接矩阵中对应位置为1
        adjMatrix[b][a] = 1;
    }

    // 输出邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

在这个例子中，我们首先输入了节点数和边数，然后逐个输入边的两个节点，并标记邻接矩阵中对应位置为1。最后输出整个邻接矩阵。

相关问题

c语言编写：1.分别用蛮力法和分治法求解最近对问题 2.输人是平面上的N个点，输出是最近点对距离。 3.要求随机生成N个点的平面坐标。 4.分别对N=100，1000，3000，统计算法运行时间（微秒），分析算法的时间性能（提高）。

在C语言中，我们可以使用蛮力法（也称为暴力搜索）和分治法（如K-d树或最短路径算法）来解决最近点对问题。以下是简要描述：

1. **蛮力法**（Brute Force）：
- 输入：N个二维坐标 (x, y)
- 算法步骤：
a. 创建一个邻接矩阵或者一个包含所有点对距离的数组。
b. 遍历所有可能的点对，计算它们之间的欧几里得距离。
c. 找到最小的距离作为结果。
- 时间复杂度：O(N^2)，空间复杂度：O(N)

2. **分治法（例如K-d树）**：
- 输入：N个二维坐标
- K-d树是一种数据结构，用于快速查找最近邻。
- 算法步骤：
a. 构建K-d树，将点按照一个维度划分成两个子集。
b. 对每个子集递归地构建K-d树，然后找到当前子集中的最近点。
c. 比较这两个最近点之间的距离与已知最近距离。
- 时间复杂度：取决于实现细节，通常较低，接近O(log N)或O(N log N)。
- 空间复杂度：O(N)

为了实现这个需求：
- **随机生成N个点**：可以使用`srand(time(0))`初始化随机数种子，并通过`rand()`函数生成随机整数范围内的值，然后设置为坐标。

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

int generate_random(int min, int max) {
    return min + rand() % (max - min + 1);
}

void random_points(int N, double points[][2]) {
    srand(time(NULL));
    for (int i = 0; i < N; ++i) {
        points[i][0] = generate_random(0, MAX_X);
        points[i][1] = generate_random(0, MAX_Y);
    }
}

- **计算时间性能**：

   #include <sys/time.h> // For time measurement
   ...
   struct timeval start, end;
   long diff;

   gettimeofday(&start, NULL); // Start timer
   ... // Call your algorithm here (brute_force or kdtree)
   gettimeofday(&end, NULL); // Stop timer
   diff = (end.tv_sec - start.tv_sec) * 1000000L + end.tv_usec - start.tv_usec;
   printf("Algorithm runtime: %ld microseconds\n", diff);

对于N的不同值（100、1000、3000），你可以分别测量并记录下来，然后绘制图表比较算法在不同规模下的效率提升，通常随着N增大，分治法的优势会更明显。