Adaptation of Mathematical ALGorithms

Kruskal's algorithm is used to find the minimal spanning tree of a graph. We work with a weighted undirected graph where  is a set of nodes,  is a set of undirected edges and  is a positive weight of any edge.

1. At the beginning of the algorithm initialize a subgraph containing all the nodes of the graph and an empty set of edges (At the termination of the algorithm the subgraph  becomes a minimum spanning tree of the graph .).
2. Sort the edges of the graph according to their weight and process them consecutively from the shortest one.
3. Check if addition of the current edge to the subgraph establishes a cycle.
   1. If not, add the edge to the subgraph .
   2. Otherwise, do not add the edge to the subgraph .
4. After processing the last edge the subgraph  becomes the minimum spanning tree of the graph .

When processing the algorithm in the standard way we work with a visual representation of a graph. When adding an edge to the subgraph  we highlight it directly in the graph (using a different color or any other means of highlighting). There is a graph  with seven nodes in Image 1 demonstrating the situation before processing the fourth edge between the nodes  and . After the first three steps of the algorithm the edges , , were added to the subgraph . The next one does not establish a cycle and therefore we can add it to the subgraph  as well.

Example 1: Weighted undirected graph 

Image 1: Weighted undirected graph , highlighting edges of the subgraph  and a currently processed edge

We cannot add the next two edges of the weight  to the subgraph  because they would both establish a cycle of the size  (tripple of the nodes or ).

To demonstrate Kruskal's algorithm we come with an Animation 2 of the computation and use a concrete weighted undirected graph.

1. Edges of a graph are organized in a table according to nodes, and a subgraph is created in another document (sheet):

The graph is converted to a table. We add labels of the nodes to the first column. All the other cells on the row for a node  are reserved for the edges coming out from  and are written as –– where  is a weight of the edge and  is the end node of the edge. We use another sheet or a separate text file:

1. to add the edges of the subgraph  consecutively.
2. to organize sets of nodes connected together by existing edges of the subgraph .

Let's take the same graph  with seven nodes illustrated in Image 2. The following two tables (see Table 1 and Table 2) demonstrate the situation after addition of the first two edges to the subgraph .

Example 2: Graph  from Image 1 converted to a table

	––	––	––
	––	––	––
		––	––
		––	––	––	––	––
		––	––
		––	––
	––	––	––

Table 1: Graph  converted to a table after addition of the first two edges ––, ––

Example 3: Subgraph  (the future minimum spanning tree)

MST – Edges:	––	––
MST – Sets of Vertices:

Table 2: Subgraph  (the future minimum spanning tree) after addition of the first two edges ––, ––

The last table demonstrates the following fact. The first two edges of the subgraph  connect two sets of nodes and . Before adding the next edge –– we have to check if it does not imply a new cycle at the subgraph . A sighted student checks that visually while a blind one does so by organizing sets of nodes connected together by edges of the subgraph . If both nodes of a processed edge belong to the same set of nodes, he/she immediately knows a cycle is going to be created. Otherwise he/she can update the Table 3, add the processed edge to the subgraph  and modify the sets of nodes connected together. He/she should not forget the currently processed edge was kept in the Table 2 twice therefore it is necessary to delete it at both places.

2. Edges are organized in two rows of a table, a subgraph is created in another document (sheet):

The graph is again converted to a table but edges are organized differently. They are completely described in the first column as strings –– where symbols indicate nodes connected by an edge with a weight . The second column serves to repeat the weight of the edge. Such an organization of the edges is demonstrated in Table 3.

Example 4: Graph edges organized in two columns

––
––
––
––
––
––
––
––
––
––
––
––

Table 3: Edges of the graph  organized in two columns including their weight

Most of the spreadsheet applications enable users to arrange data according to values of a certain column. Therefore a blind student can sort edges in ascending order with regard to weights kept in the second column. To consecutively prepare the subgraph  and sets of nodes connected by the subgraph's edges we use the second sheet or a separate document. We process the algorithm in the same manner as previously.

Let us state in advance that blind students find the second method of adaptation better. There are three main reasons for that:

1. they can immediately find the edge which should processed;
2. they spend less time moving the cursor between rows and columns of the table;
3. they do not need to delete the processed edge twice.

When using the first method they have difficulties finding the edge with the lowest weight. They can solve the problem if they search for them by finding strings as "––", "––", etc. One of the students came up with a proposal to leave the concept of the graph representation by means of a table and use the same arrangement of edges in any plain text editor. Edges of a certain node would be positioned on a line separated by commas or spaces. In that case blind students can use keyboard shortcuts or a refreshable braille display and its functions to work with a text effectively.