Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.
We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.
These were just recap questions from the videos asking you to summarize terms. The most interesting one was Question 2.3.
The Adjacency list is optimized to find all the edges going from a node $u$ to other nodes. So we have easy access to all the edges where the starting node is some node $u$. This structure doesn't easily provide information about all nodes that have an edge towards $u$, so we will need to loop through all nodes $v$ and all edges from those nodes $e$ to see which ones have $u$ as a destination. In pseudo-code, the operation over an adjacency list looks something like the following (includes an operation for outNeighbors for comparisons).
outNeighbors(Graph g, Vertex u):
Set<Vertex> result = empty set
for Edge e in g.getOutEdges(u):
result.add(e.destination)
return result
inNeighbors(Graph g, Vertex u):
Set<Vertex> result = empty set
for Vertex v in g:
for Edge e in g.getOutEdges(v):
if e.destination == u:
result.add(v)
return result
This essentially requires a loop over all the vertices (an $\mathcal{O}(n)$ operation) and in total, a loop over all edges (an $\mathcal{O}(m)$ operation). This edge loop is a bit tricky since it's "distributed" over the loop over the nodes, but it will hit each edge once in the total of the whole program. The overall runtime would then be $\mathcal{O}(n + m)$.
The graph is cyclic, since you can get from B, D, or E back to your starting point.
[B→D, D→E, E→B]
This one is a bit tricky. We wouldn't consider it fully connected since it's not possible to get to every node from any start point. If you start at A, you are stuck at A!
We sometimes will call this graph "weakly connected", since it's connected if we consider it as an undirected graph.
This one is a bit tricky since the graph is directed and simple. We can't have a "full connected graph" in the sense that each vertex has an edge to every other vertex, since that would have parallel edges and therefore wouldn't be simple.
Instead, we have to think about a way to count the maximum number of edges while still keeping simplicity. One strategy is to think about this in an iterative process: