Last active
September 21, 2016 22:27
-
-
Save gosuri/5158872 to your computer and use it in GitHub Desktop.
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking. A graph can be represented by its adjacency matrix G, where G[i][j] == 1 if there is an edge betwe…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| .data | |
| Graph: .word 0,1,1,0,0,1,1,0,0 | |
| .word 1,0,0,0,0,0,0,0,0 | |
| .word 1,0,0,0,0,0,0,0,0 | |
| .word 0,0,0,0,1,1,0,0,0 | |
| .word 0,0,0,1,0,1,1,0,0 | |
| .word 1,0,0,1,1,0,0,0,0 | |
| .word 1,0,0,0,1,0,0,0,0 | |
| .word 0,0,0,0,0,0,0,0,0 | |
| .word 0,0,0,0,0,0,0,0,0 | |
| Graph2: .space 400 # temp array to store explored edges | |
| N: .word 0 # stores the array size | |
| Labels: .byte 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J' | |
| welcomemsg: .asciiz "Welcome to Depth First Search Traversal in MAL" | |
| inputmsg: .asciiz "\nEnter the root node: " | |
| linefeed: .asciiz "\n" | |
| .text | |
| .align 2 | |
| .globl main | |
| main: la $a0, welcomemsg # printf("%s", welcomemsg) | |
| li $v0, 4 | |
| syscall | |
| li $t0, 4 # Get the size of the graph | |
| la $s0, Graph # N = sqrt( (&graph2 - &graph)/4 ) | |
| la $s1, Graph2 | |
| sub $a0, $s1, $s0 | |
| div $a0, $a0, $t0 | |
| jal sqrt | |
| sw $v0, N | |
| input: li $v0, 4 | |
| la $a0, inputmsg | |
| syscall | |
| la $a0, Graph # &graph // Base address of the source graph | |
| lw $a1, N # size // Size of the Graph | |
| la $a2, Graph2 # &graph2 // Base address of the target graph | |
| jal InitGraph2 | |
| li $v0, 5 # take user input | |
| syscall | |
| move $a2, $v0 # root = input from user | |
| beq $a2, $zero, rdone # while ( root != 0 ) { | |
| lw $a1, N # size = Size of the Graph | |
| la $a0, Graph2 | |
| jal dfs # dfs(*graph2, size, root) | |
| j input # } | |
| dfs: addi $sp, $sp, -40 # adjust the stack | |
| sw $s5, 36($sp) # stores j ( temp pointer to graph ) | |
| sw $s4, 32($sp) # stores i ( counter variable ) | |
| sw $s3, 28($sp) # stores k = size * 4 | |
| sw $s2, 24($sp) # stores root | |
| sw $s1, 20($sp) # stores size | |
| sw $s0, 16($sp) # stores *graph | |
| sw $a2, 12($sp) # save a2 | |
| sw $a1, 8($sp) # save a1 | |
| sw $a0, 4($sp) # save a0 | |
| sw $ra, 0($sp) # save the return address ( to support recursion ) | |
| add $s0, $a0, $zero # saving the *graph | |
| add $s1, $a1, $zero # saving the size | |
| add $s2, $a2, $zero # saving the root | |
| li $s3, 4 # k = size * 4 | |
| mul $s3, $s3, $s1 | |
| add $a0, $zero, $s2 # printl(root) | |
| jal printl | |
| addi $s5, $s2, -1 # j = graph + ( (root - 1) * k ) | |
| mul $s5, $s5, $s3 | |
| add $s5, $s5, $s0 | |
| li $s4, 1 # i = 1 (counter) | |
| while1: bgt $s4, $s1, endloop1 # while ( i < size ) { | |
| sw $zero, ($s5) # *j = 0 | |
| addi $s5, $s5, 4 # j += 4 | |
| addi $s4, $s4, 1 # i++ | |
| j while1 # } | |
| endloop1: addi $s5, $s2, -1 # j = graph + ( ( root - 1 ) * 4 ) | |
| li $t1, 4 | |
| mul $s5, $s5, $t1 | |
| add $s5, $s5, $s0 | |
| li $s4, 1 # i = 1 (counter) | |
| while2: bgt $s4, $s1, endloop2 # while ( i < size ) { | |
| lw $t2, ($s5) # if ( *graph != 0 && i != root ) { | |
| beq $t2, $zero, L1 | |
| beq $s4, $s2, L1 | |
| move $a0, $s0 # dfs(*graph, size, i) | |
| move $a1, $s1 | |
| move $a2, $s4 | |
| jal dfs | |
| L1: addi $s4, $s4, 1 # } i++ | |
| add $s5, $s5, $s3 # j += k | |
| j while2 # } | |
| endloop2: lw $ra, 0($sp) | |
| lw $a0, 4($sp) | |
| lw $a1, 8($sp) | |
| lw $a2, 12($sp) | |
| lw $s0, 16($sp) | |
| lw $s1, 20($sp) | |
| lw $s2, 24($sp) | |
| lw $s3, 28($sp) | |
| lw $s4, 32($sp) | |
| lw $s5, 36($sp) | |
| addi $sp, $sp, 40 # pop items and adjust the stack pointer | |
| jr $ra | |
| InitGraph2: addi $sp, $sp, -16 # InitGraph2(*source, size, *target) | |
| sw $s0, 12($sp) # stores i // counter | |
| sw $a2, 8($sp) # save a2 // target | |
| sw $a1, 4($sp) # save a1 // size | |
| sw $a0, 0($sp) # save a0 // source | |
| mul $a1, $a1, $a1 # size = size * size | |
| li $s0, 1 # i = 1 // counter | |
| li $t1, 1 # j = 1 | |
| while3: bgt $s0, $a1, endloop3 # while ( i < size) { | |
| sw $zero, ($a2) # *target = 0 | |
| lw $t0, ($a0) | |
| bne $t0, $t1, L2 # if ( *target == j ) | |
| sw $t0, ($a2) # *source = j | |
| L2: addi $a0, $a0, 4 # source += 4 | |
| addi $a2, $a2, 4 # target += 4 | |
| addi $s0, $s0, 1 # i++ | |
| j while3 # } | |
| endloop3: lw $a0, 0($sp) | |
| lw $a1, 4($sp) | |
| lw $a2, 8($sp) | |
| lw $s0, 12($sp) | |
| addi $sp, $sp, 16 # pop items and adjust the stack pointer | |
| jr $ra | |
| printl: addi $sp, $sp, -8 # adjust stack to make room for 2 items | |
| sw $t0, 4($sp) # save register t0 to use afterwards | |
| sw $s0, 0($sp) # save register s0 to use afterwards | |
| la $s0, Labels | |
| addi $t0, $a0, -1 | |
| add $t0, $t0, $s0 | |
| lb $a0, ($t0) | |
| li $v0, 11 # Put | |
| syscall | |
| lw $s0, 0($sp) | |
| lw $t0, 4($sp) | |
| addi $sp, $sp, 8 | |
| jr $ra | |
| sqrt: addi $v0, $zero, 0 # r = 0 | |
| loop: mul $t0, $v0, $v0 # t0 = r*r | |
| bgt $t0, $a0, end # if (r*r > n) goto end | |
| addi $v0, $v0, 1 # r = r + 1 | |
| j loop # goto loop | |
| end: addi $v0, $v0, -1 # r = r - 1 | |
| jr $ra # return with r-1 in $v0 | |
| rdone: li $v0, 10 | |
| syscall |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment