You must implement Kruskal?s Algorithm in assembly language and test
it on data to prove its correctness.
1.Sort all edges using some sorting algorithm into increasing order by edge weight.
2.Take lowest-cost edge ij not in MST; if ij doesn?t form a cycle then
output that edge.
3.If not all vertices are in MST, repeat step 2.
Below are some egdes with their weight 
ab-1
dg-1
fi-1
be-2
bc-3
ef-3
cf-4
de-4
gh-4
ae-5
ce-6
eh-6
eg-7
ei-7
ad-8
hi-8

---

Clarification of Question by kaycee1234-ga on 28 Feb 2005 21:44 PST

It has to be in Intel assembly to run with Masm615 assembler

---

Clarification of Question by kaycee1234-ga on 01 Mar 2005 12:32 PST

I am trying to make arrays and sort them in order, then delete the
non-shortest paths but even if i do that for the weights/numbers, how
do i make the weights when sorted, to also carry along their path such
as ab-1,ad-8 e.t.c

TITLE Kruskal's Algorithm		

INCLUDE Irvine32.inc
.data

V1    BYTE "a","a","a","b","b","c","c","d","d","e","e","e","e","f","g","h"
V2    BYTE "b","d","e","c","e","e","f","e","g","f","g","h","i","i","h","i"
cost  BYTE   1,  8,  5,  3,  2,  6,  4,  4,  1,  3,  7,  6,  7,  1,  4,  8

.code
main PROC
	mov edi,OFFSET cost  ;address of cost
	mov ecx,LENGTHOF cost	


	dec ecx
L1:   push ecx
	mov esi,cost

L2:	mov eax,[esi]
	cmp [esi+1],eax
	jge L3
	xchg eax,[esi+1]
	mov [esi],eax

L3:	add esi,1
	loop L2

	pop ecx
	loop L1
	exit
main ENDP
END main

---

Clarification of Question by kaycee1234-ga on 02 Mar 2005 07:58 PST

Below is a code i have been able to come up with. It compiles but does
not run. Please can someone help fix this problem?

INCLUDE Irvine32.inc
.data
V1 BYTE "a", "a", "a", "b", "b", "c", "c", "d", "d", "d", "e", "e",
"e", "f", "f", "f", "g", "g", "g", "h", "h", "h", "i", "i", "i";
V2 BYTE "d", "e", "b", "e", "c", "e", "f", "e", "a", "g", "i", "h",
"g", "e", "c", "i", "d", "e", "h", "g", "e", "i", "h", "e", "f";
COST BYTE 1,2,2,7,4,5,7,3,2,3,4,5,6,9,6,5;
Temp BYTE ?
AnsV1 BYTE ?
AnsV2 BYTE ?
ACost BYTE ?
.code 
main PROC
	mov esi,OFFSET V1
	mov edi,OFFSET Temp
	mov ebx,OFFSET COST
	mov edx,OFFSET V2
	mov ecx,OFFSET ACost
;~-----------------------------------------------------------------------------------
L1:	push esi	; Starting of Code----Moving the value of array V1 into stack
	mov edi,ebx ; moving the associated cost into Temp for comparison
	add esi,4   ; incrementing the pointer 
JP1:cmp ebp,esi ; comparing the next value with the one in stack
    jne L2		; If not equal then the next value is the next node in Spanning Tree
    add ebx,4	; incrementing the pointer
    mov edi,ebx ; Storing the value to choose the minimum in Temp
Loop JP1		; Repeat until there is a new value
Loop L1
;~-----------------------------------------------------------------------------------
L2: mov eax,edi	; Finding the minimum value	
	add edi,4	 ; Sorting	
	cmp eax,edi
	jle L2       ; If less than or equal to : compare with next value
	mov eax,edx; Else what is the next node for minimum edge value
    cmp eax,ebp	 ; compare with the existing node if same or not i.e.
if there is a loop
    jne	L4		 ; if the values not are equal then jump to L4
	mov edi,1000 ; else go back one step and repeat the same process
without the previous vertex
	jmp JP1 	 ;
	 	
L4: ;mov AnsV1[ecx],ebp
    ;mov AnsV2[ecx],eax   
    mov ecx,ebx
	;inc ecx
;~-------------------------------------------------------------------------------------
	mov edx,OFFSET ACost
	call WriteString
    main endp
END main

I'd understand if you were looking for advice on how to approach the
problem, or posting samples of your code and asking for assistance. 
If you want someone to do this work for you, maybe you'd be better
suited with a different major.

I may not be the best to answer your question and perhaps you are
looking for a complete answer.  I'll give you a point in the right
direction in case no one provides the finished code for you.

You'll need to implement an array of structures to hold each edge.

Here's a primer on how to do structures:
http://maven.smith.edu/~thiebaut/ArtOfAssembly/CH05/CH05-3.html

Once you get the gist of how to do the addressing to get to the right
record and field, its not so bad.  Memory diagrams are very helpful
for this.  You may need an extra byte in your structure to hold
status.  For example, you can flag a bit in the status field to
"eliminate" an edge during processing or mark it as "followed."  If
you manipulate everything carefully in the array, the status field may
not even be necessary.

I take from the problem statement that your sorting routine can use a
simple algorithm such as bubble sort.  If so, just write a support
routine (basically a static method) that swaps the contents of two
records in the array and the rest is fairly straightforward.