Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

9.3. The Graph Abstract Data Type

The graph abstract data type (ADT) is defined as follows:

• Graph() creates a new, empty graph.

• addVertex(vert) adds an instance of Vertex to the graph.

• addEdge(fromVert, toVert) Adds a new, directed edge to the graph that connects two vertices.

• addEdge(fromVert, toVert, weight) Adds a new, weighted, directed edge to the graph that connects two vertices.

• getVertex(vertKey) finds the vertex in the graph named vertKey.

• getVertices() returns the list of all vertices in the graph.

• in returns True for a statement of the form vertex in graph, if the given vertex is in the graph, False otherwise.

Beginning with the formal definition for a graph there are several ways we can implement the graph ADT in Python. We will see that there are trade-offs in using different representations to implement the ADT described above. There are two well-known implementations of a graph, the adjacency matrix and the adjacency list. We will explain both of these options, and then implement one as a Python class.

Q-1: Drag and drop each graph abstract data type to its corresponding definition. This is feedback.
• Graph()
• creates a new, empty graph.
• addVertex(vert)
• adds an instance of Vertex to the graph.
• addEdge(fromVert, toVert)
• Adds a new, directed edge to the graph that connects two vertices.
• addEdge(fromVert, toVert, weight)
• Adds a new, weighted, directed edge to the graph that connects two vertices.
• getVertex(vertKey)
• finds the vertex in the graph named vertKey.
• getVertices()
• returns the list of all vertices in the graph.
• in
• returns True for a statement of the form vertex in graph, if the given vertex is in the graph, False otherwise.

Before you keep reading...

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

Support Runestone Academy Today

You have attempted 1 of 2 activities on this page