Please help with the program below. Need to write a program called dfs-stack.py in python that uses the algorithm below without an agency list but instead uses an adjacency matrix. The program should prompt the user for the number of vertices V, in the graph.Please read the directions below in the image I will post a picture of the instructions and the algorithm.
Please help with the program below. Need to write a program called dfs-stack.py in python that uses the algorithm below without an agency list but instead uses an adjacency matrix. The program should prompt the user for the number of vertices V, in the graph.Please read the directions below in the image I will post a picture of the instructions and the algorithm.
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Please help with the program below. Need to write a program called dfs-stack.py in python that uses the algorithm below without an agency list but instead uses an adjacency matrix. The program should prompt the user for the number of vertices V, in the graph.Please read the directions below in the image I will post a picture of the instructions and the algorithm.
![Algorithm 2.3: Graph depth-first search with a stack.
StackDFS (G, node) → visited
Input: G=(V, E), a graph
1
2
3
4
node, the starting vertex in G
Output: visited, an array of size |V| such that visited[i] is TRUE if we
have visited node i, FALSE otherwise
S-CreateStack()
2
5 Push (S, node)
6
8
visited CreateArray (VI)
for i-0 to V| do
9
10
11
visited[i] FALSE
while not IsStackEmpty(S) do
1-
c-Pop (s)
visited[c] TRUE
foreach in AdjacencyList (G, c) do
if not visited[v] then
Push (S.)
return visited
added only if it is not already in the stack. To do this we use an additional
array. An element of that array will be true if that element is currently in the
stack and false otherwise. Algorithm 2.4 is the result. The algorithm is pretty
much the same as algorithm 2.4 but uses the additional array instack, where
8
+
199+
fg
144
10
▶11
▶▶
ins](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F691d33e1-8c25-4f84-bfa0-1a093fc94f94%2F95cf622e-2409-4703-afc7-e9f46a71e942%2Fl5j914_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Algorithm 2.3: Graph depth-first search with a stack.
StackDFS (G, node) → visited
Input: G=(V, E), a graph
1
2
3
4
node, the starting vertex in G
Output: visited, an array of size |V| such that visited[i] is TRUE if we
have visited node i, FALSE otherwise
S-CreateStack()
2
5 Push (S, node)
6
8
visited CreateArray (VI)
for i-0 to V| do
9
10
11
visited[i] FALSE
while not IsStackEmpty(S) do
1-
c-Pop (s)
visited[c] TRUE
foreach in AdjacencyList (G, c) do
if not visited[v] then
Push (S.)
return visited
added only if it is not already in the stack. To do this we use an additional
array. An element of that array will be true if that element is currently in the
stack and false otherwise. Algorithm 2.4 is the result. The algorithm is pretty
much the same as algorithm 2.4 but uses the additional array instack, where
8
+
199+
fg
144
10
▶11
▶▶
ins
Transcribed Image Text:1. Using Python, you will write a program called dfs-stack.py that implements Algorithm 2.3 (p. 49): Graph depth-first search (DFS) with a stack.
2. You will not use an adjacency list, as indicated in Algorithm 2.3. Instead, you will use an adjacency matrix (i.e., a two-dimensional array, or, in Python, a list of lists).
3. You may use ANY list method you wish (e.g., append, pop, etc.).
IMPLEMENTATION DETAILS:
4
1. Based upon the REQUIREMENTS above, along with the IMPLEMENTATION DETAILS (i.e., this section), you MUST develop a FINAL algorithmic solution using pseudocode.
This includes both your logic (in pseudocode) and the logic presented in the pseudocode indicated in Algorithm 2.3.
2. Be sure to include your name, along with the Certificate of Authenticity, as comments at the very beginning of your Python code. Also, if you collaborated with others,
be sure to state their names as well.
3. Your program should begin by prompting the user for the number of vertices, V, in the graph, G.
4. Your program will represent the graph G using an adjacency matrix, which is a square matrix with a row and a column for each vertex. Thus, your program will need to
create a matrix M that consists of a Vx Vtwo-dimensional array -- in Python, a list of lists. (I recommend that your program initialize each element of the matrix equal
to zero.)
5. Next, your program should prompt the user to indicate which elements in the matrix should be assigned the value of 1 (i.e., information about vertices). Recall that
each element in the matrix is the intersection of a row and a column.
6. The result of step 4 should be an adjacency matrix representation of a graph, G.
7. At this point, your program should print the newly-created adjacency matrix on the screen.
8. Next, your program should prompt the user to specify node -- i.e., the starting vertex in G.
9. From here, you then proceed with the implementation of Algorithm 2.3, with the following enhancements:
o Be sure to use the newly-created adjacency matrix, instead of an adjacency list.
o Immediately following line 5 (but before line 6) of Algorithm 2.3, your program should print the values currently on the stack.
o At the end of the while block, your program should print the values currently on the stack.
In effect, the result of step 8 above should be a display of the stack evolution for your implementation of the DFS algorithm on graph G.
Back to Top
Expert Solution
Step 1 : Code (Explained with comment)
def dfs(graph, start):
stack = [start] # stack with starting vertex
visited = [False for i in range(len(graph))] # visited list
visited[start] = True # mark the starting vertex as visited
print(visited) # print the visited list 9a
while stack: # while the stack is not empty
v = stack.pop() # pop the last element from the stack
for i in range(len(graph)): # for each vertex in the graph
if graph[v][i] != 0 and not visited[i]:
# if there is an edge between v and i and i is not visited
stack.append(i) # append i to the stack
visited[i] = True # mark i as visited
print(stack) # print the stack 9c
return visited
def main():
V = int(input("Enter the number of vertices:")) # number of vertices
E = int(input("Enter the number of edges:")) # number of edges
graph = [[0 for i in range(V)] for j in range(V)] # adjacency matrix
for i in range(E): # for each edge
a, b = map(int, input().split()) # get the vertices
graph[a][b] = 1 # add the edge
graph[b][a] = 1 # add the edge
print(*graph, sep="\n") # print the adjacency matrix
print() # print a new line
start = int(input("Enter the starting vertex:")) # get the starting vertex
print(*dfs(graph, start), sep=",") # print the visited list 9
print()
if __name__ == '__main__':
main()
Step by step
Solved in 3 steps with 2 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY