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

Commit5940cf1

Browse files
author
jsquared21
committed
Add Ex_28.04
1 parentabfe210 commit5940cf1

14 files changed

+472
-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: 292 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,292 @@
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+
publicAbstractGraph() {
9+
}
10+
11+
/** Construct a graph from vertices and edges stored in arrays */
12+
publicAbstractGraph(V[]vertices,int[][]edges) {
13+
for (inti =0 ;i <vertices.length;i++) {
14+
addVertex(vertices[i]);
15+
}
16+
17+
createAdjacencyLists(edges,vertices.length);
18+
}
19+
20+
/** Construct a graph from vertices and edges stored in lists */
21+
publicAbstractGraph(List<V>vertices,List<Edge>edges) {
22+
for (inti =0;i <vertices.size();i++) {
23+
addVertex(vertices.get(i));
24+
}
25+
26+
createAdjacencyLists(edges,vertices.size());
27+
}
28+
29+
/** Construct a graph for integer vertices 0, 1, 2 and edge list */
30+
publicAbstractGraph(List<Edge>edges,intnumberOfVertices) {
31+
for (inti =0;i <numberOfVertices;i++) {
32+
addVertex((V)(newInteger(i)));// vertices is {0, 1, ...}
33+
}
34+
35+
createAdjacencyLists(edges,numberOfVertices);
36+
}
37+
38+
/** Construct a graph for integer vertices 0, 1, 2 and edge array */
39+
publicAbstractGraph(int[][]edges,intnumberOfVertices) {
40+
for (inti =0;i <numberOfVertices;i++) {
41+
addVertex((V)(newInteger(i)));// vertices is {0, 1, ...}
42+
}
43+
44+
createAdjacencyLists(edges,numberOfVertices);
45+
}
46+
47+
/** Create adjacency lists for each vertex */
48+
privatevoidcreateAdjacencyLists(int[][]edges,intnumberOfVertices) {
49+
for (inti =0;i <edges.length;i++) {
50+
addEdge(edges[i][0],edges[i][1]);
51+
}
52+
}
53+
54+
/** Create adjacency lists for each vertex */
55+
privatevoidcreateAdjacencyLists(List<Edge>edges,intnumberOfVertices) {
56+
for (Edgeedge:edges) {
57+
addEdge(edge.u,edge.v);
58+
}
59+
}
60+
61+
@Override/* Return the number of vertices in the graph */
62+
publicintgetSize() {
63+
returnvertices.size();
64+
}
65+
66+
@Override/** Return the vertices in the graph */
67+
publicList<V>getVertices() {
68+
returnvertices;
69+
}
70+
71+
@Override/** Return the object for the specified vertex index */
72+
publicVgetVertex(intindex) {
73+
returnvertices.get(index);
74+
}
75+
76+
@Override/** Return the index for the specified vertex object */
77+
publicintgetIndex(Vv) {
78+
returnvertices.indexOf(v);
79+
}
80+
81+
@Override/** Return the neighbors of the specified vertex */
82+
publicList<Integer>getNeighbors(intindex) {
83+
List<Integer>result =newArrayList<>();
84+
for (Edgee:neighbors.get(index)) {
85+
result.add(e.v);
86+
}
87+
88+
returnresult;
89+
}
90+
91+
@Override/** Return the degree for a spceified vertex */
92+
publicintgetDegree(intv) {
93+
returnneighbors.get(v).size();
94+
}
95+
96+
@Override/** Print the edges */
97+
publicvoidprintEdges() {
98+
for (intu =0;u <neighbors.size();u++) {
99+
System.out.print(getVertex(u) +" (" +u +"): ");
100+
for (Edgee :neighbors.get(u)) {
101+
System.out.print("(" +getVertex(e.u) +", " +
102+
getVertex(e.v) +") ");
103+
}
104+
System.out.println();
105+
}
106+
}
107+
108+
@Override/** Clear the graph */
109+
publicvoidclear() {
110+
vertices.clear();
111+
neighbors.clear();
112+
}
113+
114+
@Override/** Add a vertex to the graph */
115+
publicbooleanaddVertex(Vvertex) {
116+
if (!vertices.contains(vertex)) {
117+
vertices.add(vertex);
118+
neighbors.add(newArrayList<Edge>());
119+
returntrue;
120+
}
121+
returnfalse;
122+
}
123+
124+
/** Add an edge to the grpah */
125+
privatebooleanaddEdge(Edgee) {
126+
if (e.u <0 ||e.u >getSize() -1)
127+
thrownewIllegalArgumentException("No such index: " +e.u);
128+
129+
if (e.v <0 ||e.v >getSize() -1)
130+
thrownewIllegalArgumentException("No such index: " +e.v);
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+
170+
// Mark visited vertices
171+
boolean[]isVisited =newboolean[vertices.size()];
172+
173+
// Recursively search
174+
dfs(v,parent,searchOrder,isVisited);
175+
176+
// Return a search
177+
returnnewTree(v,parent,searchOrder);
178+
}
179+
180+
/** Recursive method for DFS search */
181+
privatevoiddfs(intu,int[]parent,
182+
List<Integer>searchOrder,boolean[]isVisited) {
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/** Obtain a BFS tree starting 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+
202+
LinkedList<Integer>queue =newLinkedList<>();
203+
boolean[]isVisited =newboolean[vertices.size()];
204+
205+
queue.offer(v);// Enqueue v
206+
isVisited[v] =true;// Mark it visited
207+
208+
while (!queue.isEmpty()) {
209+
intu =queue.poll();
210+
searchOrder.add(u);
211+
for (Edgee :neighbors.get(u)) {
212+
if (!isVisited[e.v]) {
213+
queue.offer(e.v);
214+
parent[e.v] =u;
215+
isVisited[e.v] =true;
216+
}
217+
}
218+
}
219+
220+
returnnewTree(v,parent,searchOrder);
221+
}
222+
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 of 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 root to vertex v */
269+
publicvoidprintPath(intindex) {
270+
List<V>path =getPath(index);
271+
System.out.print("A path from " +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+
278+
/** Print the whole tree */
279+
publicvoidprintTree() {
280+
System.out.println("Root is: " +vertices.get(root));
281+
System.out.print("Edges: ");
282+
for (inti =0;i <parent.length;i++) {
283+
if (parent[i] != -1) {
284+
// Display an edge
285+
System.out.print("(" +vertices.get(parent[i]) +", " +
286+
vertices.get(i) +") ");
287+
}
288+
}
289+
System.out.println();
290+
}
291+
}
292+
}
2.13 KB
Binary file not shown.
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/*********************************************************************************
2+
* (Find connected components) Create a new class named MyGraph as a subclass of *
3+
* MyGraph that contains a method for finding all connected components in a graph *
4+
* with the following header: *
5+
* *
6+
* public List<List<Integer>> getConnectedComponents(); *
7+
* *
8+
* The method returns a List<List<Integer>>. Each element in the list is another *
9+
* list that contains all the vertices in a connected component. For example, for *
10+
* the graph in Figure 28.21b, getConnectedComponents() returns *
11+
* [[0, 1, 2, 3], [4, 5]]. *
12+
*********************************************************************************/
13+
importjava.util.*;
14+
15+
publicclassExercise_28_04 {
16+
publicstaticvoidmain(String[]args)throwsException {
17+
// Prompt the user to enter a file name
18+
System.out.print("Enter file name: ");
19+
ScannerfileName =newScanner(System.in);
20+
java.io.Filefile =newjava.io.File(fileName.nextLine());
21+
22+
// Test if file exists
23+
if (!file.exists()) {
24+
System.out.println("The file\"" +file +"\" does not exist.");
25+
System.exit(0);
26+
}
27+
28+
try (
29+
// Create a Scanner for the file
30+
Scannerinput =newScanner(file);
31+
) {
32+
intNUMBER_OF_VERTICES =input.nextInt();
33+
34+
// Create a list of AbstractGraph.Edge objects
35+
ArrayList<AbstractGraph.Edge>edges =newArrayList<>();
36+
37+
while (input.hasNext()) {
38+
Strings =input.nextLine();
39+
String[]line =s.split("[\\s+]");
40+
41+
// Add edges
42+
for (intj =1;j <line.length;j++) {
43+
edges.add(newAbstractGraph.Edge(
44+
Integer.parseInt(line[0]),Integer.parseInt(line[j])));
45+
}
46+
}
47+
48+
// Create a graph
49+
MyGraph<String>graph =newMyGraph<>(edges,NUMBER_OF_VERTICES);
50+
System.out.println(graph.getConnectedComponents());
51+
}
52+
}
53+
}
811 Bytes
Binary file not shown.
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 object 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 the 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-first 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: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
6
2+
0 1 2
3+
1 0 3
4+
2 0 3 4
5+
3 1 2 4 5
6+
4 2 3 5
7+
5 3 4

0 commit comments

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