This course is the fourth course in the specialization about learning how to develop video games using the C# programming language and the Unity game engine on Windows or Mac. Why use C# and Unity instead of some other language and game engine? Well, C# is a really good language for learning how to program and then programming professionally. Also, the Unity game engine is very popular with indie game developers; Unity games were downloaded 16,000,000,000 times in 2016! Finally, C# is one of the programming languages you can use in the Unity environment. This course assumes you have the prerequisite knowledge from the previous three courses in the specialization. You should make sure you have that knowledge, either by taking those previous courses or from personal experience, before tackling this course. The required prerequisite knowledge is listed in the "Who this class is for" section below. Throughout this course you'll build on your foundational C# and Unity knowledge by developing more robust games with better object-oriented designs using various data structures and design patterns. Data structures and design patterns are both general programming and software architecture topics that span all software, not just games. Although we'll discuss these ideas in the game domain, they also apply if you're writing a web app in ASP.NET, building a tool using WinForms, or any other software you decide to build. Module 1: Explore a Dynamic Array data structure and learn the basics of algorithm analysis Module 2: Learn about and use the common Linked List and Graph data structures Module 3: Learn about and use several additional data structures: Stacks, Queues, and Trees Module 4: Learn why design patterns are so useful and discover a number of design patterns useful in game development Module 5: Complete final peer review “Unity” is a trademark or registered trademark of Unity Technologies or its affiliates in the U.S. and elsewhere. This course is an independent work and is not sponsored by, authorized by, or affiliated with Unity Technologies or its affiliates
Graph Analysis
Loading...
From the course by University of Colorado System
Data Structures and Design Patterns for Game Developers
13 ratings
University of Colorado System
13 ratings
Course 4 of 5 in the Specialization C# Programming for Unity Game Development
From the lesson
Linked Lists and Graphs
Meet the Instructors
Dr. Tim "Dr. T" ChamillardAssociate Professor
Computer Science
In this lecture, we'll complete
our algorithm analysis for our graph and graph node classes.
We'll start by analyzing the complexity of the GraphNode operations.
So, we'll scroll down to adding a neighbor.
The neighborsContains method which is a list method is order n,
where n is the number of items in the list.
This is constant time.
Adding a neighbor is either order one if we don't have to expand the list,
or order n if we do have to expand the list.
And this is constant time.
But this we know is always order n. So,
the AddNeighbor operation is order n,
where n is defined as the number of neighbors for the node.
Removing a neighbor is also order n because the list remove
method is order n. It does a linear search to find the neighbor to remove,
so in the worst case it goes all the way to the end before finding the neighbor,
or not finding the neighbor.
So, the Remove method is an order n method.
So, the RemoveNeighbor operation for GraphNode is also order n.
Removing all neighbors is order n.
The RemoveAt method because we're removing from the end of the list,
I've written this for loop to go backwards not forwards,
so we're removing from the end of the list each time,
and that's a constant time operation because nothing in
the list has to get shifted around once we remove the GraphNode.
So, the body of the loop is order one,
but this for loop executes n times.
So, the RemoveAllNeighbors operation is
order n because we need to remove each of those neighbors,
so it's a order n, where n is defined as the number of neighbors.
The ToString method is also order n,
where n is the number of neighbors because of this for loop that executes n times,
once for each neighbor.
For the graph, it is common for people to specify complexities for graphs using V,
for the number of vertices in the graph and E,
for the number of edges in the graph.
So, even though we have typically been talking about order n,
where n would be say,
the number of nodes in the graph,
we'll be consistent with common convention for graphs and we'll express our complexities
in terms of V. And I'll point out
one place where E might give us a better result, when we get there.
So, we'll start with the Clear method.
The RemoveAllNeighbors method for a GraphNode is order n,
where n is the number of neighbors.
But in the worst case,
a node could be connected to all other nodes in the graph, including itself.
So, in the worst case,
n is actually V,
the number of vertices in the graph.
So, the body of this first loop is order V.
We also are going to iterate over all the vertices or nodes in the graph.
So, this outer loop is order V as well.
The way we calculate the complexity for this loop as a whole,
is we take the complexity of the loop body,
and we multiply it by the complexity of the loop itself.
And we do that because for each iteration,
we might get the worst case here.
So, this is order V,
and this is order V,
so this is actually order V squared,
V times V is V squared.
This bottom for loop,
the list RemoveAt method because we're removing from the end again,
going backwards, is constant time.
So, constant time times order V,
because this touches every vertex in the graph.
So, this loop is order V. So,
we have an order V squared loop and an order V loop,
so the complexity of the Clear operation is order V squared,
because V squared dominates V and we can just throw the V away.
Now, the worst case for removing all neighbors is
actually based on the fact that this is what's called the dense graph.
So, there are lots of edges relative to the number of nodes or vertices in the graph.
In a sparse graph,
where we have fewer edges,
this is really pessimistic because in fact,
this can't be V in the sparse graph,
it's going to be much smaller than that.
So, one other way we can think about this,
is this inner loop is order E overall.
In the worst case through all of the iterations of this outer loop,
we're going to do two E removals,
because the edge is actually contained in both nodes to connect to the other node.
So, if we want to be a little more precise,
we can say this first loop is order V times E,
instead of order V squared,
and so that's a little more fair for sparse graphs.
For the rest of our discussion here,
I'm just going to express everything in terms of V
because that is generally applicable to all graphs whether it's sparse or dense.
But you should recognize the fact that for sparse graphs,
including an E term for the number of edges in the graph can give
you a tighter upper bound on the complexity of doing stuff on the graph.
To add a node, we'll actually discover that
the Find method is order V once we go analyze that.
So, order V, constant time.
Adding to the list is either order one if we don't have to expand the list,
or order V if we do.
And then this is constant time.
So, this is clearly the dominant factor,
it's order V. So,
adding a node to the graph is order V. Adding an edge between two nodes,
I just said that the Find operation or method is order V. So,
these first two lines are order V. And then we have some constant time stuff.
And then checking a neighbor to see if that edge already exists is in fact,
order V in the worst case.
For a complete graph,
we'd have to work a list of neighbors that
contained V different entries for all the nodes in the graph.
So, this is also order V. And this is constant time.
So, we saw this before when we added a neighbor to a GraphNode.
That if we needed to expand that list of neighbors then it was order n,
where n is the number of neighbors.
And here for a complete graph or even a dense graph,
we're going to say this is order V. So,
we have a bunch of order V's but none of them are nested inside another one.
So, there's no multiplication here,
there's just a bunch of adding.
So the AddEdge operation is
order V. For the RemoveNode operation or method,
this is order V. We have a bunch of constant time stuff.
Removing an item from the list is order V because
the list Remove method does a linear search for that item to remove.
So, NodeRemoveNeighbor is order n,
where n is the number of neighbors for the node.
So, we'll say order V for a dense or complete graph.
So, the body of this loop is order V. And the loop executes V times,
one for each vertex or node in the graph.
So, we have to multiply this order V by this order V,
which tells us that the RemoveNode operation is order V squared.
Removing an edge, order V. Order V, constant time.
Order V, constant time.
Removing each neighbor is order V as well.
And because all these order V's are added together,
the RemoveEdge operation is
order V. The Find simply does a linear search of the GraphNodes.
So, this is order V because this loop executes in the worst case, the times.
And finally, converting to a string is also order V
because we convert each node in the graph to a string.
To recap, in this lecture,
we got more algorithm analysis practice.
We discovered that the complexity of algorithms
on graphs are regularly expressed using V,
the number of vertices in a graph.
And we also learned that using both V and E,
the number of edges in a graph,
can give us a tighter bound on the complexity for some algorithms on sparse graphs.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
