repl.it
@candh/

Prims ALgo

C

https://www.dyclassroom.com/graph/prim-algorithm-finding-minimum-spanning-tree

fork
loading
Files
  • main.c
main.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
/*
taken from:
https://www.dyclassroom.com/graph/prim-algorithm-finding-minimum-spanning-tree
*/

/* 
	my notes:
	doesn't work on complex graphs (can't handle if we've visited a node before and goes into an infinite loop)
	TODO: err handling
*/

/**
 * file: prim.c
 * author: yusuf shakeel
 * date: 2014-03-02
 *
 * description: find MST using prim's algorithm
 *
 * vertices are represented using numbers.
 * vertex A becomes 0
 * vertex B becomes 1
 * and so on...
 */

#include <stdio.h>
/**
 * contant to represent infinity
 * it is assumed that edges of the graph will have weight less than this value
 */
#define INF 9999

/**
 * total number of vertices in the graph
 */
#define V 4

/**
 * this function will display the MST
 */
void displayMST(int graph[V][V], int markedCell[V][V]) {
  
  int r, c;

  for (r = 0; r < V-1; r++) {
    for (c = r+1; c < V; c++) {
      if(markedCell[r][c]) {
        printf("Edge: %d -- %d\tWeight: %d\n", r, c, graph[r][c]);
      }
    }
  }

}

/**
 * prim&aposs algorithm function
 */
void prim(int graph[V][V]) {
  //variables
  int i, r, c,
    solved = 0,
    count = 0,
    min,
    expectedR,
    expectedC;

  /**
   * this array holds the marked cells in the graph
   */
  int markedCell[V][V] = {{0}};

  /**
   * this array holds the marked vertices
   * 0 = unmarked
   * 1 = marked
   */
  int markedVertex[V] = {0};
  markedVertex[0] = 1;

  
  /**
   * find MST
   */
  while(!solved) {

    min = INF;
    count = 0;
    expectedR = -1;
    expectedC = -1;

    /**
     * find minimum weight from marked vertex
     *
     * note!
     * graph[][] is a square matrix
     * diagonal elements of the graph[][] are zeros
     * and elements on either sides are same
     * example: element graph[1][0] is same as graph[0][1]
     * so, we will check only one side of the diagonal
     */
    for (r = 0; r < V; r++) {

      if (markedVertex[r] == 1) {

        for (c = r; c < V; c++) {

          if (graph[r][c] != 0 && graph[r][c] < min && !markedCell[r][c]) {

            min = graph[r][c];
            expectedR = r;
            expectedC = c;

          }

        }

      }

    }

    /**
     * mark the newly found vertex for MST
     */
    if (expectedR != -1 && expectedC != -1) {
      markedCell[expectedR][expectedC] = 1;
      markedCell[expectedC][expectedR] = 1;
      markedVertex[expectedR] = 1;
      markedVertex[expectedC] = 1;
    }

    /**
     * check if the graph is solved
     */
    for (i = 0; i < V; i++) {
      if (markedVertex[i]) {
        count++;
      }
    }
    if (count == V) {
      solved = 1;
    }

  }

  displayMST(graph, markedCell);

}

/**
 * this is the main function
 */
int main(void) {
  // int graph[V][V] = {
  //   {0, INF, 16, INF, 15, INF, 14, INF, 13},
  //   {INF, 0, 12, INF, INF, INF, INF, INF, 10},
  //   {16, 12, 0, 1, 2, INF, INF, INF, 11},
	// 	{INF, INF, 1, 0, 3, INF, INF, INF, INF},
	// 	{15, INF, 2, 3, 0, 4, 5, INF, INF},
	// 	{INF, INF, INF, INF, 4, 0, 6, INF, INF},
	// 	{14, INF, INF, INF, 5, 6, 0, 7, 8},
	// 	{INF, INF, INF, INF, INF, INF, 7, 0, 9},
	// 	{13, 10, 11, INF, INF, INF, 8, 9, 0}
  // };

	int graph[V][V] = {
    {0, 5, 10, INF},
    {5, 0, 4, 11},
    {10, 4, 0, 5},
    {INF, 11, 5, 0}
  };

  /**
   * find MST using prim
   */
  prim(graph);

  return 0;
}
Fetching token
?