Question

Describe a software application that would require a graph data structure in its implementation. Explain what the vertices and edges of the graph would represent. Would the graph be undirected or directed? Would it be weighted or unweighted? Decide which type of representation would be best for this application, an adjacency matrix, an adjacency list using an array of linked lists or a fully linked representation. Explain your reasoning.

Answer 1

when the question is related on any of the software product based on graph theory

the foremost thing that comes to my mind is the Google Map Technology. Web based map and

graph theory are inevitable.The role of graph theory in any web based map is very much prominent .

In google map routes between the cities are represented using graphs.The places are considered as vertices and routes as edges.

Dijkstra's Algorithm can be used to find the shortest route between two places as long as there is at least one possible route.

The graph would be directed (since route has a fixed direction) and weighted. The weight on each edge will signify the distance between two places or two vertices.

This algorithm uses adjacency matrix to calculate the shortest path between source and destination.

While implementing this algorithm we use array of link list because every time the link list will be updated to find the shortes route.

THANK YOU!!! PLEASE VOTE