Description
Please complete the homework problems on the following page using a separate piece of paper. Note that this is an individual assignment and all work must be your own. Be sure to show your work when appropriate.
1. [13] Define these terms as they relate to graph and graph algorithms:
Use mathematical terms where appropriate.
Graph ______________________________________________________________
Vertice ____________________________________________________________
Edge _______________________________________________________________
Undirected Graph ___________________________________________________
Directed Graph _____________________________________________________
Path _______________________________________________________________
Loop _______________________________________________________________
Cycle ______________________________________________________________
Acyclic ____________________________________________________________
Connected __________________________________________________________
Sparse _____________________________________________________________
Weight _____________________________________________________________
2. [4] Under what circumstances would we want to use an adjacency matrix instead of an adjacency list to store our graph?
3. [6] Name three problems or situations where a graph would be a good data structure to use:
4. [4] What kind of graph is this?
5. [4] Identify the loop in this graph:
6. [4] How many vertices and edges are in this graph:
|
|
Vertices ______________________ Edges _________________________ |
7. [6] Are these cyclic or acyclic graphs?
|
|
Cyclic? Yes No |
|
|
Cyclic? Yes No |
|
|
Cyclic? Yes No |
8. [5] A tree is a particular kind of graph. What kind of graph is that?
9. [4] What is the difference between a breadth-first search and a depth first search?
10. [10] Dijkstra’s Algorithm. Use Dijkstra’s Algorithm to determine the shortest path starting at A. Note that edges without heads are bi-directional. To save time, you do not have to add items to the “priority queue” column after it has been discovered (listed in the “distance” column). Use the table below to show your work.
What’s the shortest route (by weight) from A to C? ___________________________________
|
Node: Distance |
Priority Queue |
11. [10] Topo sort. Show the final output of running Topo Sort on this graph:
 |
What’s the vertice with the largest degree and its value?
What’s the vertice with the highest outdegree and its value? |
Topo sort output:
