# MATLAB code for Aldous-Broder algorithm from spanning trees of a graph

## Homework Statement

Let G = (V,E) be a graph with vertices V and edge set E.

Aldous-Broder algorithm:
Input: G = (V,E)
Output: T = (V, W), where W is a subset of E such that T is a spanning tree of G.

Let W be the empty set. Add edges to W in the following manner: starting at any vertex v in V,
1) If all vertices in V have been visited, halt and return T
2) Choose a vertex u uniformly at random from the set of neighbors of v.
3) If u has never been visited before, add the edge (u,v) to the spanning tree.
4) Set v, the current vertex, to be u and return to step 1.

1) Write a matlab function USTsample that takes a connected graph specified in the form of a 2-by-n matrix E, where n is the number of edges in the graph, and returns an output from the Aldous-Broder algorithm in the form of a 2-by-r matrix T, where r is the number of edges in the tree generated by the algorithm. Each row of E specifies the two vertices that constitute an edge: e.g. if G has an edge between the 5th vertex and 80th vertex, then either [5 80] or [80 5] (but not both) will be a row of E; T is a similar specification of the edges in the spanning tree. Note that we don't pass in or out the vertex sets: we assume that the vertices of G are 1 through m, where you can determine m as the largest number in E.

2) Write a script function that demonstrates your USTsample function:
- In one cell, specify K5, the complete graph on 5 vertices, in the form that USTsample takes as input, and use USTsample to return a spanning tree of K5
- In another cell, visualize K5 and its spanning tree in one plot. You will need coordinates for the vertices of the graph; according to your own preference, assign the coordinates by hand. Plot the vertices of the graph as red dots and the edges of G as gray lines of width 1. Plot the edges of T as thick red lines of width 2.
- Add two cells that repeat the above two steps (of calling USTsample and visualizing the output) for the grid graph on 10 vertices.

## Homework Equations

Aldous-Broder algorithm

## Answers and Replies

Related Engineering and Comp Sci Homework Help News on Phys.org
lewando
Homework Helper
Gold Member
In order to make any progress on this, you need to show what you have tried, and what, specifically, it is that is giving you troubles.

Here is what I have tried.
I am still debugging some problems, but can anyone debug it?

This is for task1 btw.

#### Attachments

• 404 bytes Views: 365
lewando
Homework Helper
Gold Member
Sorry, I couldn't deal with debugging what you had provided. So I hope you don't mind, but I took the liberty of reorganizing it, adding a commented structure, following the instructions provided more or less verbatim, not trying to pass V, adding a calling script, etc. Plus leaving you still with plenty to do.

Calling script (K4 complete graph to start):
Code:
%USTscript.m

%setup V (K4)
V = 1:4

%setup E (2xn for complete K4 graph)
n = 6;
E = zeros(2,n);

E(1,1)= 1;
E(2,1)= 2;

E(1,2)= 2;
E(2,2)= 3;

E(1,3)= 3;
E(2,3)= 4;

E(1,4)= 1;
E(2,4)= 4;

E(1,5)= 1;
E(2,5)= 3;

E(1,6)= 2;
E(2,6)= 4;

USTsample_version_1(E)
function:
Code:
function [T] = USTsample_version_1(E)

%determine V, m
m = max(max(E));
V=1:m;

%establish empty set W
W = [];

%pick a random v
v = ceil(m*rand)

%LOOP UNITL DONE
V_visited = V; %(all elements non-zero. update element with a zero when visited)

while sum(V_visited)~= 0
%identify the set of neighbors at v
%(you have some fun and add some code..)

%pick a neighbor, u, uniformly at random
%(you have some fun and add some code..)
u = 3;

%if V_visited(u) ~= 0, update W: add edge (v,u)
if V_visited(u) ~= 0
%per convention, specify edges (smallest_v, largest_v)
if u > v
W = [W; v, u];
else
W = [W; u, v];
end

V_visited(u) = 0;
end

%v = u
v = u;

V_visited = [0,0,0,0]; %just to escape for now
end

%setup T
T = W;

end

Last edited: