C语言无向图校园导航

在C语言中，实现无向图的校园导航功能可以使用邻接表（Adjacency List）数据结构来存储地图信息，因为这种结构对于表示稀疏图（如校园地图，通常不会每个节点都与其他所有节点相连）更为高效。以下是一个简单的概述：

1. **定义图结构**：
- 创建一个节点结构（Node），包含节点编号和指向相邻节点的指针数组。
- 创建一个图结构（Graph），包含顶点数量和指向每个节点的指针。

2. **构建图**：
- 使用数组或链表为每个校园区域（或建筑物）创建节点，并连接相应的边（路径）。
- 可以使用哈希或邻接矩阵（对密集图更合适，但不适用于校园导航这样稀疏的情况）来查找邻居，但这里我们只用邻接表。

3. **搜索算法**：
- 为了实现导航，你可以使用广度优先搜索（BFS）或深度优先搜索（DFS）。BFS适合找到最短路径，而DFS适用于寻找路径。
- 用户输入起点和终点，从起点开始遍历图，直到找到终点或确定没有路径。

4. **示例代码**：
- 编写函数来添加节点、连接边、执行搜索等操作。
- 使用控制台输入输出显示路径信息。

5. **用户界面**：
- 如果是命令行交互，可以提示用户输入起点和终点；如果是图形用户界面（GUI），可以设计一个简单的菜单或地图视图。

相关问题：
1. 在C语言中，如何表示图的邻接表结构？
2. 选择BFS还是DFS搜索时，应考虑哪些因素？
3. 如何处理用户输入并找到两个节点之间的路径？

相关问题

1）地图实现功能：设计校园平面图，展示校园中所有地点。2）地点查询功能：为来访客人提供图中任意景点相关信息的查询。3）导航功能：为来访客人提供途中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。3）导航功能：为来访客人提供途中任意两个景点的所有路线查询，即查询任意两个景点之间的所有路径。4）导航功能（多点导航）：实现多个景点之间的访问路线查询，即查询路过多个景点的一条最短的简单路径。界面要求：有合理的提示，打印出学校所有景点在线地图一览，设计主控菜单（例如西安工商学院导游咨询系统菜单栏），根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计相应的存储结构。但要求至少使用基本数据结构图、栈、队列中的两种，请在最后的上交资料中指明用到的存储结构及结构类型定义代码；测试数据：进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。C语言

该系统可以使用图来实现，每个景点可以看作图中的一个节点，每条路径可以看作图中的一条边。可以使用邻接表来存储图。

具体实现：

1. 定义结构体表示图中的节点（景点）和边（路径）：

// 表示图中的节点
typedef struct node {
    int id; // 节点的唯一标识符
    char name[50]; // 节点名称
    char info[100]; // 节点信息，如景点介绍、开放时间等
} Node;

// 表示图中的边
typedef struct edge {
    int start; // 起点节点的id
    int end; // 终点节点的id
    int weight; // 权重，即路径长度或花费等
} Edge;

2. 定义邻接表结构体表示整个图：

typedef struct graph {
    Node* nodes; // 所有节点构成的数组
    int numNodes; // 节点的数量
    Edge* edges; // 所有边构成的数组
    int numEdges; // 边的数量
    int** adjMatrix; // 邻接矩阵，用于实现最短路径算法
} Graph;

3. 实现校园平面图的初始化函数，读取节点和边的信息并存储在邻接表中：

void initGraph(Graph* graph, char* nodeFile, char* edgeFile) {
    // 读取节点信息
    FILE* fp = fopen(nodeFile, "r");
    fscanf(fp, "%d", &(graph->numNodes)); // 第一行为节点数量
    graph->nodes = (Node*) malloc(graph->numNodes * sizeof(Node));
    for (int i = 0; i < graph->numNodes; i++) {
        fscanf(fp, "%d %s %[^\n]", &(graph->nodes[i].id), graph->nodes[i].name, graph->nodes[i].info);
    }
    fclose(fp);

    // 读取边信息
    fp = fopen(edgeFile, "r");
    fscanf(fp, "%d", &(graph->numEdges)); // 第一行为边数量
    graph->edges = (Edge*) malloc(graph->numEdges * sizeof(Edge));
    graph->adjMatrix = (int**) malloc(graph->numNodes * sizeof(int*));
    for (int i = 0; i < graph->numNodes; i++) {
        graph->adjMatrix[i] = (int*) malloc(graph->numNodes * sizeof(int));
        for (int j = 0; j < graph->numNodes; j++) {
            graph->adjMatrix[i][j] = -1; // 初始化为-1，表示不连通
        }
    }
    for (int i = 0; i < graph->numEdges; i++) {
        fscanf(fp, "%d %d %d", &(graph->edges[i].start), &(graph->edges[i].end), &(graph->edges[i].weight));
        // 将边的信息存储到邻接矩阵中
        graph->adjMatrix[graph->edges[i].start][graph->edges[i].end] = graph->edges[i].weight;
        graph->adjMatrix[graph->edges[i].end][graph->edges[i].start] = graph->edges[i].weight; // 无向图，需要存储两次
    }
    fclose(fp);
}

4. 实现地点查询功能，根据节点名称查找对应节点的信息：

void searchNode(Graph* graph, char* nodeName) {
    int found = 0;
    for (int i = 0; i < graph->numNodes; i++) {
        if (strcmp(graph->nodes[i].name, nodeName) == 0) {
            printf("节点名称：%s\n", graph->nodes[i].name);
            printf("节点信息：%s\n", graph->nodes[i].info);
            found = 1;
            break;
        }
    }
    if (!found) {
        printf("未找到该节点\n");
    }
}

5. 实现最短路径算法，使用Dijkstra算法或Floyd算法都可以：

void dijkstra(Graph* graph, int start, int end, int* path, int* len) {
    int* dist = (int*) malloc(graph->numNodes * sizeof(int));
    int* visited = (int*) calloc(graph->numNodes, sizeof(int));
    for (int i = 0; i < graph->numNodes; i++) {
        dist[i] = -1; // 初始化为-1，表示不连通
    }
    dist[start] = 0;
    visited[start] = 1;
    for (int i = 0; i < graph->numNodes - 1; i++) {
        for (int j = 0; j < graph->numNodes; j++) {
            if (visited[j]) {
                for (int k = 0; k < graph->numNodes; k++) {
                    if (graph->adjMatrix[j][k] != -1 && !visited[k]) {
                        if (dist[k] == -1 || dist[k] > dist[j] + graph->adjMatrix[j][k]) {
                            dist[k] = dist[j] + graph->adjMatrix[j][k];
                            path[k] = j;
                        }
                    }
                }
            }
        }
        int minDist = -1;
        int minNode = -1;
        for (int j = 0; j < graph->numNodes; j++) {
            if (!visited[j] && dist[j] != -1) {
                if (minDist == -1 || dist[j] < minDist) {
                    minDist = dist[j];
                    minNode = j;
                }
            }
        }
        if (minNode != -1) {
            visited[minNode] = 1;
        } else {
            break;
        }
    }
    *len = dist[end];
    free(dist);
    free(visited);
}

void floyd(Graph* graph, int start, int end, int* path, int* len) {
    int** dist = (int**) malloc(graph->numNodes * sizeof(int*));
    for (int i = 0; i < graph->numNodes; i++) {
        dist[i] = (int*) malloc(graph->numNodes * sizeof(int));
        for (int j = 0; j < graph->numNodes; j++) {
            if (graph->adjMatrix[i][j] != -1) {
                dist[i][j] = graph->adjMatrix[i][j];
            } else {
                dist[i][j] = INT_MAX;
            }
        }
    }
    for (int k = 0; k < graph->numNodes; k++) {
        for (int i = 0; i < graph->numNodes; i++) {
            for (int j = 0; j < graph->numNodes; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i * graph->numNodes + j] = k;
                }
            }
        }
    }
    *len = dist[start][end];
    for (int k = path[start * graph->numNodes + end]; k != -1; k = path[start * graph->numNodes + k]) {
        path[*len] = k;
        (*len)++;
    }
    free(dist);
}

6. 实现单点导航功能，查询两个节点之间的最短路径：

void navigate(Graph* graph, char* startNode, char* endNode) {
    int start = -1, end = -1;
    for (int i = 0; i < graph->numNodes; i++) {
        if (strcmp(graph->nodes[i].name, startNode) == 0) {
            start = i;
        }
        if (strcmp(graph->nodes[i].name, endNode) == 0) {
            end = i;
        }
        if (start != -1 && end != -1) {
            break;
        }
    }
    if (start == -1 || end == -1) {
        printf("起点或终点不存在\n");
        return;
    }
    int* path = (int*) malloc(graph->numNodes * sizeof(int));
    int len;
    dijkstra(graph, start, end, path, &len);
    if (len == -1) {
        printf("起点与终点不连通\n");
    } else {
        printf("最短路径长度为：%d\n", len);
        printf("最短路径为：");
        for (int i = len - 1; i >= 0; i--) {
            printf("%s", graph->nodes[path[i]].name);
            if (i != 0) {
                printf(" -> ");
            }
        }
        printf("\n");
    }
    free(path);
}

7. 实现多点导航功能，查询经过多个节点的最短路径：

void multiNavigate(Graph* graph, char** nodes, int numNodes) {
    int* nodeIds = (int*) malloc(numNodes * sizeof(int));
    for (int i = 0; i < numNodes; i++) {
        int found = 0;
        for (int j = 0; j < graph->numNodes; j++) {
            if (strcmp(graph->nodes[j].name, nodes[i]) == 0) {
                nodeIds[i] = j;
                found = 1;
                break;
            }
        }
        if (!found) {
            printf("节点 %s 不存在\n", nodes[i]);
            free(nodeIds);
            return;
        }
    }
    int* path = (int*) malloc(graph->numNodes * sizeof(int));
    int len;
    int minLen = INT_MAX;
    int* minPath = (int*) malloc(graph->numNodes * sizeof(int));
    for (int i = 0; i < numNodes - 1; i++) {
        for (int j = i + 1; j < numNodes; j++) {
            dijkstra(graph, nodeIds[i], nodeIds[j], path, &len);
            if (len != -1 && len < minLen) {
                minLen = len;
                memcpy(minPath, path, graph->numNodes * sizeof(int));
            }
        }
    }
    if (minLen == INT_MAX) {
        printf("所选节点之间均不连通\n");
    } else {
        printf("最短路径长度为：%d\n", minLen);
        printf("最短路径为：");
        int cur = nodeIds[0];
        printf("%s", graph->nodes[cur].name);
        for (int i = 0; i < minLen; i++) {
            cur = minPath[cur];
            printf(" -> %s", graph->nodes[cur].name);
        }
        printf("\n");
    }
    free(nodeIds);
    free(path);
    free(minPath);
}

8. 实现主控菜单和测试数据。