请帮我用c语言把以下代码补充完整要求输入以下数据能得到期望输出：#include stdioh#include stdlibh#include stringh# define max_dis 100000typedef char vextype20;typedef struct int N E;N是顶点数E是边数 int matrix;储存邻接矩阵 vextype vertex
代码实现：
#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* visited = (int*)malloc(sizeof(int) * g.N);
memset(visited, 0, sizeof(int) * g.N);
DFS(g, 0, visited, NULL);
for (int i = 0; i < g.N; i++) {
if (visited[i] == 0) {
free(visited);
return 0;
}
}
free(visited);
return 1;
}
/**
* DFS遍历图
* @param g 图
* @param i 当前顶点的下标
* @param visited 标记数组
* @param count 连通块的顶点数，若为NULL则不统计
*/
void DFS(Graph g, int i, int* visited, int* count)
{
visited[i] = 1;
if (count != NULL) {
(*count)++;
}
for (int j = 0; j < g.N; j++) {
if (g.matrix[i][j] != max_dis && visited[j] == 0) {
DFS(g, j, visited, count);
}
}
}
/**
* 计算图的直径。提示：Floyd算法
* @param g 图
* @return 直径的长度
*/
int Diameter(Graph g) {
int** dist = (int**)malloc(sizeof(int*) * g.N);
int** path = (int**)malloc(sizeof(int*) * g.N);
for (int 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 (int i = 0; i < g.N; i++) {
for (int j = i + 1; j < g.N; j++) {
if (dist[i][j] > max) {
max = dist[i][j];
diameter_path[0] = i;
diameter_path[1] = j;
for(int k = 2; k < g.N; k++) {
diameter_path[k] = -1;
}
int p = path[i][j];
int k = 1;
while (p != j) {
diameter_path[k++] = p;
p = path[p][j];
}
diameter_path[k++] = j;
diameter_path[k++] = -1;
}
}
}
printPath(max, diameter_path, g);
for (int 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);
for (int 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 min = max_dis;
for (int i = 0; i < g.N; i++) {
int max = 0;
for (int j = 0; j < g.N; j++) {
if (dist[i][j] > max) {
max = dist[i][j];
}
}
if (max < min) {
min = max;
}
}
for (int i = 0; i < g.N; i++) {
free(dist[i]);
free(path[i]);
}
free(dist);
free(path);
return min;
}
/**
* 使用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* visited = (int*)malloc(sizeof(int) * g.N);
int* dist = (int*)malloc(sizeof(int) * g.N);
memset(visited, 0, sizeof(int) * g.N);
for (int i = 0; i < g.N; i++) {
dist[i] = g.matrix[start][i];
}
visited[start] = 1;
for (int i = 1; i < g.N; i++) {
int min = max_dis;
int next = start;
for (int j = 0; j < g.N; j++) {
if (visited[j] == 0 && dist[j] < min) {
min = dist[j];
next = j;
}
}
visited[next] = 1;
for (int j = 0; j < g.N; j++) {
if (visited[j] == 0 && g.matrix[next][j] < max_dis) {
if (dist[next] + g.matrix[next][j] < dist[j]) {
dist[j] = dist[next] + g.matrix[next][j];
path[j] = next;
}
}
}
}
int p = end;
int i = 0;
while (p != start) {
path[i++] = p;
p = path[p];
}
path[i++] = start;
int d = dist[end];
free(dist);
free(visited);
return d;
}
/**
* Floyd算法计算任意两点间的最短路径
* @param g 图
* @param dist 任意两点间的最短路径长度
* @param path 任意两点间的最短路径
*/
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] = j;
}
}
for (k = 0; k < g.N; k++) {
for (i = 0; i < g.N; i++) {
for (j = 0; j < g.N; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[i][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;
}
``
原文地址: https://www.cveoy.top/t/topic/eCOK 著作权归作者所有。请勿转载和采集!