#include <stdio.h> #include <malloc.h> #define MAXV 6 #define INF 9999 typedef struct { int no; char info; } VertexType; typedef struct { int edges[MAXV][MAXV]; int n, e; VertexType vexs[MAXV]; } MatGraph; void CreateMat(MatGraph* g, int A[MAXV][MAXV], int n, int e) { int i, j; g->n = n; g->e = e; for (i = 0; i < g->n; i++) for (j = 0; j < g->n; j++) g->edges[i][j] = A[i][j]; } void DispMat(MatGraph g) { int i, j; for (i = 0; i < g.n; i++) { for (j = 0; j < g.n; j++) if (g.edges[i][j] != INF) printf("%4d", g.edges[i][j]); else printf("%4s", ""); printf("\n"); } } int Prim(MatGraph g, int v) { int lowcost[MAXV], min, n = g.n, sum = 0; int closest[MAXV], i, j, k; for (i = 0; i < n; i++) { lowcost[i] = g.edges[v][i]; closest[i] = v; } lowcost[v] = 0; for (i = 1; i < n; i++) { min = INF; for (j = 0; j < n; j++) if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; k = j; } printf("%d-%d距离为：%d\n", closest[k] + 1, k + 1, min); sum += min; lowcost[k] = 0; for (j = 0; j < n; j++) if (g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j]) { lowcost[j] = g.edges[k][j]; closest[j] = k; } } return sum; } int main() { int k; MatGraph g; int A[MAXV][MAXV] = { {0, 6, 1, 5, INF, INF}, {6, 0, 5, INF, 3, INF}, {1, 5, 0, 5, 6, 4}, {5, INF, 5, 0, INF, 2}, {INF, 3, 6, INF, 0, 6}, {INF, INF, 4, 2, 6, 0} }; int n = 6, e = 10; CreateMat(&g, A, n, e); printf("城市连接图的邻接矩阵:\n"); DispMat(g); printf("求解结果：\n"); k = Prim(g, 0); printf("总最短距离为：%d\n", k); return 0; }改错

代码中存在以下问题：

1. 使用了未定义的宏INF。应该在头文件中定义INF，例如： #define INF 9999。

2. 在 CreateMat 函数中，应该使用参数e来初始化 g->e，而不是使用常量值10。应该修改为： g->e = e;

3. 在 DispMat 函数中，当 g.edges[i][j]为INF时，应该输出一个空格，而不是四个空格。应该修改为： printf(" ");

4. 在 Prim 函数中，应该将距离最短的点的下标k加1后输出，而不是直接输出k。应该修改为： printf("%d-%d距离为：%d\n", closest[k] + 1, k + 1, min);

修改后的代码如下：

相关问题

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <malloc.h> #define MAXV 1000 #define ElemType int #define INF 32767typedef struct { int no; int info; }VertexType; typedef struct{ int edges[MAXV][MAXV]; int n,e; VertexType vexs[MAXV]; }

MGraph;

void CreateMGraph(MGraph *G)
{
int i,j,k,w;
printf("请输入顶点数和边数：\n");
scanf("%d,%d",&(G->n),&(G->e));
for(i=0;i<G->n;i++)
{
printf("请输入第%d个顶点的编号和信息：\n",i+1);
scanf("%d,%d",&(G->vexs[i].no),&(G->vexs[i].info));
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=INF;
for(k=0;k<G->e;k++)
{
printf("请输入一条边的起点、终点和权值：\n");
scanf("%d,%d,%d",&i,&j,&w);
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}

void ShortestPath_Dijkstra(MGraph G,int v0,int *D,int *P)
{
int final[MAXV];
int i,j,k,min;
for(i=0;i<G.n;i++)
{
final[i]=0;
D[i]=G.edges[v0][i];
P[i]=0;
}
D[v0]=0;
final[v0]=1;
for(i=1;i<G.n;i++)
{
min=INF;
for(j=0;j<G.n;j++)
if(!final[j]&&D[j]<min)
{
k=j;
min=D[j];
}
final[k]=1;
for(j=0;j<G.n;j++)
if(!final[j] && (min+G.edges[k][j]<D[j]))
{
D[j]=min+G.edges[k][j];
P[j]=k;
}
}
}

void DisplayResult(MGraph G,int v0,int *D,int *P)
{
int i,j,k;
printf("起点为%d的最短路径如下：\n",v0);
for(i=0;i<G.n;i++)
{
if(i!=v0)
{
printf("从%d到%d的最短路径长度为：%d，路径为：",v0,i,D[i]);
j=i;
while(P[j]!=0)
{
printf("%d<-",G.vexs[j].no);
j=P[j];
}
printf("%d\n",G.vexs[j].no);
}
}
}

int main()
{
MGraph G;
int v0=0;
int D[MAXV],P[MAXV];
CreateMGraph(&G);
ShortestPath_Dijkstra(G,v0,D,P);
DisplayResult(G,v0,D,P);
return 0;
}

#include "graph.h" #include <stdio.h> #include <stdlib.h> void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表 { int i,j; ArcNode *p; G=(AdjGraph *)malloc(sizeof(AdjGraph)); for(i=0;i<n;i++)

这是一个创建图的邻接表的函数实现，其中AdjGraph是图的邻接表结构体，定义如下：

#define MAXV 100   // 最大顶点数
typedef struct ArcNode{   // 边结点
    int adjvex;           // 邻接点
    struct ArcNode *next; // 指向下一个邻接点的指针
}ArcNode;
typedef struct VNode{     // 顶点结点
    int data;             // 顶点的数据
    ArcNode *first;       // 指向第一个邻接点的指针
}VNode, AdjList[MAXV];
typedef struct{           // 邻接表
    AdjList vertices;     // 存放顶点的数组
    int vexnum, arcnum;   // 顶点数和边数
}AdjGraph;

下面是CreateAdj函数的实现：

void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
{
    int i, j;
    ArcNode *p;
    G = (AdjGraph *)malloc(sizeof(AdjGraph));  // 分配内存空间
    for(i = 0; i < n; i++)
    {
        G->vertices[i].data = i;  // 初始化顶点的数据
        G->vertices[i].first = NULL;  // 初始化指向第一个邻接点的指针
        for(j = 0; j < n; j++)
        {
            if(A[i][j] != 0)  // 如果顶点i和顶点j之间有边
            {
                p = (ArcNode *)malloc(sizeof(ArcNode));  // 创建边结点
                p->adjvex = j;  // 邻接点为j
                p->next = G->vertices[i].first;  // 将该边结点插入到顶点i的邻接表头部
                G->vertices[i].first = p;
            }
        }
    }
    G->vexnum = n;  // 顶点数为n
    G->arcnum = e;  // 边数为e
}

其中，A[MAXV][MAXV]是一个邻接矩阵，n是顶点数，e是边数。函数的作用是将邻接矩阵转换为邻接表存储法。