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 $G = (V, E, w)$ where $V$ is a set of nodes, $E$ is a set of undirected edges and $w$ is a positive weight of any edge.

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

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

Example 1: Weighted undirected graph $H$

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

We cannot add the next two edges of the weight $4$ to the subgraph $T$ because they would both establish a cycle of the size $3$ (tripple of the nodes $C, D, F$ or $D, E, G$).

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 $X$ are reserved for the edges coming out from $X$ and are written as $X$–$n$–$Y$ where $n$ is a weight of the edge and $Y$ is the end node of the edge. We use another sheet or a separate text file:

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

Let's take the same graph $H$ 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 $T$.

The last table demonstrates the following fact. The first two edges of the subgraph $T$ connect two sets of nodes $ \{ C, F \}$ and $ \{ D, E \}$. Before adding the next edge $C$–$3$–$D$ we have to check if it does not imply a new cycle at the subgraph $T$. A sighted student checks that visually while a blind one does so by organizing sets of nodes connected together by edges of the subgraph $T$. 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 $T$ 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 $x$–$n$–$y$ where symbols $x, y$ indicate nodes connected by an edge with a weight $n$. The second column serves to repeat the weight of the edge. Such an organization of the edges is demonstrated in Table 3.

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 $T$ 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 "–$1$–", "–$2$–", 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.