Results 1 to 10 of 10
Thread: K
Hybrid View
-
26th April 2010 21:18 #1Registered User
Join Date: Apr:2010
Location:
Posts: 6
K
.
#include <stdio.h>
#define N 6 /* number of vertices */
#define M 15 /* number of edges in graph */
int U[N];
/* function prototypes */
void makeset (int i);
int find (int i);
void merge (int p, int q);
int equal (int p, int q);
void initial (int n);
void test_univ (void);
void pause (void); /* used mainly for test purposes */
/* function definitions */
int main()
{ int W[N][N] = {0,2,4,1,3,2, /* weighted graph */
2,0,6,4,5,1,
4,6,0,4,2,1,
1,4,4,0,5,4,
3,5,2,5,0,6,
2,1,1,4,6,0};
int E[M][3]; /* complete set of edges */
int F[N-1][3]; /* set of edges in min. span. tree */
int num_edges = 0; /* num of edges in min. span. tree */
int next_edge = 0; /* next edge not yet considered */
int weight = 0; /* minimal spanning tree weight */
int a, b, c, i, j, k; /* counter/placeholder variables */
/* initialize set of edges */
k = 0;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (j > i)
{ E[k][0] = i; /* first vertex of edge */
E[k][1] = j; /* second vertex of edge */
E[k][2] = W[i][j]; /* weight of edge */
k++;
}
/* display set of edges - before sort */
for (i = 0; i < M; i++)
{ for (j = 0; j < 3; j++)
printf(" %3d", E[i][j]);
printf("\n");
}
pause();
/* sort set of edges in non-decreasing order by weight - bubblesort */
for (i = M - 1; i > 0; i--)
for (j = 0; j < i; j++)
if (E[j][2] > E[j+1][2])
{ a = E[j][0];
b = E[j][1];
c = E[j][2];
E[j][0] = E[j+1][0];
E[j][1] = E[j+1][1];
E[j][2] = E[j+1][2];
E[j+1][0] = a;
E[j+1][1] = b;
E[j+1][2] = c;
}
/* display set of edges - after sort */
for (i = 0; i < M; i++)
{ for (j = 0; j < 3; j++)
printf(" %3d", E[i][j]);
printf("\n");
}
/* create n disjoint subsets */
initial (N);
/* initialize set of edges in min. span. tree to empty */
for (i = 0; i < N - 1; i++)
for (j = 0; j < 3; j++)
F[i][j] = -1; /* '-1' denotes 'empty' */
test_univ();
/* find minimal spanning tree */
while (num_edges < N - 1)
{ a = E[next_edge][0];
b = E[next_edge][1];
i = find(a);
j = find(b);
if (!equal(i, j))
{ merge (i, j);
F[num_edges][0] = E[next_edge][0];
F[num_edges][1] = E[next_edge][1];
F[num_edges][2] = E[next_edge][2];
num_edges++;
test_univ();
}
next_edge++;
}
/* display edges comprising minimal spanning tree */
printf("\nMinimal Spanning Tree Edges:\n");
printf("F = (");
for (i = 0; i < N - 1; i++)
{ printf("(V%d,V%d)", F[i][0], F[i][1]);
if (i < N - 2)
printf(", ");
weight = weight + F[i][2];
}
printf(")\n");
printf("Minimal Spanning Tree Weight = %d\n", weight);
return (0);
}
/*************** makeset() ***************/
void makeset (int i)
{ U[i] = i;
}
/*************** find() ***************/
int find (int i)
{ int j;
j = i;
while (U[j] != j)
j = U[j];
return (j);
}
/*************** merge() ***************/
void merge (int p, int q)
{ if (p < q)
U[q] = p;
else
U[p] = q;
}
/*************** equal() ***************/
int equal (int p, int q)
{ if (p == q)
return (1);
else
return (0);
}
/*************** initial() ***************/
void initial (int n)
{ int i;
for (i = 0; i < n; i++)
makeset(i);
}
/*************** test() ***************/
void test_univ (void)
/* test universe values */
{ int i;
printf("\nThe disjoint subsets are:\n");
for (i = 0; i < N; i++)
printf(" %3d", U[i]);
printf("\n");
}
/*************** pause() ***************/
void pause (void)
{ int i;
printf("Press ENTER to continue...\n");
i = getchar();
}
.
-
26th April 2010 21:41 #2
:P
? ?
-
26th April 2010 21:43 #3Registered User
Join Date: Apr:2010
Location:
Posts: 6
-
26th April 2010 22:47 #4Registered User
Join Date: Apr:2010
Location:
Posts: 6
.
-
26th April 2010 23:04 #5
-
26th April 2010 23:16 #6
, 42
Software Developer & Hrdware Lamer
-
26th April 2010 23:22 #7Registered User
Join Date: Apr:2010
Location:
Posts: 6
-
26th April 2010 23:35 #8
-
26th April 2010 23:36 #9Registered User
Join Date: Apr:2010
Location:
Posts: 6
?
-
26th April 2010 23:58 #10''? * *
- !
...





Lenovo ThinkPad 15 IdeaPad 15
5th May 2023, 22:16 in