Question

Describe a graph abstraction (e.g., the world-wide-web can be modeled as a graph where vertices are web pages and edges are hot-links). Describe one not discussed in the course material. For this graph, describe the meaning of a shortest hop path, diameter, and degree.

Answer 1

Graph-Is is one of the data structure in a computer science subject.

Graph abstraction is basically the reading of a graph in a way that we can classify the different data points in particular sections. The graph data structure has two types Directed and undirected. For the directed graph, the edges are known as the arrows.

In this example, it is mentioned that the world wide web is a graph where the web pages are vertices and the edges are hot-links. Shortest hop path is the path connecting between two vertices,Diameter is the maximum eccentricity of any vertex in a graph, that is it is the greatest distance between any pair of vertices. A degree is the number of edges incident on the vertex.

This graph is basically the internet in which we can search for anything we want there might be connecting link between two webpages it depends on the information we are searching for. We can take two vertices first, one having connecting link with others so it will be directed to the vertex and the other is single, it depends wholly on the type of search we do.

For finding the shortest path there are many algorithms like

Dijkstra's algorithm solves the single-source shortest path problem with non-negative edge weight.
Bellman–Ford algorithm solves the single-source problem if edge weights may be negative.
A* search algorithm solves for single pair shortest path using heuristics to try to speed up the search.
Floyd–Warshall algorithm solves all pairs shortest paths.
Johnson's algorithm solves all pairs shortest paths, and may be faster than Floyd–Warshall on sparse graphs.
Viterbi algorithm solves the shortest stochastic path problem with an additional probabilistic weight on each node.