C语言实现车站路线图连通性、最短路径、直径和半径计算

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

#define max_dis 100000

typedef char vextype[20];

typedef struct { int N, E;// N是顶点数，E是边数 int **matrix;// 储存邻接矩阵 vextype *vertex;// 存储节点的名字 } Graph;

Graph createGraph(int n); int isConnected(Graph g); int Diameter(Graph g); int Radius(Graph g); int dijkstra(Graph g, int start, int end, int *path); void printPath(int d, int *diameter_path, Graph g); void DFS(Graph g, int i, int *visited, int *count); int DFSTraverse(Graph g); void floyd(Graph g, int **dist, int **path);

/**

创建一个节点数为n的图
@param n 节点个数
@return 返回这个图 */ Graph createGraph(int n) { int i, j; Graph g; g.N = n; g.matrix = (int **)malloc(sizeof(int *) * g.N); for (i = 0; i < n; i++) { g.matrix[i] = (int *)malloc(sizeof(int) * g.N); } for (i = 0; i < g.N; i++) { for (j = 0; j < g.N; j++) { g.matrix[i][j] = max_dis; } } for (i = 0; i < g.N; i++) { g.matrix[i][i] = 0; } g.vertex = (vextype *)malloc(sizeof(vextype) * g.N); return g; }

/**

根据距离d和路径数组path输出路径，这样就不需要路径的节点数也能正确输出路径
@param d 路径长度
@param diameter_path 储存路径的数组
@param g 图 */ void printPath(int d, int *diameter_path, Graph g) { int k = 0; int path_length = 0; printf("Path: "); do { printf("%s->", g.vertex[diameter_path[k]]); path_length += g.matrix[diameter_path[k]][diameter_path[k + 1]]; k++; } while (path_length < d); printf("%s\n", g.vertex[diameter_path[k]]); }

/**

判断图是否连通
@param g 图
@return 连通返回1，否则返回0 */ int isConnected(Graph g) { int count = 0; int *visited = (int *)malloc(sizeof(int) * g.N); memset(visited, 0, sizeof(int) * g.N); DFS(g, 0, visited, &count); free(visited); return count == g.N; }

/**

使用dijkstra算法计算单源最短路径
@param g 图
@param start 起点
@param end 终点
@param path 从start到end的路径, [start,...,end]
@return 路径长度 */ int dijkstra(Graph g, int start, int end, int *path) { int i, j, k, min; int *dis = (int *)malloc(sizeof(int) * g.N); int *visited = (int *)malloc(sizeof(int) * g.N); for (i = 0; i < g.N; i++) { dis[i] = g.matrix[start][i]; visited[i] = 0; if (dis[i] < max_dis) { path[i] = start; } else { path[i] = -1; } } dis[start] = 0; visited[start] = 1; for (i = 1; i < g.N; i++) { min = max_dis; k = -1; for (j = 0; j < g.N; j++) { if (!visited[j] && dis[j] < min) { min = dis[j]; k = j; } } if (k == -1) { break; } visited[k] = 1; for (j = 0; j < g.N; j++) { if (!visited[j] && g.matrix[k][j] < max_dis) { if (dis[j] > dis[k] + g.matrix[k][j]) { dis[j] = dis[k] + g.matrix[k][j]; path[j] = k; } } } } int d = dis[end]; free(dis); free(visited); return d; }

/**

计算图的直径。提示：Floyd算法
@param g 图
@return 直径的长度 */ int Diameter(Graph g) { int **dist = (int **)malloc(sizeof(int *) * g.N); int **path = (int **)malloc(sizeof(int *) * g.N); int i, j, k; for (i = 0; i < g.N; i++) { dist[i] = (int *)malloc(sizeof(int) * g.N); path[i] = (int *)malloc(sizeof(int) * g.N); } floyd(g, dist, path); int max = 0; int *diameter_path = (int *)malloc(sizeof(int) * g.N); for (i = 0; i < g.N - 1; i++) { for (j = i + 1; j < g.N; j++) { if (dist[i][j] > max) { max = dist[i][j]; diameter_path[0] = i; k = 1; while (path[diameter_path[k - 1]][j] != j) { diameter_path[k] = path[diameter_path[k - 1]][j]; k++; } diameter_path[k] = j; } } } printf("diameter path: "); for (i = 0; i <= k; i++) { printf("%s->", g.vertex[diameter_path[i]]); } printf("length:%d\n", max); for (i = 0; i < g.N; i++) { free(dist[i]); free(path[i]); } free(dist); free(path); free(diameter_path); return max; }

/**

计算图的半径
@param g 图
@return 半径长度 */ int Radius(Graph g) { int **dist = (int **)malloc(sizeof(int *) * g.N); int **path = (int **)malloc(sizeof(int *) * g.N); int i, j; for (i = 0; i < g.N; i++) { dist[i] = (int *)malloc(sizeof(int) * g.N); path[i] = (int *)malloc(sizeof(int) * g.N); } floyd(g, dist, path); int radius = max_dis; for (i = 0; i < g.N; i++) { int e = 0; for (j = 0; j < g.N; j++) { if (dist[i][j] > e) { e = dist[i][j]; } } if (e < radius) { radius = e; } } for (i = 0; i < g.N; i++) { free(dist[i]); free(path[i]); } free(dist); free(path); return radius; }

/**

深度优先搜索遍历
@param g 图
@param i 当前搜索的节点
@param visited 记录节点是否被访问过的标志数组
@param count 记录已经访问的节点数 */ void DFS(Graph g, int i, int *visited, int *count) { visited[i] = 1; (*count)++; int j; for (j = 0; j < g.N; j++) { if (!visited[j] && g.matrix[i][j] < max_dis) { DFS(g, j, visited, count); } } }

/**

深度优先搜索遍历整个图
@param g 图
@return 被访问的节点数 */ int DFSTraverse(Graph g) { int count = 0; int *visited = (int *)malloc(sizeof(int) * g.N); memset(visited, 0, sizeof(int) * g.N); DFS(g, 0, visited, &count); free(visited); return count; }

/**

Floyd算法
@param g 图
@param dist dist[i][j]是节点i到节点j的最短距离
@param path path[i][j]是节点i到节点j的最短路径上节点j的前一个节点 */ void floyd(Graph g, int **dist, int **path) { int i, j, k; for (i = 0; i < g.N; i++) { for (j = 0; j < g.N; j++) { dist[i][j] = g.matrix[i][j]; path[i][j] = -1; } } for (k = 0; k < g.N; k++) { for (i = 0; i < g.N; i++) { for (j = 0; j < g.N; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; path[i][j] = k; } } } } }

int main() { int node_num; int edge_num;

scanf("%d %d", &node_num, &edge_num);

Graph g = createGraph(node_num);
for (int i = 0; i < node_num; i++) {
    sprintf(g.vertex[i], "%d", i);
}
for (int i = 0; i < edge_num; i++) {
    int start_idx, end_idx, weight;
    scanf("%d %d %d", &start_idx, &end_idx, &weight);
    g.matrix[start_idx][end_idx] = weight;
    g.matrix[end_idx][start_idx] = weight;
}
printf("connected: %d\n", isConnected(g));

if (isConnected(g)) {
    int *short_path = (int *)malloc(sizeof(int) * g.N);
    int dis = dijkstra(g, 1, 3, short_path);
    printf("the minimum fare between 1 and 3: %d\n", dis);
    printPath(dis, short_path, g);
    free(short_path);
    int d = Diameter(g);
    printf("diameter:%d\n", d);
    int r = Radius(g);
    printf("radius:%d\n", r);
}

return 0;

}