CODEWITHSUNDEEP
matlabgraph-theorybreadth-first-search
Olivia Huang
Olivia Huang

Reputation: 23

Graph theory Matlab BFS algorithm

I am trying to write a function that convert the adjacency matrix to a BFS list. The output contains two rows, one is the index of node and the second is the order of visiting the node. The function should look like that, where A is the adjacency matrix:

function [ forest ] = Find_BFS_forest( A )

For example, when the input A is [0,1,0,0,1,0;1,0,1,0,0,0;0,1,0,0,0,0;0,0,0,0,0,0;1,0,0,0,0,0;0,0,0,0,0,0] the edge_list is {(1,2) (1,5) (2,3)}. I want the output to be [1,2,5,3,4,6;0,1,1,2,0,0]

n=length(A);
% vis to mark if a node is visited earlier or not
vis=zeros(n,1);
% pred to predecessor of each node
pred=zeros(n,1);
% path to store the bfs traversal
path =zeros(n,1); pp = 1;

for i = 1:n
    % start bfs from each unvisited node i
    if vis(i) == 0
        % search queue and search queue tail/head
        sq=zeros(n,1);
        sqt=1;
        sqh=0;
        % push starting node in the queue
        sq(sqt)=i;
        while sqt-sqh>0
            % pop v off the head of the queue
            sqh=sqh+1;
            v=sq(sqh);
            path(pp) = v;
            pp=pp+1;
            for u=1:n
                if A(v,u)==1 && vis(u)==0
                    % if u is connected to v and is unvisited push it to the queue
                    sqt=sqt+1;
                    sq(sqt)=u;
                    vis(u) = 1;
                    pred(u)= v;
                end
            end
        end
    end
end
% create the output forest
forest = zeros(2,n);
for i=1:n
    forest(1,i) = path(i);
    forest(2,i) = pred(path(i));
end
end

Here is the code I have right now, but the nodes are repeating. Where I should make changes??

Thanks in advance!

Upvotes: 2

Views: 1041

Answers (1)

beaker
beaker

Reputation: 16810

You've forgotten to mark the initial node of each tree as visited:

for i = 1:n
    % start bfs from each unvisited node i
    if vis(i) == 0
        vis(i) = 1;   % mark initial node as visited <-- added
        % search queue and search queue tail/head
...

Output after the addition:

forest =
   1   2   5   3   4   6
   0   1   1   2   0   0

Upvotes: 1

Related Questions