图的深度优先搜索【源代码】
文章作者：三把刀
assume cs:code
code segment
DFSV db 16 dup(0)
NODEV db "abcde"
NODE db 0,0, 0,0, 0,0, 0,0, 0,0
NODES dw NODE1,NODE2,NODE3,NODE4,NODE5
NODE1 dw 0, 1, 0, 1, 0
NODE2 dw 1, 0, 1, 0, 1
NODE3 dw 0, 1, 0, 1, 1
NODE4 dw 1, 0, 1, 0, 0
NODE5 dw 0, 1, 1, 0, 0
start:
;图有五个节点
mov ax,cs
mov ds,ax
call ShowNodeRelation
call DFSearch
mov ax,4c00h
int 21h
;-----------------------------------DFSearch start
;深度优先搜索
DFSearch:
push si
push di
push ax
push dx
push cx
push bx
mov si,0
mov di,0
mov dl,3
mov byte ptr NODE[di],1
mov byte ptr NODE[di + 1],-1
;打印
push bx
push di
mov ax,di
mov bl,2
div bl
mov di,ax
mov dh,10
inc dl
mov bl,1
mov bh,NODEV[di]
mov cl,00000001B
call print
pop di
pop bx
DFSS:
call DFSF1
cmp byte ptr DFSV[0],-1
je DFSS1
mov ax,0
mov al,DFSV[0]
mov si,ax
mov ax,di
mov NODE[si + 1],al
mov di,si
;打印
push bx
push di
mov ax,di
mov bl,2
div bl
mov di,ax
mov dh,10
inc dl
mov cl,00000001B
call ShowArrow
add dl,4
mov bl,1
mov bh,NODEV[di]
call print
pop di
pop bx
jmp DFSS
DFSS1:
cmp byte ptr NODE[di + 1],-1
je DFSearchReturn
mov ax,0
mov al,NODE[di + 1]
mov si,ax
mov di,si
;打印
push bx
push di
mov ax,di
mov bl,2
div bl
mov di,ax
mov dh,10
inc dl
mov cl,00000001B
call ShowArrow
add dl,4
mov bl,1
mov bh,NODEV[di]
call print
pop di
pop bx
jmp DFSS
DFSearchReturn:
pop bx
pop cx
pop dx
pop ax
pop di
pop si
ret
;--------function1 start
;指定节点是否有未访问的邻近节点
DFSF1:
push si
push di
push ax
mov si,NODES[si]
mov di,0
DFSF1S:
cmp di,10
je DFSF1ReturnB
cmp byte ptr cs:[si],0
je DFSF1S1
cmp byte ptr NODE[di],0
je DFSF1ReturnA
add si,2
add di,2
jmp DFSF1S
DFSF1S1:
add si,2
add di,2
jmp DFSF1S
DFSF1ReturnA:
mov word ptr NODE[di],1
mov ax,di
mov DFSV[0],al
jmp DFSF1Return
DFSF1ReturnB:
mov byte ptr DFSV[0],-1
DFSF1Return:
pop ax
pop di
pop si
ret
;--------function1 end
;-----------------------------------DFSearch end
;-----------------------------------print start
;打印字符
;可以打印单个字符和数据段中的数据
;cl颜色值
;dh,dl传行列
;bl传功能号
;0ds:si传数据段的位置
;1bh传打印的数据
print:
push ax
push di
push es
push dx
push bx
push si
mov ax,0b800h
mov es,ax
mov ax,0
mov al,160
mul dh
mov di,ax
mov ax,2
mul dl
add di,ax
cmp bl,0
je show0
cmp bl,1
je show1
jmp return
show0:
mov al,[si]
mov es:[di],al
mov es:[di + 1],cl
inc si
cmp byte ptr [si],'#'
je return
add di,2
jmp show0
show1:
mov es:[di],bh
mov es:[di + 1],cl
return:
pop si
pop bx
pop dx
pop es
pop di
pop ax
ret
;-----------------------------------print end
;-----------------------------------ShowArrow start
ShowArrow:
jmp ShowArrowStart
SACUE db "-->#"
ShowArrowStart:
push ax
push bx
push ds
push si
mov ax,cs
mov ds,ax
mov si,offset SACUE
mov bl,0
call print
pop si
pop ds
pop bx
pop ax
ret
;-----------------------------------ShowArrow end
;-----------------------------------ShowNodeRelation start
;显示节点间的关系
ShowNodeRelation:
push di
push si
push cx
push dx
push ax
push bp
call ClearScreen
mov di,0
mov dl,0
mov cx,5
SNRS:
push cx
mov si,0
mov al,dl
mov dh,5
mov bp,NODES[di]
;打印
push dx
push cx
push bx
push ax
mov dh,4
mov cl,00000001B
mov ax,di
mov bl,2
div bl
mov bl,al
call ShowCue
pop ax
pop bx
pop cx
pop dx
mov cx,5
SNRS1:
cmp word ptr [bp + si],0
je SNRS2
push cx
push di
push si
push ax
mov cl,00000001B
mov ax,di
mov bl,2
div bl
mov di,ax
mov bl,1
mov bh,NODEV[di]
call print
inc dl
call ShowArrow
add dl,4
mov ax,si
mov bl,2
div bl
mov si,ax
mov bl,1
mov bh,NODEV[si]
call print
pop ax
pop si
pop di
pop cx
inc dh
mov dl,al
SNRS2:
add si,2
loop SNRS1
add dl,10
add di,2
pop cx
loop SNRS
pop bp
pop ax
pop dx
pop cx
pop si
pop di
ret
;-----------------------------------ShowNodeRelation end
;-----------------------------------ShowCue start
;显示提示
;bl传打印那个提示
ShowCue:
jmp ShowCueStart
CUES dw CUE0,CUE1,CUE2,CUE3,CUE4
CUE0 db "node a:#"
CUE1 db "node b:#"
CUE2 db "node c:#"
CUE3 db "node d:#"
CUE4 db "node e:#"
ShowCueStart:
push ax
push bx
push si
push ds
mov al,2
mul bl
mov bx,ax
mov ax,cs
mov ds,ax
mov si,CUES[bx]
mov bl,0
call print
ShowCueReturn:
pop ds
pop si
pop bx
pop ax
ret
;-----------------------------------ShowCur end
;--------------------------------ClearScreen start
;清屏
ClearScreen:
push bx
push es
push cx
mov bx,0b800h
mov es,bx
mov bx,0
mov cx,2000
CLS:
mov byte ptr es:[bx],' '
add bx,2
loop CLS
pop cx
pop es
pop bx
ret
;--------------------------------ClearScreen end
code ends
end start
发表日期：09/09/21 00:00
网友评论(0)
当前1/1页 首页 上一页下一页 尾页