How the adjacency list data structure can represent a weighted graph.
Weighted Graphs have edges with a numerical value assigned called a Weight to each edge. Typically the values of each edge are positive rather than negative. An example of a Weighted Graph is finding the shortest path using the weights such as A to D. The total weight of a path is the sum of the weights of its edges. There is an algorithm called Dijkstra’s algorithm that can find the shortest path between nodes in the graph. There are three main ways to represent a weighted graph which are Edge List, Adjacency List and Adjacency Matrix. This graph can be associated with certain problems such as graph traversal, shortest path, minimum spanning tree, topological sort and travelling salesman. The purpose of Weighted Graphs is to find out certain weights such as a measure of the length of a route, the capacity of a line or the energy required to move between locations along a route.
Adjacency Lists uses array of lists, the size of the array is same as the number of vertices. The certain weights of each edge can be represented as lists of pairs. Each list can show you the nodes that are next to it. In python a simple dictionary of vertices and its edges is a very good representation of a graph. Also if the nodes are represented by objects, then they have a value and a neighbour field to hold the node’s value. If you want easy access to a node’s neighbours, you could simply store them with the node.
There are three things needed to insert an edge for a weighted graph using an Adjacency List. The first one is allocate the edge, then put in the data, then add it to the dictionary. Below is an example of the above function and one possible way of adding an edge to a weighted graph. First I have created a class, then I created a function which will show all the edges in the graph. The next function will add edges to the graph and then the last function find all the edges within the graph. Then I drew the graph showing how many edges and vertices there will be and what will be adjacent to each other. Last of all, I have collated all functions to run the code to add an edge.
Adjacency List and Adjacency Matrix are two different ways of implementing weighted graphs. Vertex numbers in an adjacency list do not need to appear in a certain order, but it is better to list them in increasing order. You can get to each vertex’s adjacency list in constant time, because you just have to index into an array. An adjacency list is efficient when talking about storage because you only need to store the values for the edges. For a sparse graph with millions of vertices and edges, this can mean a lot of saved space.With an adjacency matrix, we can find out whether an edge is present in constant time, by just looking up the corresponding entry in the matrix. In a Adjacency it takes more space than an Adjacency List, even if the graph is sparse which has fewer edges. For a sparse graph the Adjacency Matrix is mostly 0’s, and it uses a lot of space to represent only a few edges. Also, if you want to find out which vertices are adjacent to a given vertex, you have to look at all vertical bars even if only a small number of vertices are adjacent to the vertex. The advantages of the adjacency matrix is that it is quite a simple way of representing small graphs and graphs that have a lot of edges. Also it is very easy to see which corresponding nodes are connected to other nodes. As there is only one row and one column for every vertex in the graph, the number of edges required to fill the matrix doesn’t matter too much.
References:
https://dsaa.werp.site/post/graphs/
https://www.geeksforgeeks.org/graph-and-its-representations/
Liam's Blog 