A graph is a non-linear data structure, which comprises vertices connected by edges. An edge may...

 

Transcribed Image Text:

A graph is a non-linear data structure, which comprises vertices connected by edges. An edge may be directed or undirected. Graph theory has a huge application in a plethora of fields. For example, Wang et al. (2020) uses the improved Dijkstra's algorithm to seek the shortest paths between node pairs in large-scale bridge network. Wen et al. (2020) analyses e-mail account probing attack based on graph mining. Google maps adopted graphs for constructing its transportation system. The navigation system finds the shortest path between two cities using graph algorithms. Suppose the graph shown in Fig.1 depicts a network of urban transportation system, where each vertex denotes a city and edges are roads connecting each neighbourhood cities. The weights on the edges represent the travel distance. S B 2 Figure 1: A sample graph. E 2 F Figure 1: A sample graph. (a) Construct an adjacency list representation for the graph shown in Fig.1. i. Dijkstra's algorithm. ii. Bellman-Ford's algorithm. (b) Another possible directed graph representation is the multilinked list representation. The representation is very similar to (a). However, instead of array, a linked list is adopted. Draw the multilinked list representation for the graph in Fig. 1. Hints: The list that replace the array is made up of double linked list. Each node comprises the (1) data (vertex), (2) a pointer to a list of edges, and (3) a pointer to the next vertex. The list of adjacent vertices is replaced by a list of edges made up of edges that emanate (outgoing) from the node. A node of edge comprises (1) pointer to the node that the edge terminates, and (2) pointer to the next edge. (c) Simulate the following algorithms to obtain the shortest path starting with city S (aka. source) to the other cities. Show your steps. A graph is a non-linear data structure, which comprises vertices connected by edges. An edge may be directed or undirected. Graph theory has a huge application in a plethora of fields. For example, Wang et al. (2020) uses the improved Dijkstra's algorithm to seek the shortest paths between node pairs in large-scale bridge network. Wen et al. (2020) analyses e-mail account probing attack based on graph mining. Google maps adopted graphs for constructing its transportation system. The navigation system finds the shortest path between two cities using graph algorithms. Suppose the graph shown in Fig.1 depicts a network of urban transportation system, where each vertex denotes a city and edges are roads connecting each neighbourhood cities. The weights on the edges represent the travel distance. S B 2 Figure 1: A sample graph. E 2 F Figure 1: A sample graph. (a) Construct an adjacency list representation for the graph shown in Fig.1. i. Dijkstra's algorithm. ii. Bellman-Ford's algorithm. (b) Another possible directed graph representation is the multilinked list representation. The representation is very similar to (a). However, instead of array, a linked list is adopted. Draw the multilinked list representation for the graph in Fig. 1. Hints: The list that replace the array is made up of double linked list. Each node comprises the (1) data (vertex), (2) a pointer to a list of edges, and (3) a pointer to the next vertex. The list of adjacent vertices is replaced by a list of edges made up of edges that emanate (outgoing) from the node. A node of edge comprises (1) pointer to the node that the edge terminates, and (2) pointer to the next edge. (c) Simulate the following algorithms to obtain the shortest path starting with city S (aka. source) to the other cities. Show your steps.

Answer rating: 100% (QA)

Answer i include using namespace std include Number of vertices in the graph define V 9 A utility fu... View the full answer