Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5095726

Browse files
author
jsquared21
committed
Add Ex 28.01
1 parent8ac4506 commit5095726

12 files changed

+436
-0
lines changed
472 Bytes
Binary file not shown.
2.2 KB
Binary file not shown.
5.21 KB
Binary file not shown.
Lines changed: 291 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,291 @@
1+
importjava.util.*;
2+
3+
publicabstractclassAbstractGraph<V>implementsGraph<V> {
4+
protectedList<V>vertices =newArrayList<>();// Store vertices
5+
protectedList<List<Edge>>neighbors =newArrayList<>();// Adjacendy lists
6+
7+
/** Construct an empty graph */
8+
protectedAbstractGraph() {
9+
}
10+
11+
/** Construct a graph from vertices and edges stored in arrays */
12+
protectedAbstractGraph(V[]vertices,int[][]edges) {
13+
for (inti =0;i <vertices.length;i++)
14+
addVertex(vertices[i]);
15+
16+
createAdjacencyLists(edges,vertices.length);
17+
}
18+
19+
/** Construct a graph from vertices and edges stored in List */
20+
protectedAbstractGraph(List<V>vertices,List<Edge>edges) {
21+
for (inti =0;i <vertices.size();i++)
22+
addVertex(vertices.get(i));
23+
24+
createAdjacencyLists(edges,vertices.size());
25+
}
26+
27+
/** Construct a graph for integer vertices 0, 1, 2 and edge list */
28+
protectedAbstractGraph(List<Edge>edges,intnumberOfVertices) {
29+
for (inti =0;i <numberOfVertices;i++)
30+
addVertex((V)(newInteger(i)));// vertices is {0, 1, ...}
31+
32+
createAdjacencyLists(edges,numberOfVertices);
33+
}
34+
35+
/** Construct a graph from integer vertices 0, 1, and edge array */
36+
protectedAbstractGraph(int[][]edges,intnumberOfVertices) {
37+
for (inti =0;i <numberOfVertices;i++)
38+
addVertex((V)(newInteger(i)));// vertices is {0, 1, ...}
39+
40+
createAdjacencyLists(edges,numberOfVertices);
41+
}
42+
43+
/** Create adjacency lists for each vertex */
44+
privatevoidcreateAdjacencyLists(
45+
int[][]edges,intnumberOfVertices) {
46+
for (inti =0;i <edges.length;i++) {
47+
addEdge(edges[i][0],edges[i][1]);
48+
}
49+
}
50+
51+
/** Create adjacency lists for each vertex */
52+
privatevoidcreateAdjacencyLists(
53+
List<Edge>edges,intnumberOfVertices) {
54+
for (Edgeedge :edges) {
55+
addEdge(edge.u,edge.v);
56+
}
57+
}
58+
59+
@Override/** Return the number of vertices in the graph */
60+
publicintgetSize() {
61+
returnvertices.size();
62+
}
63+
64+
@Override/** Return the vertices in the graph */
65+
publicList<V>getVertices() {
66+
returnvertices;
67+
}
68+
69+
@Override/** Return the object of the specified vertex */
70+
publicVgetVertex(intindex) {
71+
returnvertices.get(index);
72+
}
73+
74+
@Override/** Return the index for the specified vertex object */
75+
publicintgetIndex(Vv) {
76+
returnvertices.indexOf(v);
77+
}
78+
79+
@Override/** Return the neighbors of the specified vertex */
80+
publicList<Integer>getNeighbors(intindex) {
81+
List<Integer>result =newArrayList<>();
82+
for (Edgee :neighbors.get(index)) {
83+
result.add(e.v);
84+
}
85+
86+
returnresult;
87+
}
88+
89+
@Override/** Return the degree for a specified vertex */
90+
publicintgetDegree(intv) {
91+
returnneighbors.get(v).size();
92+
}
93+
94+
@Override/** Print the edges */
95+
publicvoidprintEdges() {
96+
for (intu =0;u <neighbors.size();u++) {
97+
System.out.print(getVertex(u) +" (" +u +"): ");
98+
for (Edgee :neighbors.get(u)) {
99+
System.out.print("(" +getVertex(e.u) +", " +
100+
getVertex(e.v) +") ");
101+
}
102+
System.out.println();
103+
}
104+
}
105+
106+
@Override/** Clear teh graph */
107+
publicvoidclear() {
108+
vertices.clear();
109+
neighbors.clear();
110+
}
111+
112+
@Override/** Add a vertex to the graph */
113+
publicbooleanaddVertex(Vvertex) {
114+
if (!vertices.contains(vertex)) {
115+
vertices.add(vertex);
116+
neighbors.add(newArrayList<Edge>());
117+
returntrue;
118+
}
119+
else {
120+
returnfalse;
121+
}
122+
}
123+
124+
/** Add an edge to the graph */
125+
protectedbooleanaddEdge(Edgee) {
126+
if (e.u <0 ||e.u >getSize() -1)
127+
thrownewIllegalArgumentException("No such index: " +e.u);
128+
129+
if (e.u <0 ||e.v >getSize() -1)
130+
thrownewIllegalArgumentException("No such index: " +e.u);
131+
132+
if (!neighbors.get(e.u).contains(e)) {
133+
neighbors.get(e.u).add(e);
134+
returntrue;
135+
}
136+
else {
137+
returnfalse;
138+
}
139+
}
140+
141+
@Override/** Add an edge to the graph */
142+
publicbooleanaddEdge(intu,intv) {
143+
returnaddEdge(newEdge(u,v));
144+
}
145+
146+
/** Edge inner class inside the AbstractGraph class */
147+
publicstaticclassEdge {
148+
publicintu;// Starting vertex of the edge
149+
publicintv;// Ending vertex of the edge
150+
151+
/** Construct an edge for (u, v) */
152+
publicEdge(intu,intv) {
153+
this.u =u;
154+
this.v =v;
155+
}
156+
157+
publicbooleanequals(Objecto) {
158+
returnu == ((Edge)o).u &&v == ((Edge)o).v;
159+
}
160+
}
161+
162+
@Override/** Obtain a DFS tree starting from vertex v */
163+
publicTreedfs (intv) {
164+
List<Integer>searchOrder =newArrayList<>();
165+
int[]parent =newint[vertices.size()];
166+
for (inti =0;i <parent.length;i++)
167+
parent[i] = -1;// Initialize parent[i] to -1
168+
169+
// Mark visited vertices
170+
boolean[]isVisited =newboolean[vertices.size()];
171+
172+
// Recursively search
173+
dfs(v,parent,searchOrder,isVisited);
174+
175+
// Return a search tree
176+
returnnewTree(v,parent,searchOrder);
177+
}
178+
179+
/** Recursive method for DFS search */
180+
privatevoiddfs(intu,int[]parent,List<Integer>searchOrder,
181+
boolean[]isVisited) {
182+
// Store the visited vertex
183+
searchOrder.add(u);
184+
isVisited[u] =true;// Vertex v visited
185+
186+
for (Edgee :neighbors.get(u)) {
187+
if (!isVisited[e.v]) {
188+
parent[e.v] =u;// The parent of vertex e.v is u
189+
dfs(e.v,parent,searchOrder,isVisited);// Recursive search
190+
}
191+
}
192+
}
193+
194+
@Override/** Starting bfs search from vertex v */
195+
publicTreebfs(intv) {
196+
List<Integer>searchOrder =newArrayList<>();
197+
int[]parent =newint[vertices.size()];
198+
for (inti =0;i <parent.length;i++)
199+
parent[i] = -1;// Initialize parent[i] to -1
200+
201+
java.util.LinkedList<Integer>queue =
202+
newjava.util.LinkedList<>();// list used as a queue
203+
boolean[]isVisited =newboolean[vertices.size()];
204+
queue.offer(v);// Enqueue v
205+
isVisited[v] =true;// Mark it visited
206+
207+
while (!queue.isEmpty()) {
208+
intu =queue.poll();// Dequeue to u
209+
searchOrder.add(u);// u searched
210+
for (Edgee :neighbors.get(u)) {
211+
if (!isVisited[e.u]) {
212+
queue.offer(e.v);// Enqueue w
213+
parent[e.v] =u;// The parent of w is u
214+
isVisited[e.v] =true;// Mark it visited
215+
}
216+
}
217+
}
218+
219+
returnnewTree(v,parent,searchOrder);
220+
}
221+
222+
/** Tree inner class inside the AbstractGraph class */
223+
publicclassTree {
224+
privateintroot;// The root of the tree
225+
privateint[]parent;// Store the parent of each vertex
226+
privateList<Integer>searchOrder;// Store the search order
227+
228+
/** Construct a tree with root, parent, and searchOrder */
229+
publicTree(introot,int[]parent,List<Integer>searchOrder) {
230+
this.root =root;
231+
this.parent =parent;
232+
this.searchOrder =searchOrder;
233+
}
234+
235+
/** Return the root of the tree */
236+
publicintgetRoot() {
237+
returnroot;
238+
}
239+
240+
/** Return the parent vertex v */
241+
publicintgetParent(intv) {
242+
returnparent[v];
243+
}
244+
245+
/** Return an array representing search order */
246+
publicList<Integer>getSearchOrder() {
247+
returnsearchOrder;
248+
}
249+
250+
/** Return the number of vertices found */
251+
publicintgetNumberOfVerticesFound() {
252+
returnsearchOrder.size();
253+
}
254+
255+
/** Return the path of vertices from a vertex to the root */
256+
publicList<V>getPath(intindex) {
257+
ArrayList<V>path =newArrayList<>();
258+
259+
do {
260+
path.add(vertices.get(index));
261+
index =parent[index];
262+
}
263+
while (index != -1);
264+
265+
returnpath;
266+
}
267+
268+
/** Print a path from the root to vertex v */
269+
publicvoidprintPath(intindex) {
270+
List<V>path =getPath(index);
271+
System.out.print("A path form " +vertices.get(root) +" to " +
272+
vertices.get(index) +": ");
273+
for (inti =path.size() -1;i >=0;i--)
274+
System.out.print(path.get(i) +" ");
275+
}
276+
277+
/** Print the whole tree */
278+
publicvoidprintTree() {
279+
System.out.println("Root is: " +vertices.get(root));
280+
System.out.print("Edges: ");
281+
for (inti =0;i <parent.length;i++) {
282+
if (parent[i] != -1) {
283+
// Display an edge
284+
System.out.print("(" +vertices.get(parent[i]) +", " +
285+
vertices.get(i) +") ");
286+
}
287+
}
288+
System.out.println();
289+
}
290+
}
291+
}
2.86 KB
Binary file not shown.
Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
importjava.util.*;
2+
3+
publicclassExercise_28_01 {
4+
publicstaticvoidmain(String[]args)throwsException {
5+
// Prompt the user to enter a file name
6+
System.out.print("Enter a file name: ");
7+
ScannerfileName =newScanner(System.in);
8+
java.io.Filefile =newjava.io.File(fileName.nextLine());
9+
10+
// Test if file exists
11+
if (!file.exists()) {
12+
System.out.println("The file\"" +file +"\" does not exist.");
13+
System.exit(0);
14+
}
15+
16+
// Crate a Scanner for the file
17+
Scannerinput =newScanner(file);
18+
intNUMBER_OF_VERTICES =input.nextInt();
19+
20+
// Create a list of AbstractGraph.Edge objects
21+
ArrayList<AbstractGraph.Edge>edgeList =newArrayList<>();
22+
23+
// Create an array of vertices
24+
String[]vertices =newString[NUMBER_OF_VERTICES];
25+
26+
// Read data from file
27+
input.nextLine();
28+
for (intj =0;j <NUMBER_OF_VERTICES;j++) {
29+
Strings =input.nextLine();
30+
String[]line =s.split("[\\s+]");
31+
Stringu =line[0];
32+
vertices[j] =u;// Add vertex
33+
34+
// Add edges for vertex u
35+
for (inti =1;i <line.length;i++) {
36+
edgeList.add(newAbstractGraph.Edge(Integer.parseInt(u),
37+
Integer.parseInt(line[i])));
38+
}
39+
}
40+
41+
// Crate a graph
42+
Graph<String>graph =newUnweightedGraph<>(
43+
Arrays.asList(vertices),edgeList);
44+
45+
// Display the number of vertices
46+
System.out.println("The number of vertices is " +graph.getSize());
47+
48+
// Display edges
49+
for (intu =0;u <NUMBER_OF_VERTICES;u++) {
50+
System.out.print("Vertex " +graph.getVertex(u) +":");
51+
for (Integere :graph.getNeighbors(u))
52+
System.out.print(" (" +u +", " +e +")");
53+
System.out.println();
54+
}
55+
56+
// Obtain an instance tree of AbstractGraph.Tree
57+
AbstractGraph.Treetree =graph.dfs(0);
58+
59+
// Test if graph is connected and print results
60+
System.out.println("The graph is " +
61+
(tree.getNumberOfVerticesFound() !=graph.getSize() ?
62+
"not " :"") +"connected");
63+
64+
// Close the file
65+
input.close();
66+
}
67+
}
811 Bytes
Binary file not shown.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp