YouTube channel here<\/a> (contains ads). Now, let’s continue.<\/p>\n\n\n\nGraphs are much clear when defined in mathematical terms. A Graph G (V, E)<\/strong>, consists of two sets,<\/p>\n\n\n\n\nSet of Vertices, V<\/strong><\/li>\n\n\n\nSet of Edges, E<\/strong><\/li>\n<\/ul>\n\n\n\nAs the name suggest, V<\/strong>, is the set of vertices or, the set of all nodes in a given graph and E<\/strong>, is the set of all the edges between these nodes, or the associations between them. So, |V|<\/strong> denotes the number of nodes in a graph and |E|<\/strong> denotes the number of edges. Let us take up a small example to understand these terms –<\/p>\n\n\n\n\n\n\t\t\t\n\t\t\t\t\n\t\t\t\n\t\t\t\tAs you can see, we have two types of graphs, Directed<\/strong> and Undirected Graphs<\/strong>. In Undirected <\/strong>Graphs,<\/b> the direction for an edge is not defined. This is generally used to indicate that the edge is actually bi-directional in nature, i.e., one can go from V1<\/sub> \u2192 V2<\/sub>, as well as from V2<\/sub> \u2192 V1<\/sub>. This is used to represent the graph where the states (nodes) are re-doable, such as, in a Rubik’s Cube, you can go from one configuration of the cube to the other as well as the vice-versa.<\/p>\n\n\n\nThe other type, the Directed Graph<\/strong> restricts the… “traversal”, if you say… to only one direction. For example, in the Snakes and Ladders game, you can play dice and go from Position 5 \u2192 Position 10, but you can’t roll the dice such that it gets you from Position 10 \u2190 Position 5… That’s obvious…! So, it really depends on the requirement of the situation, which graph you choose. Generally, we only have to deal with graphs which are purely Directed or purely Undirected. We do not talk about the hybrid type. Some of the other type of graphs are shown below –<\/p>\n\n\n\n\n\n\t\t\t\n\t\t\t\t\n\t\t\t\n\t\t\t\tIn Disconnected Graphs<\/strong>, there will be at least one pair of vertices V1<\/sub> and V2<\/sub> \u2208 V<\/strong>, which doesn’t have a path. In the above example, vertex 2 and 4 are not reachable from each other. Similarly, vertex 1 and 5 are not reachable from each other. In this graph, vertices 1, 2, 3 for a Connected Component<\/strong> and vertices 4, 5, 6, 7 form another Connected Component.<\/p>\n\n\n\nIn Weighted Graphs<\/strong>, the edges are given “weights”. To understand a Weighted Graph, you can think of the vertices as cities and the edges as the distance between them (so they will have some value). You could be asked the shortest path between two cities. So, in the context of a Weighted graph, the shortest path may not be the one with least edges. One must keep that in mind.<\/p>\n\n\n\nThere are plenty of other graph types, like Simple Graphs<\/strong> which do not contain any loops. A loop is an edge from a vertex to itself. The graphs which do contain loops are Non-Simple Graphs<\/strong>.<\/p>\n\n\n\nNow, we will look at the way the graphs are implemented. There are mainly two ways to implement graphs, they are –<\/p>\n\n\n\n
\nAdjacency Matrix<\/li>\n\n\n\n Adjacency List<\/li>\n<\/ul>\n\n\n\nAdjacency Matrix<\/h3>\n\n\n\n It is a very simple representation where we take a two-dimensional matrix of the size |V+1| \u00d7 |V+1|<\/strong>, i.e., the declaration in C would look like,<\/p>\n\n\n\n\nint adjMat[V + 1][V + 1];\n<\/pre><\/pre>\n\n\n\nAs the arrays are zero-indexed, we generally prefer to keep the sizes V + 1<\/em>. Now, initially all the values would be zeroes. We put ‘1’ in an element of the two-dimensional array, adjMat[i][j]<\/em>, if there exists an edge between Vi<\/sub> \u2192 Vj<\/sub>. Remember, arrays are zero-indexed. Let us take an example to understand this,<\/p>\n\n\n\n\n\t\t\t\n\t\t\t\tI hope it is clear from the example, how we can represent the graph using an Adjacency Matrix. It is very easy to code. All you have to do is create a two-dimensional matrix and assign the values. For a weighted graph, all you have to do is assign the weights of the edges instead of assigning value 1 in the cells –<\/p>\n\n\n\n\n\t\t\t\n\t\t\t\tAdjacency List<\/h3>\n\n\n\n It is an array of pointers of size |V| + 1<\/strong>, where each pointer points to a linked list. The linked list holds the nodes which are adjacent to the ith<\/sup><\/strong> vertex. By adjacent, we mean those vertices that can be accessed from ith<\/sup> node by making a single move. It is a little complex implementation if you are uncomfortable with linked lists. But it is this implementation that we will use for Graph Search Algorithms. This is because we can easily and efficiently know which of the vertices of V<\/strong> are neighbors of a given vertex. And that is what you want, if you are to do a Graph Search. Now, let us take an example to understand the concept of Adjacency Lists.<\/p>\n\n\n\n\n\t\t\t\n\t\t\t\tFor the above illustrated graph which has 4 nodes, we create an array of size 5 (for easy 1-indexing), where each element in the array is a pointer to a linked list. Hence, the building block of our Adjacency List is an array of pointers. These pointers will each act as the head pointers of a linked list. Each linked list node is simple, it contains an integer and a next pointer.<\/p>\n\n\n\n\n\t\t\t\n\t\t\t\tLike I stated before, the linked list will hold the list of vertices that are adjacent to the ith<\/sup><\/strong> vertex. From vertex 3, you can go to vertex 2 and 4. Hence the linked list corresponding to vertex 3 in the Adjacency List has elements 2 and 4.<\/p>\n\n\n\nSimilarly, for a weighted graph, we will just have an extra integer in the linked list node to store the weight of the edge –<\/p>\n\n\n\n\n\t\t\t\n\t\t\t\tI hope this makes it clear as to how we use the Adjacency List to implement a Graph. As I mentioned before, it is one of the most versatile implementations of the Graph Data Structure. Now, try to code the implementation in C, or any language you like. Please try this at least once by yourself so that you can get brain deep into the Graph Data Structure. It is only a linked list. And one more thing, don’t get confused between pointer-to-an-array and array-of-pointers…! So, if we put the value of |V| + 1<\/strong> in a variable ‘vertices<\/em>‘, now the declaration of our Adjacency List would be,<\/p>\n\n\n\n\nstruct node * adjacency_list[vertices];\n<\/pre><\/pre>\n\n\n\nRemember this is an “array of pointers”, the declaration for “pointer to an array” would look like,<\/p>\n\n\n\n
\nstruct node (* adjcency_list)[vertices];\n<\/pre><\/pre>\n\n\n\nThis is due to operator precedence. Some people make mistakes here, so, watch out! If you want to code in C++, we can have a vector where each element of the vector can hold another vector or a list, so, the declaration would be, like,<\/p>\n\n\n\n
vector<list<int>> adjacencyList(vertices + 1);<\/code><\/pre>\n\n\n\nTry to code for an hour or two… If you don’t get the code, it’s ok…! I’ve put my C code below. Those who got the code right… You are fabulous…! \ud83d\ude09 … But please take a minute to go through my code, I might have written a slightly better code than yours.<\/p>\n\n\n
C<\/span>Java<\/span>C#<\/span>C++ (STL)<\/span>C++ (STL) (String vertices)<\/span><\/div>
![\"\"](\"https:\/\/i0.wp.com\/theoryofcoding.com\/wp-content\/uploads\/2024\/01\/DirectedGraph.jpg?resize=1024%2C849&ssl=1\")