При рассмотрении алгоритмов Union Find, которые доктор Роберт Седжвик и доктор Кевин Уэйн проинструктировали через их книгу и веб-сайт:
https://algs4.cs.princeton.edu/10fundamentals/
я создал Проект Maven (который я импортировал в IntelliJ IDEA) со следующим pom. xml:
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>edu.princeton.cs.algs4</groupId>
<artifactId>algs4</artifactId>
<version>1.0-SNAPSHOT</version>
<dependencies>
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>4.12</version>
<scope>test</scope>
<exclusions>
<exclusion>
<groupId>org.hamcrest</groupId>
<artifactId>hamcrest-core</artifactId>
</exclusion>
</exclusions>
</dependency>
<dependency>
<groupId>org.hamcrest</groupId>
<artifactId>hamcrest-library</artifactId>
<version>2.2</version>
<scope>test</scope>
</dependency>
<dependency>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-javadoc-plugin</artifactId>
<version>3.2.0</version>
</dependency>
</dependencies>
<build>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-compiler-plugin</artifactId>
<configuration>
<source>10</source>
<target>10</target>
</configuration>
</plugin>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-javadoc-plugin</artifactId>
<version>3.2.0</version>
<configuration>
<show>private</show> <!--javadoc shows all classes and members-->
</configuration>
</plugin>
</plugins>
</build>
<reporting>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-javadoc-plugin</artifactId>
<version>3.2.0</version>
<configuration>
<stylesheetfile>${basedir}/src/main/javadoc/stylesheet.css</stylesheetfile>
<show>public</show>
</configuration>
</plugin>
</plugins>
</reporting>
</project>
Структура файла проекта:
algs4
|
├── pom.xml
└── src
├── main
│ ├── java
│ │ └── edu
│ │ └── princeton
│ │ └── cs
│ │ └── algs4
│ │ ├── QuickFindUF.java
│ │ ├── QuickUnionUF.java
│ │ ├── StdIn.java
│ │ ├── StdOut.java
│ │ └── WeightedQuickUnionUF.java
│ └── resources
│ ├── largeUF.txt
│ ├── mediumUF.txt
│ └── tinyUF.txt
└── test
└── java
QuickFindUF. java:
public class QuickFindUF {
private int[] id; // id[i] = component identifier of i
private int count; // number of components
public QuickFindUF(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}
public int count() {
return count;
}
public int find(int p) {
validate(p);
return id[p];
}
// validate that p is a valid index
private void validate(int p) {
int n = id.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
}
}
public void union(int p, int q) {
validate(p);
validate(q);
int pID = id[p]; // needed for correctness
int qID = id[q]; // to reduce the number of array accesses
// p and q are already in the same component
if (pID == qID) return;
for (int i = 0; i < id.length; i++)
if (id[i] == pID) id[i] = qID;
count--;
}
public static void main(String[] args) {
int n = StdIn.readInt();
QuickFindUF uf = new QuickFindUF(n);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.find(p) == uf.find(q)) continue;
uf.union(p, q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count() + " components");
}
}
QuickUnionUF. java:
public class QuickUnionUF {
private int[] parent; // parent[i] = parent of i
private int count; // number of components
public QuickUnionUF(int n) {
parent = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int count() {
return count;
}
public int find(int p) {
validate(p);
while (p != parent[p])
p = parent[p];
return p;
}
// validate that p is a valid index
private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
}
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
count--;
}
public static void main(String[] args) {
int n = StdIn.readInt();
QuickUnionUF uf = new QuickUnionUF(n);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.find(p) == uf.find(q)) continue;
uf.union(p, q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count() + " components");
}
}
WeightedQuickUnionUF. java:
public class WeightedQuickUnionUF {
private int[] parent; // parent[i] = parent of i
private int[] size; // size[i] = number of elements in subtree rooted at i
private int count; // number of components
public WeightedQuickUnionUF(int n) {
count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int count() {
return count;
}
public int find(int p) {
validate(p);
while (p != parent[p])
p = parent[p];
return p;
}
// validate that p is a valid index
private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
}
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// make smaller root point to larger one
if (size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
count--;
}
public static void main(String[] args) {
int n = StdIn.readInt();
WeightedQuickUnionUF uf = new WeightedQuickUnionUF(n);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.find(p) == uf.find(q)) continue;
uf.union(p, q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count() + " components");
}
}
Реализация для StdIn может быть найдена в:
https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/StdIn.java.html
Реализация для StdOut может быть найдена в:
https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/StdOut.java.html
Файлы данных можно найти по адресу:
Когда я провожу mvn clean install или mvn test
Это создал соответствующий целевой каталог, как показано ниже:
target
├── classes
├── edu
│ └── princeton
│ └── cs
│ └── algs4
│ ├── QuickFindUF.class
│ ├── QuickUnionUF.class
│ ├── StdIn.class
│ ├── StdOut.class
│ └── WeightedQuickUnionUF.class
├── largeUF.txt
├── mediumUF.txt
└── tinyUF.txt
Так как я создал и импортировал его в Что касается IntelliJ как проекта maven, я не мог понять, как настроить «Запуск как автономное Java приложение» (с txt-файлом как аргументом метода main ().
Итак, что Я выполнил «mvn test»
Ничего не произошло ... Есть ли способ сделать это через терминал или IntelliJ IDEA?