{"id":1330,"date":"2015-06-08T05:33:42","date_gmt":"2015-06-08T05:33:42","guid":{"rendered":"https:\/\/theoryofprogramming.wordpress.com\/?page_id=1330"},"modified":"2015-06-08T05:33:42","modified_gmt":"2015-06-08T05:33:42","slug":"adjacency-list-using-cpp-stl","status":"publish","type":"page","link":"https:\/\/theoryofcoding.com\/index.php\/adjacency-list-using-cpp-stl\/","title":{"rendered":"Adjacency List using C++ STL"},"content":{"rendered":"<p>Hello people..! This is a special extension for my discussion on <strong><a href=\"http:\/\/theoryofprogramming.azurewebsites.net\/2014\/12\/24\/graph-theory-an-introduction\/\">Graph Theory Basics<\/a><\/strong>. Here, I give you the code for implementing the Adjacency List using C++ STL. Some of the features of this code are &#8211;<\/p>\n<ul>\n<li>The Adjacency List is a vector of list, where each element is a pair, from the utility header file. This pair stores two values, the destination vertex, (V<sub>2<\/sub> in an edge V<sub>1<\/sub> \u2192 V<sub>2<\/sub>) and the weight of the edge.<\/li>\n<li>For adding an edge, all we have to do is to call push_back() function. Although it does not represent our addEdge() in the initial discussion where we had head insertion, it is tail insertion which is an O(1) insertion operation.<\/li>\n<li>The vector representing the vertices is 1-indexed.<\/li>\n<\/ul>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\n\/*\n * Adjacency List for\n * Directed Weighted Graph\n * Code using C++ STL\n * \n * Authored by,\n * Vamsi Sangam.\n *\n *\/\n\n#include &lt;cstdio&gt;\n#include &lt;vector&gt;\n#include &lt;list&gt;\n#include &lt;utility&gt;\n\nusing namespace std;\n\nint main()\n{\n\tint vertices, edges, v1, v2, weight;\n\t\n\tprintf(&quot;Enter the Number of Vertices -\\n&quot;);\n\tscanf(&quot;%d&quot;, &amp;vertices);\n\t\n\tprintf(&quot;Enter the Number of Edges -\\n&quot;);\n\tscanf(&quot;%d&quot;, &amp;edges);\n\t\n\t\/\/ Adjacency List is a vector of list.\n\t\/\/ Where each element is a pair&lt;int, int&gt;\n\t\/\/ pair.first -&gt; the edge's destination\n\t\/\/ pair.second -&gt; edge's weight\n\tvector&lt; list&lt; pair&lt;int, int&gt; &gt; &gt; adjacencyList(vertices + 1);\n\t\n\tprintf(&quot;Enter the Edges V1 -&gt; V2, of weight W\\n&quot;);\n\t\n\tfor (int i = 1; i &lt;= edges; ++i) {\n\t\tscanf(&quot;%d%d%d&quot;, &amp;v1, &amp;v2, &amp;weight);\n\t\t\n\t\t\/\/ Adding Edge to the Directed Graph\n\t\tadjacencyList&#x5B;v1].push_back(make_pair(v2, weight));\n\t}\n\t\n\tprintf(&quot;\\nThe Adjacency List-\\n&quot;);\n\t\/\/ Printing Adjacency List\n\tfor (int i = 1; i &lt; adjacencyList.size(); ++i) {\n\t\tprintf(&quot;adjacencyList&#x5B;%d] &quot;, i);\n\t\t\n\t\tlist&lt; pair&lt;int, int&gt; &gt;::iterator itr = adjacencyList&#x5B;i].begin();\n\t\t\n\t\twhile (itr != adjacencyList&#x5B;i].end()) {\n\t\t\tprintf(&quot; -&gt; %d(%d)&quot;, (*itr).first, (*itr).second);\n\t\t\t++itr;\n\t\t}\n\t\tprintf(&quot;\\n&quot;);\n\t}\n\t\n\treturn 0;\n}\n<\/pre>\n<p>Feel free to comment if you have any doubts..! Keep practicing..! Happy Coding..! \ud83d\ude00<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Hello people..! This is a special extension for my discussion on Graph Theory Basics. Here, I give you the code for implementing [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"jetpack_post_was_ever_published":false,"footnotes":""},"class_list":["post-1330","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/pages\/1330","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/comments?post=1330"}],"version-history":[{"count":0,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/pages\/1330\/revisions"}],"wp:attachment":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/media?parent=1330"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}