Yesterday I wrote about the number of connected components. The algorithm is a variation on breadth first search, and is very inefficient. Today, I am going to write a lisp function that returns a list of connected components.
Given an edge, the first function returns the list of vertices that belongs to the same connected component with the edge.
(defun handle (e components &optional A)
(let* ((x (car e))
(y (cadr e))
(c (car components)))
(cond
((null components) (union e A))
((or (member x c)
(member y c))
(handle e (cdr components) (union e (union c A))))
(t (handle e (cdr components) A)))))HANDLEThe second function returns the list of connected components of a graph.
(defun connected-components (G &optional components)
(if (null G)
components
(let* ((W (handle (car G) components))
(U (remove-if (lambda (xs) (intersection xs W)) components)))
(connected-components (cdr G) (append U (list W))))))CONNECTED-COMPONENTSLet us test:
(defparameter G
'((0 1) (1 2) (1 3) (2 4) (3 4) (5 6) (6 7)
(8 9) (8 10) (10 8) (9 11)
(12 13) (13 14) (13 15) (14 15)))
(connected-components G)G
((0 1 2 3 4) (5 6 7) (10 8 9 11) (12 13 14 15))