Design your algorithm in a pseudocode! (PS: use greedy algorithm) ___________________________________________________________________________ #include #define max 6 int count = 0, countSpan = 0, cost = 0; struct ed{ int pq, zx; int value; }; ed list[max]; ed spanning[max]; int graph[max][max], n; int find(int *belong, int node) { return(belong[node]); } void sort(){ ed temp; for (int i = 1; i < count; i++) { for (int j = 0; j < count - 1; j++) { if (list[j].value > list[j+1].value) { temp = list[j]; list[j] = list[j+1]; list[j + 1] = temp; } } } } void kl(){ int belong[max], node1, node2; for(int i = 1; i < max; i++){ for(int j = 0; j < i; j++) { if(graph[i][j] != 0){ list[count].pq = i; list[count].zx = j; list[count].value = graph[i][j]; count++; } } } sort(); for(int i = 0; i < max; i++) { belong[i] = i; } for(int i = 0; i < max; i++){ node1 = find(belong, list[i].pq); node2 = find(belong, list[i].zx); if(node1 != node2){ spanning[countSpan] = list[i]; cost += spanning[countSpan].value; countSpan++; for(int i = 0; i < max; i++) { if(belong[i] == node2){ belong[i] = node1; } } } } } void print(){ printf("%d\n", cost); for (int i = 0; i < countSpan; i++){ printf("%c - %c : %d\n", spanning[i].zx+65, spanning[i].pq+65, spanning[i].value); cost = cost + spanning[i].value; } } int main() { char ot, ds; int value; for(int i = 0; i < 12; i++) { scanf("%c", &ot); getchar(); scanf("%c", &ds); getchar(); scanf("%d", &value); getchar(); list[i].value = value; graph[ot-'A'][ds-'A'] = graph[ds-65][ot-65] = value; } kl(); print(); return 0; }
Design your
___________________________________________________________________________
#include <stdio.h>
#define max 6
int count = 0, countSpan = 0, cost = 0;
struct ed{
int pq, zx;
int value;
};
ed list[max];
ed spanning[max];
int graph[max][max], n;
int find(int *belong, int node)
{
return(belong[node]);
}
void sort(){
ed temp;
for (int i = 1; i < count; i++)
{
for (int j = 0; j < count - 1; j++)
{
if (list[j].value > list[j+1].value)
{
temp = list[j];
list[j] = list[j+1];
list[j + 1] = temp;
}
}
}
}
void kl(){
int belong[max], node1, node2;
for(int i = 1; i < max; i++){
for(int j = 0; j < i; j++)
{
if(graph[i][j] != 0){
list[count].pq = i;
list[count].zx = j;
list[count].value = graph[i][j];
count++;
}
}
}
sort();
for(int i = 0; i < max; i++)
{
belong[i] = i;
}
for(int i = 0; i < max; i++){
node1 = find(belong, list[i].pq);
node2 = find(belong, list[i].zx);
if(node1 != node2){
spanning[countSpan] = list[i];
cost += spanning[countSpan].value;
countSpan++;
for(int i = 0; i < max; i++)
{
if(belong[i] == node2){
belong[i] = node1;
}
}
}
}
}
void print(){
printf("%d\n", cost);
for (int i = 0; i < countSpan; i++){
printf("%c - %c : %d\n", spanning[i].zx+65, spanning[i].pq+65, spanning[i].value);
cost = cost + spanning[i].value;
}
}
int main()
{
char ot, ds;
int value;
for(int i = 0; i < 12; i++)
{
scanf("%c", &ot);
getchar();
scanf("%c", &ds);
getchar();
scanf("%d", &value);
getchar();
list[i].value = value;
graph[ot-'A'][ds-'A'] = graph[ds-65][ot-65] = value;
}
kl();
print();
return 0;
}
Step by step
Solved in 2 steps
