STD 03 - Implement Graph as Adjacency Matrix
Intro
Adjacency matrix is a way to show a graph using a table. If there is a connection between two vertices, it's marked as 1, otherwise it's 0. It's a fast way to check and change connections.
Task
Using the given python code use python to implement an unweighted and undirected graph data structure as an adjacency matrix, where the vertices consist of positive integers (note that 0 is not a positive integer). The program should have methods for the following:
- Adding a vertex to the graph.
- Adding an edge to the graph. This should check whether the edge already exists.
- Removing an edge from the graph. Checking that there is an edge to remove.
- Printing the graph as a matrix.
IMPORTANT:
- The code as given may need altering to allow the new methods to be introduced.
- Edges can be removed with no need to worry about vertices.
NOTE: If you wish, you could implement the entire code as C++ instead of, or in addition to, python. This is not mandatory for this task.
Python code
class Graph(object):
def __init__(self, size):
self.adjMatrix = []
for i in range(size):
self.adjMatrix.append([0 for i in range(size)])
print(self.adjMatrix)
self.size = size
#methods for (1) adding a vertex; (2) adding an edge; (3) removing an edge; and (4) printing the
#matrix should appear here
#remember list indexing - this is 1 out, unless we start the matrix at 0 (not a +ve integer)
def main():
g = Graph(6)
if __name__ == '__main__':
main()