广度优先遍历无权图访问到某顶点，所经过的是最短路径吗？为什么？

如果图中所有边的权重相等，那么广度优先搜索得到的路径就是最短路径。因为广度优先搜索是一层一层地遍历，当它找到目标顶点时一定是经过最少的边数到达的。也就是说，它找到的路径是最短的。

但是，如果图中存在权重不相等的边，那么广度优先搜索得到的路径不一定是最短路径。因为广度优先搜索只考虑了边的数量，而没有考虑边的权重。如果存在一条边权重很小的路径和一条边权重很大的路径，但是边数相同，那么广度优先搜索可能会选择边数相同但是权重较大的路径，这样得到的路径就不是最短的了。因此，广度优先搜索只适用于无权图或者所有边权重相等的图。

相关问题

用C语言实现用广度优先遍历求无权图的单源最短路径，要求写出详细的注释

以下是用C语言实现用广度优先遍历求无权图的单源最短路径的代码，注释已经详细说明了每一步的操作：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数

// 邻接表的定义
typedef struct node{
    int vertex; // 顶点
    struct node *next; // 指向下一个结点的指针
}Node;

typedef struct graph{
    Node *adjList[MAX_VERTEX_NUM]; // 邻接表
    int vertexNum; // 顶点数
}Graph;

// 初始化图
void initGraph(Graph *g, int vertexNum){
    g->vertexNum = vertexNum;
    int i;
    for(i = 0; i < g->vertexNum; i++){
        g->adjList[i] = NULL; // 所有结点初始化为空
    }
}

// 添加边
void addEdge(Graph *g, int u, int v){
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = g->adjList[u];
    g->adjList[u] = newNode;

    // 如果是无向图，还需要反向添加一条边
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = u;
    newNode->next = g->adjList[v];
    g->adjList[v] = newNode;
}

// 广度优先遍历
void bfs(Graph *g, int start, int *dist){
    int visited[MAX_VERTEX_NUM] = {0}; // 标记结点是否被访问过
    int queue[MAX_VERTEX_NUM]; // 队列
    int front = 0, rear = 0; // 队头和队尾指针
    visited[start] = 1; // 标记起点已经访问过
    queue[rear++] = start; // 将起点入队
    dist[start] = 0; // 起点到自己的距离为0

    while(front != rear){ // 队列不为空
        int u = queue[front++]; // 取出队头元素
        Node *p = g->adjList[u];
        while(p != NULL){ // 遍历u的所有邻接点
            int v = p->vertex;
            if(!visited[v]){ // 如果v没有访问过
                visited[v] = 1; // 标记v已经访问过
                queue[rear++] = v; // 将v入队
                dist[v] = dist[u] + 1; // 更新v到起点的距离
            }
            p = p->next; // 访问下一个邻接点
        }
    }
}

int main(){
    Graph g;
    initGraph(&g, 6); // 初始化一个有6个顶点的图
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 3);
    addEdge(&g, 2, 4);
    addEdge(&g, 3, 5);
    addEdge(&g, 4, 5);

    int dist[MAX_VERTEX_NUM]; // 存储各个顶点到起点的距离
    int start = 0; // 起点为0
    bfs(&g, start, dist);

    int i;
    for(i = 0; i < g.vertexNum; i++){
        printf("Vertex %d: distance = %d\n", i, dist[i]);
    }

    return 0;
}

在这个示例代码中，我们初始化了一个有6个顶点的无向图，并添加了一些边。我们通过广度优先遍历算法求出了从起点0到各个顶点的最短距离，并打印出来。

图的遍历 --- 广度优先遍历算法

广度优先遍历算法（BFS）是一种用于图的遍历的算法。它从图的某个顶点开始，首先访问这个顶点，然后依次访问其相邻的未被访问过的顶点，再依次访问这些顶点的相邻未被访问过的顶点，以此类推，直到所有顶点都被访问过为止。

BFS 通常使用队列来实现。具体步骤如下：

1. 将起始顶点入队列，并将其标记为已访问。
2. 从队列中取出一个顶点，并访问它。
3. 将该顶点的所有未被访问过的邻接顶点入队列，并将它们标记为已访问。
4. 重复步骤2和步骤3，直到队列为空。

这样，BFS 可以保证从起始顶点开始，按照距离递增的顺序访问所有可达的顶点。

需要注意的是，BFS 适用于无权图或者权值都相同的图。对于带有权值的图，需要使用其他算法，比如 Dijkstra 算法或者 A* 算法。

希望这个解答对你有帮助！如果你有其他问题，请随时提问。