Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

并查集处理错误 #11

Open
DormancyWang opened this issue Jan 16, 2022 · 0 comments
Open

并查集处理错误 #11

DormancyWang opened this issue Jan 16, 2022 · 0 comments

Comments

@DormancyWang
Copy link

在kruscal 算法当中 博客写的是 “终点”这个不好理解的概念 其实完全是博主坑爹自己创造的判断条件,此处应该使用并查集来确定是否成环。

在代码中 博主写的是 vends[m]=n; 这个语句也不符合博主 ”终点“ 的定义,应该先判断m,n大小
if(m<n) swap(m,n)
vends[m]=n;
否则会造成一个边重复出现的错误 下面是出现错误的测试用例: (出现了(0,1) (1,0))
int[] graph0 = new int[]{0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT};
int[] graph1 = new int[]{10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12};
int[] graph2 = new int[]{MAX_WEIGHT, 18, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8};
int[] graph3 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, MAX_WEIGHT, 16, 21};
int[] graph4 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT};
int[] graph5 = new int[]{11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT};
int[] graph6 = new int[]{MAX_WEIGHT, 16, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT};
int[] graph7 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT};
int[] graph8 = new int[]{MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0};

    graph.matrix[0] = graph0;
    graph.matrix[1] = graph1;
    graph.matrix[2] = graph2;
    graph.matrix[3] = graph3;
    graph.matrix[4] = graph4;
    graph.matrix[5] = graph5;
    graph.matrix[6] = graph6;
    graph.matrix[7] = graph7;
    graph.matrix[8] = graph8;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant