Java代写：CSE374AdjacencyList

实现 Adjacency List ，并完成Graph相关算法，比如DFS搜索。

Objectives

1. Understand and use the adjacency-list representation of directed graphs.
2. Implement some graph algorithms.

Preliminaries

• See the starter files DirectedGraph.java and DirectedGraphTester.java provided to you. You will have to write code in the DirectedGraph.java file, according to the instructions provided there. The DirectedGraphTester class contains some basic tests. When grading the project, I may add similar tests for other graphs.
• See the file ExpectedOutput.txt, which contains the expected output when running the tests provided in the DirectedGraphTester class.

Tasks

Implement the following methods in the DirectedGraph class according to the
instructions provided in the Java file DirectedGraph.java:

• Constructor
• addEdge(int u, int v)
• transpose()
• DFS()
• DFSVisit(int u)
• isAcyclic()
• topologicalSort()
• toString()
• showDFSResults()

Some Key Points

• Use the pseudocode below for DFS() and DFSVisit(int u). When you implement these methods, use d[u] instead of u.d and similarly for color, f, and , as indicated in the DirectedGraph.java file. Instead of , use p.
• Modify the code for DFS() to create a linked list called order. In DFSVisit(int u), the last line of code should add vertex u to the front of the linked list called order.
• To determine whether a graph is acyclic you would have to run the DFS algorithm which calculates the timestamps d and f for discovery and finishing time of all vertices, respectively. A graph contains cycles if and only if there is an edge (u, v) such that d[v] [ d[u] and f[u] [ f[v]. Such edges are called “back edges”. A graph that does not contain back edges is acyclic. Acyclic means that the graph does not contain cycles.

Expected Output

If you correctly implemented all the methods in DirectedGraph.java, then
running the tester DirectedGraphTester should print out the following output
(also included in the file ExpectedOutput.txt provided to you):
***********
G:
(0, 1)
(0, 2)
(1, 2)
(2, 4)
(3, 4)
Is G acyclic? true
***********
G:
(0, 1)
(0, 2)
(1, 2)
(2, 4)
(2, 0)
(3, 4)
Is G acyclic? false
***********
G:
(0, 1)
(0, 2)
(1, 2)
(2, 4)
(3, 4)
DFS Results (d/f p)
1/8 null
2/7 0
3/6 1
9/10 null
4/5 2
***********
G:
(0, 1)
(0, 2)
(1, 2)
(2, 4)
(3, 4)
DFS Results (d/f p)
1/8 null
2/7 0
3/6 1
9/10 null
4/5 2
***********
G:
(0, 1)
(0, 2)
(1, 2)
(2, 4)
(3, 4)
Transpose of G:
(1, 0)
(2, 0)
(2, 1)
(4, 2)
(4, 3)
***********
G:
(0, 1)
(0, 2)
(1, 2)
(2, 4)
(2, 0)
(3, 4)
Transpose of G:
(0, 2)
(1, 0)
(2, 0)
(2, 1)
(4, 2)
(4, 3)
***********
G:
(0, 1)
(0, 2)
(1, 2)
(2, 4)
(3, 4)
Topological Sort: 3 0 1 2 4
***********
G:
(0, 1)
(0, 2)
(1, 2)
(2, 4)
(2, 0)
(3, 4)
Topological Sort: The graph contains cycles and therefore no topological order exists.

What to Submit

1. Go to the folder where your eclipse workspace is saved (e.g., “C:\eclipse-workspace”) and find the folder associated with your project. Zip up all the contents in your project and submit the zip archive to Canvas. The zip file should include the java file that you modified plus the tester provided to you:
   * Implemented DirectedGraph.java file
   * DirectedGraphTester.java