In this problem, you're going to find the path taken by a tourist on a given undirected graph G going from S to F and sa

[answerhappygod]

In This Problem You Re Going To Find The Path Taken By A Tourist On A Given Undirected Graph G Going From S To F And Sa 1 (96.02 KiB) Viewed 59 times

In this problem, you're going to find the path taken by a tourist on a given undirected graph G going from S to F and save that sequence of vertices in a queue which represents the itinerary of their trip Some of the vertices in the graph are Points of Interest that the tourist wants to visit if given the opportunity. Specifically, here's the rules they follow: The tourist starts from the given node S. • The tourist will stop once they're at their destination (i.e. S == F). The function returns true and no more paths are explored or enqueued to the itinerary. • The tourist chooses the next node to go to from the current, X, as follows: - Any unvisited Points of Interest adjacent to X. - Any unvisited node adjacent to X - The most recent node they went through on their way to X and repeat these choices from there. If there are multiple choices of where to go, they break ties by going to the one with the smallest index in the graph's array of nodes, ver. For example suppose they started from 0 and they were traveling to 8 in the graph below. Each vertex is labeled with its index in the graph's vertex array. The nodes {3,4,7,8,9} are Points of Interest that the tourist will prioritize visiting. S 10 10 F The algorithm should store the following in its itinerary queue: 04 2 401375 78 These are the nodes on the red path followed by the tourist according to the above rules. Continued on next page

* We define a graph as follows: /* Struct for a single node in a graph. The variable ispor is true if this * node is a Point of Interest and is othervise false. * Initially visited = false for all of the nodes */ struct node { boolean visited; boolean isPOI; }; /* Number of nodes in the graph */ int NUMNODES; /* Array of all the nodes in the graph */ node ver [NUMNODES); /* 2d array representing the adjacency matrix */ int adj (NUMNODES] [NUMNODES]; //If there is an edge from the node $vers to the node $ver[j]$ then $adj[j]=1$. I/Otherwise Sadj[j] -0$. You can assume NUM NODES, ver, and adj are global variables (i.e., you can access all of them from your function) You have access to the following function for your Queue: /* Add element x to queue */ insert(Q,x); This should be the only required Queue function since you're only adding elements to the already created itinerary Continued on next page 4

Complete the recursive function "tour" which enqueues the path taken by the tourist into the given Queue called itinerary. bool tour ( int s, int F, Queue* itinerary > 1/Declare variables 1/Find the nodes adj to s 1/Return bool indicating whether you found F yet }