Questions Tagged With graphshttps://inoi15.discuss.codechef.com/tags/graphs/?type=rssquestions tagged <span class="tag">graphs</span>enSun, 04 Jan 2015 16:24:04 +0530Adjacency lists & Adjacency matriceshttps://inoi15.discuss.codechef.com/questions/60720/adjacency-lists-adjacency-matrices<p>I recently implemented DFS by making an adjacency list using a vector of vectors and was pretty pleased about that. But yesterday, I read here <a> </a><a href="http://web.stanford.edu/class/cs97si/">http://web.stanford.edu/class/cs97si/</a> on the basic Graph algorithms slide that an array of vectors is slower than plain arrays.</p>
<p>For me, vectors of vectors was pretty easy to code but just arrays was hard as I had trouble just adding an edge and manipulating the 2 arrays. What do the rest of you recommend me to use taking into account time and memory efficiency? If you recommend arrays, could you also give me a good resource which explains how to easily implement it?</p>
<p>Also, I read that we should use an adjacency matrix only when the graph is dense (No. of vertices is almost equal to no. of edges). But what if the constraints (around 10^5 edges) are such that it is too large even for the global scope? What do I use to represent the edge relations in such a case?</p>sandy999Sun, 04 Jan 2015 16:24:04 +0530https://inoi15.discuss.codechef.com/questions/60720/adjacency-lists-adjacency-matricesgraphsNeed some graph theory problemshttps://inoi15.discuss.codechef.com/questions/60648/need-some-graph-theory-problems<p>What are some good problems to do for Graph Theory for preparation of INOI ?</p>nibnalinSun, 04 Jan 2015 00:22:33 +0530https://inoi15.discuss.codechef.com/questions/60648/need-some-graph-theory-problemsgraphsproblemsinoiinoi2015