Graph Representation. There is a weighted undirected graph in Fig. 3. There are
ID: 3817357 • Letter: G
Question
Graph Representation. There is a weighted undirected graph in Fig. 3. There are five nodes, A, B, C, D, and E. The value beside each edge is its weight. Now you are required to draw the adjacency list for this graph. For each nodes, its linked nodes in the adjacency list should be arranged in alphabetical order There is a weighted directed graph in Fig. 4. There are five nodes, A, B, C, D, and E. The value beside each edge is its weight. The arrow on each edge indicates its direction. Now you are required to draw the adjacency list for this graph. For each nodes, its linked nodes in the adjacency list should be arranged in an alphabetical orderExplanation / Answer
Adjacency list denoates the graph using the array or list of directly connecting nodes to a perticular node.
For your first Question, it is a weighted undirected graph. Thus every link is bi-directional, thus if A and B has a link in between, A links to B and Vice Versa is also true.
1) As you can see in graph:
A is connected to B, E, D with respective weights or costs, list for A in alphabetical order is [B,5],[D,6],[E,2]
Similarly for:
B :[A,5],[C,3],[D,4]
C:[B,3],[D,8]
D:[A,6],[B,4],[C,8],[E,7]
E:[A,2],[D,7]
2) Your 2nd Graph is a directed graph and if there is a link between A and B directing from A to B, the B is called Adjacent to A but Vice Versa is not true.
A is connected to B, E, D with respective weights or costs and directed links to them, list for A in alphabetical order is [B,5],[D,6],[E,2]
Similarly for:
B (It has no outgoing link, thus no adjacent elements exists for B) :NULL
C:[B,3],[D,8]
D (Only Outgoing link is to B, thus B is Adjacent to D):[B,4]
E (Outgoing link to D):[D,7]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.