c语言tsp问题贪心算法

TSP问题（Traveling Salesman Problem）是一个经典的NP难问题，即给定一张有向完全图，每条边都有权值，要求从图中选择n个点组成一条回路，使得回路经过所有的n个点且总权值最小。贪心算法是TSP问题中的一种常用算法，主要思路是通过每次选择当前距离最近的未访问节点来构建路径。

在C语言中实现TSP问题的贪心算法可以分为以下几个步骤：
1. 构建图的邻接矩阵。
2. 选择起始节点，并将其标记为已访问。
3. 遍历邻接矩阵中该起始节点所在行的所有未访问节点，并选择其中距离最近的节点作为下一个访问节点，将该节点标记为已访问，并将距离加入路径长度。
4. 重复步骤3，直到所有节点都被访问过。
5. 将最后一个访问节点与起始节点相连，形成回路。

以下是一个简单的C语言代码实现TSP问题贪心算法的示例（假设有5个节点）：

#include <stdio.h>
#define N 5

int main()
{
    int graph[N][N] = {{0, 10, 15, 20, 25},
                       {10, 0, 35, 25, 20},
                       {15, 35, 0, 30, 10},
                       {20, 25, 30, 0, 15},
                       {25, 20, 10, 15, 0}};   // 邻接矩阵表示图
    int visited[N] = {0};   // 记录节点是否已经访问
    int path[N + 1] = {0};   // 记录最终路径
    int len = 0;   // 记录路径长度
    int current = 0;   // 起始节点

    visited[current] = 1;   // 标记起始节点已访问
    path = current;   // 将起始节点添加到路径中

    for (int i = 1; i < N; i++) {
        int next = -1;   // 下一个访问节点
        int min_dist = INT_MAX;   // 距离最近的节点距离

        // 遍历当前节点所在行的所有未访问节点，选择距离最近的节点作为下一个访问节点
        for (int j = 0; j < N; j++) {
            if (!visited[j] && graph[current][j] < min_dist) {
                next = j;
                min_dist = graph[current][j];
            }
        }

        visited[next] = 1;   // 标记下一个访问节点已访问
        path[i] = next;   // 将下一个访问节点添加到路径中
        len += min_dist;   // 更新路径长度
        current = next;   // 更新当前节点
    }

    path[N] = path;   // 将最后一个访问节点与起始节点相连，形成回路
    len += graph[current][path];   // 更新路径长度

    printf("Path: ");
    for (int i = 0; i < N+1; i++) {
        printf("%d ", path[i]);
    }
    printf("\nLength: %d\n", len);

    return 0;
}