Graphs are one of the most versatile structures used in computer programming. In this lab, we discuss the algorithms associated with unweighted graphs.
At the end of this lab, you need to submit a word document including some text answers and screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start->All Programs->Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).
1. Operations on GraphN.html
(1.) Click Start > Windows System -> Command Prompt. Use command "cd" to move into the directory where you run the applet, such as cd C:COSC3333Chap11GraphN. Then use the command appletviewer GraphN.html to run the application, see Figure 1. see image.
(2.) Use Double-click to create new vertex, and Drag from vertex to vertex to create edge, you need to create Figure 2. Q1: How many nodes in this Graph, how many edges in this Graph? Q2: If you drag from vertex A to B to create edge (A, B), could you create another edge (B, A) from vertex B to A? see image.
(3.) Click View to show the adjacency matrix of this graph, we have Figure 3. Click View again to switch it back. Q3: Is the matrix symmetric based on diagonal line? see image.
(4.) Click DFS to run the Depth First Search for this tree starting from vertex A, finally you have Figure 4. Q4: What is the vertex visited sequence for DFS? see image.
(5.) Click BFS to run the Breadth First Search for this tree starting from vertex A, finally you have Figure 5. Q5: What is the vertex visited sequence for BFS? see image.
(6.) Click Tree to run the algorithm of finding the minimal spanning tree for this tree starting from vertex A, finally you have Figure 6. Q6: What is the algorithm it used for finding the minimal spanning tree, DFS or BFS? see image.
2. Operations on GraphD.html
(1.) Change directory by type the command "cd ..GraphD", then use the command appletviewer GraphD.html to run the application, see Figure 7. see image.
(2.) Use Double-click to create new vertex, and Drag from vertex to vertex to create edge, we have Figure 8. Q7: How many nodes in this Graph, how many edges in this Graph? see image.
(3.) Click View to show the adjacency matrix of this graph, we have Figure 9. Click View again to switch it back. Q8: Is the matrix symmetric based on diagonal line? see image.
(4.) Click Topo to run the algorithm of topological sort, finally you have Figure 10. Q9: What is the list of the topological sort for this graph? see image.
Q1: How many nodes in this Graph, how many edges in this Graph?
Q2: If you drag from vertex A to B to create edge (A, B), could you create another edge (B, A) from vertex B to A?
Q3: Is the matrix symmetric based on diagonal line?
Q4: What is the vertex visited sequence for DFS?
Q5: What is the vertex visited sequence for BFS?
Q6: What is the algorithm it used for finding the minimal spanning tree, DFS or BFS?
Q7: How many nodes in this Graph, how many edges in this Graph?
Q8: Is the matrix symmetric based on diagonal line?
Q9: What is the list of the topological sort for this graph?
Submit the screenshots for Figure 2 to Figure 6 and Figure 8 to 10 (totally 8 figures) through Blackboard. (Don't forget to include your name in the program). (At the end of this lab, you need to submit a word document including some screenshots of your lab result. The way to get the screen shots is to press Key "Print Screen" from your keyboard to get the image of the whole screen, then use Start- >All Programs->Accessories->Paint, click Edit->Paint to get the image, use text to add your own name (to replace Qi Zhu), then cut and paste the part of image you want into your homework file such as .doc).