bfs.lisp

(defun bfs (graph listed visitStatus)
  (if (= (list-length listed) 0)
    (return-from bfs 0)
  )
  (setf poped (car listed))
  (setf listed (cdr listed))
  (if (= (aref visitStatus (- poped 1)) 0)
    (progn
      (terpri)
      (format t "~D " poped)
      (setf (aref visitStatus (- poped 1)) 1)
      (setf listed (reverse listed))
      (dotimes (i (car (array-dimensions (aref graph (- poped 1)))))
      (setf listed (cons (aref (aref graph (- poped 1)) i) listed))
      )
      (setf listed (reverse listed))
    )
  )
  (if (not (= (list-length listed) 0))
    (bfs graph listed visitStatus)
  )
)

(format t "Enter N The total number of nodes in Graph")
(terpri)
(setf n (read))
(setf graph (make-array n))
(setf visitStatus (make-array n))
(dotimes (k n)
  (setf (aref visitStatus k) 0)
)
(write visitStatus)
(format t "Enter The Adjancency Matrix")
(terpri)
(dotimes (i n)
    (progn
      (loop
          (format t "Enter The number of nodes connected to ~Dth node in graph" (+ i 1))
          (terpri)
          (setf n1 (read))
          (if (> n1 n)
            (progn
              (format t "Enter A Valid number of nodes connected")
              (terpri)
            )
            (return)
          )
      )

      (setf (aref graph i) (make-array n1))
      (dotimes (j n1)
        (loop
            (format t "Enter ~Dth Number Node ~Dth node is connected to" (+ j 1) (+ i 1))
            (terpri)
            (setf (aref (aref graph i) j) (read) )
            (if (> (aref (aref graph i) j) n)
              (progn
                (format t "Enter A Valid node number")
                (terpri)
              )
              (return)
            )
        )
      )
    )
)

(write graph)
(terpri)
(format t "Enter the starting node for BFS traversal 1 --> ~D" n)
(terpri)
(setf startnode (list (read)))
(format t "The BFS traversal of given Graph is")
(terpri)
(bfs graph startnode visitStatus)