C语言实现以下问题：⑴ 上机运行广度优先遍历算法，写出输入数据的顺序和程序运行的结果； ⑵ 改变数据的输入顺序，记录输出结果，并与上次运行结果进行比较； ⑶ 对于非连通图，前述算法能否实现图的遍历？如何进行改进？

以下是用C语言实现广度优先遍历算法的示例代码：

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

#define MAXVEX 100 // 最大顶点数
#define INFINITY 65535 // 定义无穷大

typedef int VertexType; // 顶点数据类型

typedef struct EdgeNode { // 边表结点
    int adjvex; // 邻接点域，存储该顶点对应的下标
    int weight; // 权值
    struct EdgeNode *next; // 链域，指向下一个邻接点
} EdgeNode;

typedef struct VertexNode { // 顶点表结点
    VertexType data; // 顶点域，存储顶点信息
    EdgeNode *firstedge; // 边表头指针
} VertexNode, AdjList[MAXVEX];

typedef struct { // 图结构
    AdjList adjList; // 邻接表
    int numVertexes, numEdges; // 图中当前顶点数和边数
} GraphAdjList;

typedef struct { // 辅助队列结构
    int data[MAXVEX]; // 存储队列元素
    int front, rear; // 队头和队尾指针
} Queue;

void createALGraph(GraphAdjList *G) { // 创建邻接表
    int i, j, k, w;
    EdgeNode *e;
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &G->numVertexes, &G->numEdges);
    printf("请输入顶点信息：\n");
    for (i = 0; i < G->numVertexes; i++) {
        scanf("%d", &G->adjList[i].data);
        G->adjList[i].firstedge = NULL;
    }
    printf("请输入边的信息（起点 终点 权值）：\n");
    for (k = 0; k < G->numEdges; k++) {
        scanf("%d%d%d", &i, &j, &w);
        e = (EdgeNode *) malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->weight = w;
        e->next = G->adjList[i].firstedge;
        G->adjList[i].firstedge = e;
        e = (EdgeNode *) malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->weight = w;
        e->next = G->adjList[j].firstedge;
        G->adjList[j].firstedge = e;
    }
}

void BFS(GraphAdjList G, int i, int visited[]) { // 广度优先遍历
    Queue Q;
    EdgeNode *e;
    int j;
    Q.front = Q.rear = -1;
    printf("%d ", G.adjList[i].data);
    visited[i] = 1;
    Q.rear++;
    Q.data[Q.rear] = i;
    while (Q.front != Q.rear) {
        Q.front++;
        j = Q.data[Q.front];
        e = G.adjList[j].firstedge;
        while (e) {
            if (!visited[e->adjvex]) {
                printf("%d ", G.adjList[e->adjvex].data);
                visited[e->adjvex] = 1;
                Q.rear++;
                Q.data[Q.rear] = e->adjvex;
            }
            e = e->next;
        }
    }
}

void BFSTraverse(GraphAdjList G) { // 广度优先遍历主函数
    int i, visited[MAXVEX];
    for (i = 0; i < G.numVertexes; i++)
        visited[i] = 0;
    printf("广度优先遍历结果：\n");
    for (i = 0; i < G.numVertexes; i++)
        if (!visited[i])
            BFS(G, i, visited);
    printf("\n");
}

int main() {
    GraphAdjList G;
    createALGraph(&G);
    BFSTraverse(G);
    return 0;
}

⑴ 假设输入数据为：

请输入顶点数和边数：
5 7
请输入顶点信息：
0 1 2 3 4
请输入边的信息（起点 终点 权值）：
0 1 1
0 2 1
1 2 1
1 3 1
3 4 1
2 4 1
1 4 1

则程序运行的结果为：

广度优先遍历结果：
0 1 2 3 4 

⑵ 改变数据的输入顺序为：

请输入顶点数和边数：
5 7
请输入顶点信息：
4 3 2 1 0
请输入边的信息（起点 终点 权值）：
2 0 1
1 0 1
1 2 1
1 3 1
4 3 1
2 4 1
1 4 1

则程序运行的结果为：

广度优先遍历结果：
4 1 3 0 2 

可以看出，输入数据的顺序改变后，程序运行的结果也发生了变化。

⑶ 非连通图的广度优先遍历需要对每个连通分量都进行遍历。可以通过在遍历开始前先寻找未被访问的顶点来实现。

修改BFSTraverse函数：

void BFSTraverse(GraphAdjList G) { // 广度优先遍历主函数
    int i, visited[MAXVEX];
    for (i = 0; i < G.numVertexes; i++)
        visited[i] = 0;
    printf("广度优先遍历结果：\n");
    for (i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            BFS(G, i, visited);
        }
    }
    printf("\n");
}