Я пишу код для реализации алгоритма Прима и строю минимальное остовное дерево, начиная с вершины 1.
Вот формат ввода:
Первая строка будет номеромслучаи.
Каждый случай начинается с количества вершин.
Предположим, я ввел такой код:
2
4
0,1,0,4
1,0,3,2
0,3,0,5
4,2,5,0
6
0,7,9,0,0,6
7,0,0,2,0,0
9,0,0,0,5,0
0,2,0,0,0,3
0,0,5,0,0,4
6,0,0,3,4,0
Это означает, что у меня есть 2 контрольных случая, и«4» означает 4 строки вершин.
Пример:
0,1,0,4
1,0,3,2
0,3,0,5
4,2,5,0
Будет так
|0||1||2||3|
0| 0 1 0 4
1| 1 0 3 2
2| 0 3 0 5
3| 4 2 5 0
от 0 до 4 нужно 4 расстояния, 2-2нужно 3 расстояния и т. д.
Первый выход был правильным, то есть
0-1 1
1-2 3
1-3 2
Но второй выход также совпадает с первым выходом, что означает неправильный
0-1 1
1-2 3
1-3 2
Вот мой код
#include <stdio.h>
#include <limits.h>
#include<stdbool.h>
// Number of vertices in the graph
#define V 100
// A utility function to find the vertex with
// minimum key value, from the set of vertices
// not yet included in MST
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
int v;
for (v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
// A utility function to print the
// constructed MST stored in parent[]
int printMST(int parent[], int n, int graph[V][V])
{
int i;
char front1;
char back2;
//printf("Edge \tWeight\n");
for (i = 1; i < V; i++)
if(graph[i][parent[i]]!=0)
{
front1 = parent[i];
front1 += 16;
back2 = i;
back2 +=16;
printf("%d-%d %d \n", parent[i], i, graph[i][parent[i]]);
}
else
break;
}
// Function to construct and print MST for
// a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
int i,count,v;
// Array to store constructed MST
int parent[V];
// Key values used to pick minimum weight edge in cut
int key[V];
// To represent set of vertices not yet included in MST
bool mstSet[V];
// Initialize all keys as INFINITE
for (i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
// Always include first 1st vertex in MST.
// Make key 0 so that this vertex is picked as first vertex.
key[0] = 0;
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (count = 0; count < V-1; count++)
{
// Pick the minimum key vertex from the
// set of vertices not yet included in MST
int u = minKey(key, mstSet);
// Add the picked vertex to the MST Set
mstSet[u] = true;
// Update key value and parent index of
// the adjacent vertices of the picked vertex.
// Consider only those vertices which are not
// yet included in MST
for (v = 0; v < V; v++)
// graph[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
// print the constructed MST
printMST(parent, V, graph);
}
int main()
{
printf("%c",one1);
int i,j,limit1,limit2;
int column_a=0;
int row_a=0;
char datawithco[1000];
char *pch;
int graph[V][V];
scanf("%d",&limit1);
for(i=0; i<limit1; i++)
{
scanf("%d",&limit2);
for(j=0; j<limit2; j++)
{
scanf("%s",datawithco);
pch = strtok (datawithco,",");
while (pch != NULL)
{
//printf ("%s\n",pch);
graph[row_a][column_a] = atoi(pch);
column_a++;
pch = strtok (NULL, ",");
}
column_a=0;
row_a++;
}
primMST(graph);
graph[row_a][column_a] = '\0';
}
return 0;
}
Второй вывод должен быть
0-5 6
5-3 3
3-1 2
5-4 4
4-2 5