For this homework, you will upload a zip file containing two files. The first fi

Question

For this homework, you will upload a zip file containing two files. The first file is find nbrs.m. This is the same function as from Homework 2, but you can update it if you want. The second file is component m, described below. You will write a function called "component" which, given the adjacency matrix of an undirected graph and a vertex in that graph, finds all vertices reachable from that 2-3-4 (5) vertex. For example, if your adjacency matrix is associated to the graph shown above, and you input vertex 2, the output should be (in some order) the vector [1 2 3 4 71. If you input vertex 6, the output should be [5 6]. If you input 8, the output should be [8] To receive full credit, your function must work as follows. The idea is to begin with a vertex m, and then for each vertex neighboring m, call the function again using your same function "component". This strange situation where the function calls itself is called "recursive programming". But there is a problem. If we start with the graph displayed above and the vertex 5, we will call the component function with the vertex 5, then we will call it with the vertex 6, then we will call it with the vertex 5, and we will continue forever. To fix I this problem, we need to have three inputs to component, not just two. These three components are the adjacency matrix A, a vertex m, and a vector of found vertices. We will never call the component function together with a vertex that's already on the list of found vertices. Each time component(A,m,found Jist) is called: Add the vertex m to found list. For each neighbor of m (let's call that neighbor k), if kis not already in found list, run component(A,k,found list) of your function find nbrs from the previous homework to find the neighbors m.) The functio component" should output the new (longer) found list. Make sure found list is constantly updated along the way The first time you call component, you should use the empt vector I l for foun list.

Explanation / Answer

function l = component(mat,ver)
   x,y = size(mat);
   visit = zeros(1,x);
   l = DFS(mat,ver,visit,[],x)
end

function l = DFS(mat,ver,visit,path,tol_ver)
   path = [path ver];
   visit(:,ver) = 1;
   for i = 1:tol_ver
       if (mat(ver,i) == 1 && visit(:,i) == 0)
           DFS(mat,i,visit,path,tol_ver);
       end
   end
   l = path
end

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.