C语言中如何求邻接矩阵中某一个顶点的最远邻接点
时间: 2024-03-25 14:39:48 浏览: 23
C语言中求邻接矩阵中某一个顶点的最远邻接点,同样可以采用广度优先搜索(BFS)的方法实现。具体步骤与C++类似,以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 100
int adj[MAX_N][MAX_N]; // 邻接矩阵
int dist[MAX_N]; // 到起点的距离
int bfs(int n, int v)
{
memset(dist, -1, sizeof(dist)); // 初始化
int queue[MAX_N];
int front = 0, rear = 0;
queue[rear++] = v;
dist[v] = 0;
while (front < rear)
{
int u = queue[front++];
for (int i = 0; i < n; i++)
{
if (adj[u][i] && dist[i] == -1) // i 与 u 相邻且未被访问过
{
queue[rear++] = i;
dist[i] = dist[u] + 1;
}
}
}
int max_dist = -1;
for (int i = 0; i < n; i++)
{
if (dist[i] > max_dist)
{
max_dist = dist[i];
}
}
return max_dist;
}
int main()
{
int n, v;
scanf("%d%d", &n, &v);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &adj[i][j]);
}
}
int max_dist = bfs(n, v);
printf("%d\n", max_dist);
return 0;
}
```
需要注意的是,C语言中没有STL库,因此需要手动实现队列。上述代码中使用了数组来模拟队列。