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

Commitabfe210

Browse files
author
jsquared21
committed
Add Ex_28.02
1 parent5095726 commitabfe210

11 files changed

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

‎Exercise_28/Exercise_28_02/Graph.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
publicinterfaceGraph<V> {
2+
/** Returns the number of vertices in the graph */
3+
publicintgetSize();
4+
5+
/** Return the vertices in the graph */
6+
publicjava.util.List<V>getVertices();
7+
8+
/** Return the object for the specified vertex index */
9+
publicVgetVertex(intindex);
10+
11+
/** Return the index for the specified vertex object */
12+
publicintgetIndex(Vv);
13+
14+
/** Return the neighbors of vertex with the specified index */
15+
publicjava.util.List<Integer>getNeighbors(intindex);
16+
17+
/** Return degree for a specified vertex */
18+
publicintgetDegree(intv);
19+
20+
/** Prints the edges */
21+
publicvoidprintEdges();
22+
23+
/** Clears the graph */
24+
publicvoidclear();
25+
26+
/** Add a vertex to the graph */
27+
publicbooleanaddVertex(Vvertex);
28+
29+
/** Add an edge to the graph */
30+
publicbooleanaddEdge(intu,intv);
31+
32+
/** Obtains a depth-frist search tree starting from v */
33+
publicAbstractGraph<V>.Treedfs(intv);
34+
35+
/** Obtains a breath-first search tree starting from v */
36+
publicAbstractGraph<V>.Treebfs(intv);
37+
}
Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
12
2+
0 1 3 5
3+
1 0 2 3
4+
2 1 3 4 10
5+
3 0 1 2 4 5
6+
4 2 3 5 7 8 10
7+
5 0 3 4 6 7
8+
6 5 7
9+
7 4 5 6 8
10+
8 4 7 9 10 11
11+
9 8 11
12+
10 2 4 8 11
13+
11 8 9 10
809 Bytes
Binary file not shown.

0 commit comments

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