Grid Network Solution - Algorithms - Graphs - Udacity

We can answer this question pretty quickly with the help of a little program. Like before I've got this makelink function, and I'm going to make an empty graph with 256 nodes which is going to be arranged a grid--a number nodes per row and column on a side here is the square root of n or 16. Then what we're going to do is we're going to run through all the pairs of nodes in the graph i, n, j, and for each one if it's not on the very edge, we're going to make a link-- well, if it's not on the bottom edge, then we're going to make a link downward. If it's on the right edge, we're going to make a link to the right. That's going to build our gird. So, we print out the number of edges in this graph that we created and we get 480. We could do that kind of by reasoning as well, that just like in this grid example before the little chain that we have going across is the number of nodes in a column minus 1, and there are five of them because there are five rows. In this case there will be 16 of them. There will be 16 chains of length 15 across. The downward ones are going to be the same, so we'll just double that. We also get 480 that way. It'd be nice to be able to answer this question in a little bit more generality. How many edges do we have in a grid graph? We're assuming that there are n nodes and the nodes are arranged in a square. The picture of that looks like this where you have nodes arranged in a square. For this to make sense, we're assuming that n is a perfect square, so that we can actually arrange the nodes and form a square as so. There's √n nodes on each of the sides, and if we fill in the edges, these green edges, what's the total amount that we get? Well, the same basic idea as we used last time applies. That is, the number of edges that go across in a chain here is going to be √n - 1. That's going to be repeated for each of these rows. And we're going to get the same kind of analysis for the edges that are going down. So, what is that? That's 2n - 2√n. Does that give us the right answer when n is 256? Yes. Well, that's good.