c - C中的Prim算法产生不正确的输出
问题描述
我的任务是实现 Prim 的算法,使用邻接矩阵来表示图形,并使用结构来保存 MCST。该程序接受文件输入,应用算法,然后输出最小成本生成树。我让程序接受文件输入并产生输出,但我得到的值不正确,对我来说看起来像虚拟值。
我的假设是错误发生在我将文件输入存储在数组中的方式或算法本身中。我花了 12-15 个小时来解决这个问题,希望有人能提供见解。该程序是用 C 语言编写的,并使用 make 格式编译./a6 <file>
。我将文件输入存储在我的 main() 中,然后按调用顺序使用这些方法。下面是我的教授提供的一个例子。第一行包含有关正在输入的顶点的信息,其余行包含实际数据本身。
input:
6 10 0 <<--(size, edges, start)
0 1 16 <<--(from, to, weight)
0 5 21
0 4 19
1 2 5
1 3 6
1 5 11
2 3 10
3 4 18
3 5 14
4 5 33
output:
0 1 16 <<--(first edge)
1 2 5
1 3 6
1 5 11
3 4 18
total cost: 56
我的代码:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> /* for INT_MAX */
#define N 10 /* max matrix size is 10 x 10 */
#define INF 9999
int cost = 0;
typedef struct lnode {
int fromv;
int tov;
int weight;
struct lnode *next;
} lnode;
int insertnode(lnode **lst, int from, int to, int wt);
void prims(int amtrx[][N],int n, lnode **lst);
void printpaths(lnode **lst);
void freelist(lnode **lst);
int isValid(int a, int b, int select[]);
int insertnode(lnode **lst, int from, int to, int wt){
lnode *newnode;
newnode = (lnode *) malloc(sizeof(struct lnode));
newnode->fromv = from;
newnode->tov = to;
newnode->weight = wt;
newnode->next=NULL;
if(*lst == NULL){
newnode -> next = *lst;
*lst = newnode;
} else {
lnode *current;
current = *lst;
while(current->next != NULL){
current = current->next;
}
newnode->next = current->next;
current->next = newnode;
}
return 1;
}
int isValid(int a, int b, int select[]){
if(a == b) return 0;
if(select[a] == 0 && select[b] == 0) return 0;
else if (select[a] == 1 && select[b] == 1) return 0;
return 1;
}
void prims(int amtrx[][N], int n, lnode **lst){
int i, j, row, col, edges_seen, min;
int select[N] = {0};
edges_seen = 0;
select[n] = 1;
while(edges_seen < N-1){
min = INF;
row = -1;
col = -1;
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++){
if(amtrx[i][j] < min) {
if(isValid(i, j, select) == 1){
min = amtrx[i][j];
row = i;
col = j;
}
}
}
}
if(row != -1 && col != -1){
select[col] = 1;
select[row] = 1;
cost = cost + min;
insertnode(lst, row, col, min);
edges_seen++;
}
for(i = 0; i < N; i++){
printf("%3d", select[i]);
}
puts("\n\n");
}
}
void printpaths(lnode **lst){
lnode *current;
current = *lst;
while(current != NULL) {
printf("%4i ",current->fromv);
printf("%4i ", current->tov);
printf("%4i \n", current->weight);
current = current->next;
}
printf("\ntotal cost: %4i\n", cost);
}
void freelist(lnode **lst) {
lnode *temp = NULL;
while(*lst != NULL)
{
temp = *lst;
*lst = (*lst)->next;
free(temp);
}
}
int main(int argc, char **argv){
FILE *f = fopen(argv[1], "r");
lnode *lst;
lst = (lnode *)malloc(sizeof(struct lnode));
int i, j, nsz, nedg, fr, to, vtx, wt;
vtx = 1111;
nedg = 999;
nsz = 100;
fscanf(f, "%d %d %d", &nsz, &nedg, &vtx);
int amtrx[nsz][N];
for(i = 0; i < nsz; i++){
for(j = 0; j < nsz; j++){
amtrx[i][j] = INF;
}
}
for(i = 0; i < nedg; i++){
fscanf(f, "%d %d %d", &fr, &to, &wt);
amtrx[fr][to] = wt;
amtrx[to][fr] = wt;
}
fclose(f);
prims(amtrx, vtx, &lst);
printpaths(&lst);
freelist(&lst);
return EXIT_SUCCESS;
}
解决方案
推荐阅读
- flutter - 如何禁用 Flutter web 上的上下文菜单?(右键单击,触摸按下)
- java - Java 套接字重定向
- blazor - 无法再读取 ParameterView 实例,因为它已过期。ParameterView 只能同步读取,不能存储
- javascript - NoScript 插件:“必需的主机”提示?
- bash - CAT 忽略换行符
- reactjs - 如何在handleSubmit 中打开一个对话框?
- java - 在 Android Studio 中构建项目
- javascript - Webpack 开发中间件用于登录和主应用程序的单独页面
- html2pdf - 如何处理对于 Html2Pdf 中的页面来说太长的表格单元格
- oracle - Oracle:在游标声明中使用自定义函数