Computer Science Graph Question and Answer

Question 1. Consider the above graph G = (V, E) representing air flight network. Where V represents set of vertices of graph, each vertex represents an airport, and E represents set of edges, edge represents flight routes from one airport to another. The weights (numbers) on each edge represents distance from one airport to another.

A. Represent the given air flight network using adjacency matrix and adjacency list.

B. Discuss the advantages and disadvantages of representing the above flight network using adjacency matrix and adjacency list when considering that following operations are to be performed on flight network.
1. Add airport in flight network
2. Remove airport from flight network
3. Add route in flight network
4. Remove route from flight network
1. Adding airport in flight network

If we will add an airport then we have to add one node in the graph, for adding a node in adjacency matrix we have to create a new matrix of size greater than one of previous matrix which takes O( n * n ) time complexity and if we have to add a new node in adjacency list then we have to just increase the size of adjacency list by one so the Time Complexity in this case will be just O( 1 ).

2. Removing airport from flight network

Removing the airport from the flight network will take the same performance as adding an airport from adjacency matrix and adjunct list respectively. In this case we have to reduce the size of adjacency matrix and adjacency list instead of increase.

3. Adding route in flight network

To add a route between two airports, we have to add an edge between the two airports of the graph. Adding a new edge in adjacency matrix representation of matrix, we have to just modify one variable of the matrix, i.e. if we have to add edge between node A and node B and the distance between A and B is C then we have to change the value of matrix[A][B] to C from 0. Which takes O(1) Time complexity. To an edge in adjacency list representation of the graph we need to add a new node in node A as well as node B, which takes O(n) Time complexity in the worst case.

4. Removing route from flight network

Removing an edge from the graph takes the same time complexity as adding in the graph. In the adjacency matrix we have to change matrix[A][B] from C to 0 and in the adjacency list we have to remove node A from node B and node B from node A.

C. Traverse the given flight network using breadth first traversal (BFS) and depth first traversal (DFS).

There may be multiple arrangements of nodes in the BFS or DFS traversal of a graph.
We are starting traversal from node A of graph.

One of the BFS traversal of the graph:
A
B-> F-> D
C-> E
One of the DFS traversal of the graph:
A -> B -> D -> E -> C -> F

D. Discuss any two differences obtained/observed when traversing the flight network using breadth first traversal and depth first traversal techniques.

In BFS traversal the traverse proceeds level by level, first the start node is traversed then its adjacent nodes are traversing and so on until all nodes of the graph are visited.

In DFS traversal follow first a path from the starting node to ending node then another path from start to end until all nodes are visited.

Share: