Homework Answers
1. An adjacency matrix of 5 nodes will have 5*5=25 elements.
Each element requires 4 bytes.
Therefore, total storage required = 25*4 = 100 bytes.
2. Adjacency List
1->2->4
2->1->4->5->3
3->2->5
4->1->2->5
5->2->4->3
Total int stored = 19
Total pointers used = 14
Total storage = (19+14) * 4 = 33*4 = 132 bytes.
3. 100 vertices and 1000 edges.
Storage in Adjacency Matrix = 10000*4 = 40000 bytes
Storage in Adjacency List = (2000 +1000) *4 = 12000 bytes
3.
storage in Adjacency List=(2000+(2000+100))*4=4100*4=16400 bytes
Add Answer to:
Graph Representation Worksheet 4 1. What are the storage requirements assuming an adjacency matrix is used....
Give the adjacency matrix representation and the adjacency lists representation for the graph G_1. Assume that...
Give the adjacency matrix representation and the adjacency lists representation for the graph G_1. Assume that vertices (e.g., in adjacency lists) are ordered alphabetically. For the following problems, assume that vertices are ordered alphabetically in the adjacency lists (thus you will visit adjacent vertices in alphabetical order). Execute a Breadth-First Search on the graph G_1, starting on vertex a. Specifiy the visit times for each node of the graph. Execute a Depth-First Search on the graph G_1 starting on vertex...
4&5 0 1 2 3 1. Draw the undirected graph that corresponds to this adjacency matrix...
4&5
0 1 2 3 1. Draw the undirected graph that corresponds to this adjacency matrix 0 0 1 1 0 1 1 1 1 0 1 1 1 2 1 1 1 0 1 3 1 0 1 1 0 1 2. Given the following directed graph, how would you represent it with an adjacency list? 3. We've seen two ways to store graphs - adjacency matrices, and adjacency lists. For a directed graph like the one shown above,...
3. (8 points-7+1) Figure 4 shows an undirected graph G. Assume that the adjacency list lists the ...
3. (8 points-7+1) Figure 4 shows an undirected graph G. Assume that the adjacency list lists the edges in alphabetical order. Figure 3: Graph for P3 (a) Apply depth first search (DFS) to graph G, and show the discovery and finish times of each vertex. In the main-loop of DFS, check the vertices in alphabetical the form dsc/fin, where dsc is the discovery time and fin is the finish time. (b) Draw the DFS tree obtained.
3. (8 points-7+1) Figure...
Consider the java Graph class below which represents an undirected graph in an adjacency list. How...
Consider the java Graph class below which represents an undirected graph in an adjacency list. How would you add a method to delete an edge from the graph? // Exercise 4.1.3 (Solution published at http://algs4.cs.princeton.edu/) package algs41; import stdlib.*; import algs13.Bag; /** * The <code>Graph</code> class represents an undirected graph of vertices * named 0 through V-1. * It supports the following operations: add an edge to the graph, * iterate over all of the neighbors adjacent to a vertex....
Exercise 1 Adjacency Matrix In this part, you will implement the data model to represent a graph. Implement the followi...
Exercise 1 Adjacency Matrix In this part, you will implement the data model to represent a graph. Implement the following classes Node.java: This class represents a vertex in the graph. It has only a single instance variable of type int which is set in the constructor. Implement hashCode() and equals(..) methods which are both based on the number instance variable Node - int number +Node(int number); +int getNumberO; +int hashCode() +boolean equals(Object o) +String toString0) Edge.java: This class represents a...
Below is the Graph file that needs to be modified(using Python3) : #!/usr/bin/python3 # Simple Vertex...
Below is the Graph file that
needs to be modified(using Python3) :
#!/usr/bin/python3
# Simple Vertex class
class Vertex:
""" Lightweight vertex structure for a graph.
Vertices can have the following labels:
UNEXPLORED
VISITED
Assuming the element of a vertex is string type
"""
__slots__ = '_element', '_label'
def __init__(self, element, label="UNEXPLORED"):
""" Constructor. """
self._element = element
self._label = label
def element(self):
""" Return element associated with this vertex. """
return self._element
def getLabel(self):
""" Get label assigned to...
Creating a simple graph in C++; need solution ASAP. EDIT: Pls comment letting me know what...
Creating a simple graph in C++; need solution ASAP. EDIT: Pls comment letting me know what other information you need rather than just "..." Thank you. Here is the assignment: In this final practice problem, you’ll: read a set of data representing a directed, unweighted graph build an in-memory graph structure using the data display the graph using depth-first traversal display the graph using breadth-first traversal Input data - The data consists of records like this: 16 3 15 4...
Give the adjacency matrix representation and the adjacency lists representation for the graph G_1. Assume that vertices (e.g., in adjacency lists) are ordered alphabetically. For the following problems, assume that vertices are ordered alphabetically in the adjacency lists (thus you will visit adjacent vertices in alphabetical order). Execute a Breadth-First Search on the graph G_1, starting on vertex a. Specifiy the visit times for each node of the graph. Execute a Depth-First Search on the graph G_1 starting on vertex...
4&5
0 1 2 3 1. Draw the undirected graph that corresponds to this adjacency matrix 0 0 1 1 0 1 1 1 1 0 1 1 1 2 1 1 1 0 1 3 1 0 1 1 0 1 2. Given the following directed graph, how would you represent it with an adjacency list? 3. We've seen two ways to store graphs - adjacency matrices, and adjacency lists. For a directed graph like the one shown above,...
3. (8 points-7+1) Figure 4 shows an undirected graph G. Assume that the adjacency list lists the edges in alphabetical order. Figure 3: Graph for P3 (a) Apply depth first search (DFS) to graph G, and show the discovery and finish times of each vertex. In the main-loop of DFS, check the vertices in alphabetical the form dsc/fin, where dsc is the discovery time and fin is the finish time. (b) Draw the DFS tree obtained.
3. (8 points-7+1) Figure...
Exercise 1 Adjacency Matrix In this part, you will implement the data model to represent a graph. Implement the following classes Node.java: This class represents a vertex in the graph. It has only a single instance variable of type int which is set in the constructor. Implement hashCode() and equals(..) methods which are both based on the number instance variable Node - int number +Node(int number); +int getNumberO; +int hashCode() +boolean equals(Object o) +String toString0) Edge.java: This class represents a...
Below is the Graph file that
needs to be modified(using Python3) :
#!/usr/bin/python3
# Simple Vertex class
class Vertex:
""" Lightweight vertex structure for a graph.
Vertices can have the following labels:
UNEXPLORED
VISITED
Assuming the element of a vertex is string type
"""
__slots__ = '_element', '_label'
def __init__(self, element, label="UNEXPLORED"):
""" Constructor. """
self._element = element
self._label = label
def element(self):
""" Return element associated with this vertex. """
return self._element
def getLabel(self):
""" Get label assigned to...
Most questions answered within 3 hours.
-
The denaturation of proteins can be described by the
equilibrium
F⇌U
where F and U represent...
asked 42 minutes ago -
Please answer what the maximum and minimum force is, and the
angle on the ion is...
asked 44 minutes ago -
implement a program that reads a number of rows and a symbol.
The program will draw...
asked 50 minutes ago -
Assume that when adults with smartphones are randomly selected,
45% use them in meetings or classes....
asked 54 minutes ago -
Determine the number of formula units of
Na2SO4 and moles of oxygen contained in 8.11
moles...
asked 1 hour ago -
Explain in steps on the following code
What would be the output when executed
using System;...
asked 1 hour ago -
Given the information in the table, which of the following
statements is CORRECT?
Stock A
Stock...
asked 1 hour ago -
Write MARIE assembly language programs that do the following:
Write a program that inputs an integer...
asked 1 hour ago -
Explain an understanding of services and protocols.
Explain the job of DNS.
Explain the three email...
asked 1 hour ago -
(As soon as possible) Balance each of the following equations
according to the half-reaction method:
H2O2(aq)...
asked 1 hour ago -
A thin rod with a mass of 3.5kg and a length L=1.5 m is oriented
horizontally....
asked 1 hour ago -
Inheritance pattern in BRCA 1
Describe the inheritance pattern of BRCA 1 Is it recessive or...
asked 1 hour ago