C语言实现六度空间理论
时间: 2023-08-20 19:30:13 浏览: 89
以下是使用 C 语言实现六度空间理论的示例代码:
```c
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAX_NODE 100
#define MAX_EDGE 1000
#define INF 0x3f3f3f3f
// 定义图的邻接表表示法
typedef struct {
int to; // 邻居节点的编号
int next; // 指向下一个邻居节点的边的编号
} Edge;
Edge edges[MAX_EDGE]; // 存储边的数组
int head[MAX_NODE]; // 存储每个节点的第一条边的编号
int edgeCount = 0; // 记录边的数量
// 添加一条边
void addEdge(int from, int to) {
edges[edgeCount].to = to;
edges[edgeCount].next = head[from];
head[from] = edgeCount++;
}
// 广度优先搜索函数
int bfs(int start, int end) {
int queue[MAX_NODE]; // 存储队列
int front = 0, rear = 0; // 队头和队尾
int visited[MAX_NODE]; // 记录每个节点是否被访问过
int distance[MAX_NODE]; // 记录从起点到每个节点的距离
memset(visited, 0, sizeof(visited));
memset(distance, INF, sizeof(distance));
queue[rear++] = start;
visited[start] = true;
distance[start] = 0;
while (front < rear) {
int node = queue[front++];
if (node == end) {
// 如果找到了终点,返回距离
return distance[end];
}
// 遍历当前节点的所有邻居节点
for (int i = head[node]; i != -1; i = edges[i].next) {
int neighbor = edges[i].to;
if (!visited[neighbor]) {
// 如果邻居节点未被访问过,将其加入队列
visited[neighbor] = true;
queue[rear++] = neighbor;
// 更新邻居节点的距离
distance[neighbor] = distance[node] + 1;
}
}
}
// 如果没有找到终点,返回 -1
return -1;
}
int main() {
// 初始化图
memset(head, -1, sizeof(head));
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
addEdge(a, b);
addEdge(b, a);
}
// 测试代码
int start = 1, end = n;
int distance = bfs(start, end);
if (distance >= 0 && distance <= 5) {
printf("两个节点之间的距离为 %d,符合六度空间理论\n", distance);
} else {
printf("两个节点之间的距离为 %d,不符合六度空间理论\n", distance);
}
return 0;
}
```
在上面的示例代码中,我们使用 C 语言的数组来实现邻接表表示法,使用 `addEdge` 函数来添加一条边。`bfs` 函数使用队列来实现广度优先搜索,用 `visited` 数组来记录每个节点是否被访问过,用 `distance` 数组来记录从起点到每个节点的距离。主函数中,我们读入图的节点数和边数,然后使用 `addEdge` 函数来添加边。接着,我们设定起点和终点,调用 `bfs` 函数来查找它们之间的最短距离,判断是否符合六度空间理论。