17. 그림 알고리즘 의 최소 생 성 트 리
말하자면 모든 점 을 연결 하고 가중치 가 가장 작은 무 환 연결 서브 맵 입 니 다.
주로 두 가지 알고리즘 이 있 습 니 다. Prim 알고리즘 과 Kruskal 알고리즘 입 니 다.
먼저 약속 을 하 자.
（ ）
0 （ ， ）
（ ）
의 원리
나무의 중요 한 성질 을 되돌아보다.
정리
절 분 정리 라 는 성질 은 가중 도 중의 모든 정점 을 두 개의 집합 으로 나 누 어 두 개의 집합 을 가로 지 르 는 모든 변 을 검사 하고 어느 변 이 그림 에 속 해 야 하 는 최소 생 성 트 리 를 식별 할 것 이다.
정의:
。
보통 집합 을 지정 합 니 다. 우 리 는 그것 의 보충 집합 이 다른 집합 이 라 고 암시 적 으로 지정 한 다음 에 가로 자 르 는 변 은 두 개의 집합 을 연결 하 는 변 입 니 다.
정리:
： ， ， 。
，
주의: 모든 변 의 가중치 가 다르다 고 가정 하 는 전제 에서 모든 그림 은 유일한 최소 생 성 트 리 만 있 습 니 다.
매번 절 분 될 때마다 발생 하 는 횡 절 변 은 반드시 그 가중치 가 가장 작은 것 만 최소 생 성 트 리 의 변 에 속 하 는 것 이 아니 라 실제 적 으로 여러 가지 가 있 을 수 있 지만 그 가장 작은 것 은 최소 생 성 트 리 의 변 에 속 할 것 이다.
최소 생 성 트 리 의 욕심 알고리즘
절 분 알고리즘 은 욕심 산법 의 일종 이 라 고 할 수 있 는데, 매번 가장 작은 것 을 찾 기 때문이다.
， ， 。 。 ， V-1 。 V
그림 없 는 API 가중
Edge 클래스:
public class Edge implements Comparable<Edge> {
private final int v;
private final int w;
private final double weight;
public Edge(int v, int w, double weight) {
if (v < 0) throw new IndexOutOfBoundsException("Vertex name must be a nonnegative integer");
if (w < 0) throw new IndexOutOfBoundsException("Vertex name must be a nonnegative integer");
if (Double.isNaN(weight)) throw new IllegalArgumentException("Weight is NaN");
this.v = v;
this.w = w;
this.weight = weight;
}
public double weight() {
return weight;
}
public int either() {
return v;
}
public int other(int vertex) {
if (vertex == v) return w;
else if (vertex == w) return v;
else throw new IllegalArgumentException("Illegal endpoint");
}
@Override
public int compareTo(Edge that) {
if (this.weight() < that.weight()) return -1;
else if (this.weight() > that.weight()) return +1;
else return 0;
}
public String toString() {
return String.format("%d-%d %.5f", v, w, weight);
}
}가중 무 방향 그림 EdgeWeightedGraph:
public class EdgeWeightedGraph {
private static final String NEWLINE = System.getProperty("line.separator");
private final int V;
private int E;
private Bag<Edge>[] adj;
public EdgeWeightedGraph(int V) {
if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
this.V = V;
this.E = 0;
adj = (Bag<Edge>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<Edge>();
}
}
public EdgeWeightedGraph(int V, int E) {
this(V);
if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
for (int i = 0; i < E; i++) {
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
double weight = Math.round(100 * StdRandom.uniform()) / 100.0;
Edge e = new Edge(v, w, weight);
addEdge(e);
}
}
public EdgeWeightedGraph(In in) {
this(in.readInt());
int E = in.readInt();
if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
double weight = in.readDouble();
Edge e = new Edge(v, w, weight);
addEdge(e);
}
}
public EdgeWeightedGraph(EdgeWeightedGraph G) {
this(G.V());
this.E = G.E();
for (int v = 0; v < G.V(); v++) {
// reverse so that adjacency list is in same order as original
Stack<Edge> reverse = new Stack<Edge>();
for (Edge e : G.adj[v]) {
reverse.push(e);
}
for (Edge e : reverse) {
adj[v].add(e);
}
}
}
public int V() {
return V;
}
public int E() {
return E;
}
// throw an IndexOutOfBoundsException unless 0 <= v < V
private void validateVertex(int v) {
if (v < 0 || v >= V)
throw new IndexOutOfBoundsException("vertex " + v + " is not between 0 and " + (V-1));
}
public void addEdge(Edge e) {
int v = e.either();
int w = e.other(v);
validateVertex(v);
validateVertex(w);
adj[v].add(e);
adj[w].add(e);
E++;
}
public Iterable<Edge> adj(int v) {
validateVertex(v);
return adj[v];
}
public int degree(int v) {
validateVertex(v);
return adj[v].size();
}
public Iterable<Edge> edges() {
Bag<Edge> list = new Bag<Edge>();
for (int v = 0; v < V; v++) {
int selfLoops = 0;
for (Edge e : adj(v)) {
if (e.other(v) > v) {
list.add(e);
}
// only add one copy of each self loop (self loops will be consecutive)
else if (e.other(v) == v) {
if (selfLoops % 2 == 0) list.add(e);
selfLoops++;
}
}
}
return list;
}
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (Edge e : adj[v]) {
s.append(e + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
}Prim 알고리즘
prim 알고리즘 은 한 걸음 한 걸음 성장 하 는 나무 에 한 변 을 추가 합 니 다.처음에 이 나 무 는 하나의 정점 만 있 었 고 매번 다음 연결 나무의 정점 과 나무 에 없 는 정점, 그리고 가장 작은 변 을 나무 에 넣 었 습 니 다.
Prim
데이터 구조:
marked[]， true， false
새 추가 점 과 우선 대기 열 에 저 장 된 일부 변 에 존재 할 경우 우선 대기 열 에 있 는 이 변 들 을 무효 화 합 니 다.단계: 시작 트 리 에 점 이 하나 밖 에 없습니다. 그리고 이 점 과 연 결 된 쪽 을 찾 아 우선 대기 열 에 가입 하 십시오. 우선 대기 열 에서 가중치 가 가장 작은 쪽 (가장 작은 쪽 은 우선 대기 열 에서 삭 제 됩 니 다. 나머지 쪽 은 우선 대기 열 에 남아 있 습 니 다. 예비 변 으로 남아 있 습 니 다) 그리고 선택 한 다른 점 을 트 리 에 추가 합 니 다. 새로 추 가 된 점 에 대해 서 는...남 은 접근 하지 않 은 점 과 새로 추 가 된 점 이 연결 되 어 있 는 점 을 찾 습 니 다. 또한 새로 추 가 된 점 과 연 결 된 변 을 우선 대기 열 에 추가 합 니 다. (이미 트 리 에 있 는 점 은 그만 두 지 않 습 니 다)메모: 새로 추가 할 때마다 우선 대기 열 에 있 는 일부 변 에 새 추가 점 이 포함 되 어 있 습 니 다. 그 변 을 무효 화 합 니 다.
복잡 도: 공간 은 E 와 정비례 하고 필요 한 시간 은 ElogE 와 정비례 한다.
Prim 알고리즘 의 시간 지연 실현:
지연 시간 이란 먼저 변 이 효력 을 잃 지 않도록 하 는 것 입 니 다.
public class LazyPrimMST {
private static final double FLOATING_POINT_EPSILON = 1E-12;
private double weight; // total weight of MST
private Queue<Edge> mst; // edges in the MST
private boolean[] marked; // marked[v] = true if v on tree
private MinPQ<Edge> pq; // edges with one endpoint in tree
public LazyPrimMST(EdgeWeightedGraph G) {
mst = new Queue<Edge>();
pq = new MinPQ<Edge>();
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) // run Prim from all vertices to
if (!marked[v]) prim(G, v); // get a minimum spanning forest
// check optimality conditions
assert check(G);
}
// run Prim's algorithm
private void prim(EdgeWeightedGraph G, int s) {
scan(G, s);
while (!pq.isEmpty()) { // better to stop when mst has V-1 edges
Edge e = pq.delMin(); // smallest edge on pq
int v = e.either(), w = e.other(v); // two endpoints
assert marked[v] || marked[w];
if (marked[v] && marked[w]) continue; // lazy, both v and w already scanned
mst.enqueue(e); // add e to MST
weight += e.weight();
if (!marked[v]) scan(G, v); // v becomes part of tree
if (!marked[w]) scan(G, w); // w becomes part of tree
}
}
// add all edges e incident to v onto pq if the other endpoint has not yet been scanned
private void scan(EdgeWeightedGraph G, int v) {
assert !marked[v];
marked[v] = true;
for (Edge e : G.adj(v))
if (!marked[e.other(v)]) pq.insert(e);
}
public Iterable<Edge> edges() {
return mst;
}
public double weight() {
return weight;
}
// check optimality conditions (takes time proportional to E V lg* V)
private boolean check(EdgeWeightedGraph G) {
// check weight
double totalWeight = 0.0;
for (Edge e : edges()) {
totalWeight += e.weight();
}
if (Math.abs(totalWeight - weight()) > FLOATING_POINT_EPSILON) {
System.err.printf("Weight of edges does not equal weight(): %f vs. %f
", totalWeight, weight());
return false;
}
// check that it is acyclic
UF uf = new UF(G.V());
for (Edge e : edges()) {
int v = e.either(), w = e.other(v);
if (uf.connected(v, w)) {
System.err.println("Not a forest");
return false;
}
uf.union(v, w);
}
// check that it is a spanning forest
for (Edge e : G.edges()) {
int v = e.either(), w = e.other(v);
if (!uf.connected(v, w)) {
System.err.println("Not a spanning forest");
return false;
}
}
// check that it is a minimal spanning forest (cut optimality conditions)
for (Edge e : edges()) {
// all edges in MST except e
uf = new UF(G.V());
for (Edge f : mst) {
int x = f.either(), y = f.other(x);
if (f != e) uf.union(x, y);
}
// check that e is min weight edge in crossing cut
for (Edge f : G.edges()) {
int x = f.either(), y = f.other(x);
if (!uf.connected(x, y)) {
if (f.weight() < e.weight()) {
System.err.println("Edge " + f + " violates cut optimality conditions");
return false;
}
}
}
}
return true;
}
}Prim 알고리즘 의 실시 간 실현
우리 가 정점 v 를 나무 에 추가 할 때 모든 비 나무 정점 w 에 대한 변 화 는 w 에서 최소 생 성 나무의 거리 만 가 까 워 질 수 있다 (기본 사상).한 마디 로 하면, 우 리 는 w 에서 트 리 꼭대기 까지 의 모든 변 을 우선 대기 열 에 저장 할 필요 가 없습니다. 그 중 가장 작은 변 만 저장 하고, v 를 트 리 에 추가 한 후, 이 가중치 의 가장 작은 변 을 업데이트 해 야 하 는 지 확인 하 십시오. (v - w 의 가중치 가 더 작 을 수 있 기 때 문 입 니 다.)
하나의 EdgeTo 배열 로 모든 점 에서 트 리 까지 의 거 리 를 저장 합 니 다 (나 무 를 하나의 전체 로 보 는 것 과 같 습 니 다). 점 을 추가 할 때마다 이 거 리 를 업데이트 합 니 다. 점 을 선택 할 때 도 트 리 거리 가 가장 작은 점 을 선택 합 니 다.
복잡 도: 공간 은 V 와 관련 되 고 시간 은 ElogV 와 정비례 한다.
public class PrimMST {
private static final double FLOATING_POINT_EPSILON = 1E-12;
private Edge[] edgeTo; // edgeTo[v] = shortest edge from tree vertex to non-tree vertex
private double[] distTo; // distTo[v] = weight of shortest such edge
private boolean[] marked; // marked[v] = true if v on tree, false otherwise
private IndexMinPQ<Double> pq;
public PrimMST(EdgeWeightedGraph G) {
edgeTo = new Edge[G.V()];
distTo = new double[G.V()];
marked = new boolean[G.V()];
pq = new IndexMinPQ<Double>(G.V());
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
for (int v = 0; v < G.V(); v++) // run from each vertex to find
if (!marked[v]) prim(G, v); // minimum spanning forest
// check optimality conditions
assert check(G);
}
// run Prim's algorithm in graph G, starting from vertex s
private void prim(EdgeWeightedGraph G, int s) {
distTo[s] = 0.0;
pq.insert(s, distTo[s]);
while (!pq.isEmpty()) {
int v = pq.delMin();
scan(G, v);
}
}
// scan vertex v
private void scan(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v)) {
int w = e.other(v);
if (marked[w]) continue; // v-w is obsolete edge
if (e.weight() < distTo[w]) {
distTo[w] = e.weight();
edgeTo[w] = e;
if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}
}
public Iterable<Edge> edges() {
Queue<Edge> mst = new Queue<Edge>();
for (int v = 0; v < edgeTo.length; v++) {
Edge e = edgeTo[v];
if (e != null) {
mst.enqueue(e);
}
}
return mst;
}
public double weight() {
double weight = 0.0;
for (Edge e : edges())
weight += e.weight();
return weight;
}
// check optimality conditions (takes time proportional to E V lg* V)
private boolean check(EdgeWeightedGraph G) {
// check weight
double totalWeight = 0.0;
for (Edge e : edges()) {
totalWeight += e.weight();
}
if (Math.abs(totalWeight - weight()) > FLOATING_POINT_EPSILON) {
System.err.printf("Weight of edges does not equal weight(): %f vs. %f
", totalWeight, weight());
return false;
}
// check that it is acyclic
UF uf = new UF(G.V());
for (Edge e : edges()) {
int v = e.either(), w = e.other(v);
if (uf.connected(v, w)) {
System.err.println("Not a forest");
return false;
}
uf.union(v, w);
}
// check that it is a spanning forest
for (Edge e : G.edges()) {
int v = e.either(), w = e.other(v);
if (!uf.connected(v, w)) {
System.err.println("Not a spanning forest");
return false;
}
}
// check that it is a minimal spanning forest (cut optimality conditions)
for (Edge e : edges()) {
// all edges in MST except e
uf = new UF(G.V());
for (Edge f : edges()) {
int x = f.either(), y = f.other(x);
if (f != e) uf.union(x, y);
}
// check that e is min weight edge in crossing cut
for (Edge f : G.edges()) {
int x = f.either(), y = f.other(x);
if (!uf.connected(x, y)) {
if (f.weight() < e.weight()) {
System.err.println("Edge " + f + " violates cut optimality conditions");
return false;
}
}
}
}
return true;
}
}Kruskal 알고리즘
Kruskal 알고리즘 은 임의의 가중 무 방향 그림 의 맨 아래 생 성 트 리 를 계산 하여 변 의 가중치 에 따라 정렬 할 수 있 으 며, 가입 시 링 을 구성 할 수 없 음 을 판단 해 야 합 니 다.이 테 두 리 를 숲 으로 구성 하 는 Prim 알고리즘 은 한 변 한 변 의 구조 가 가장 작은 생 성 트 리 이지 만 Prim 알고리즘 과 달리 매번 추 가 된 테 두 리 를 꼭 같은 나무 에 추가 하 는 것 은 아니 지만 결국 이 나무 들 은 한 걸음 한 걸음 융합 된다.
복잡 도: 공간 은 E 와 정비례 하고 시간 은 ElogE 와 정비례 하 며 내부 에 서 는 우선 대기 열과 union - find 알고리즘 을 사용 합 니 다.
public class KruskalMST {
private static final double FLOATING_POINT_EPSILON = 1E-12;
private double weight; // weight of MST
private Queue<Edge> mst = new Queue<Edge>(); // edges in MST
public KruskalMST(EdgeWeightedGraph G) {
// more efficient to build heap by passing array of edges
MinPQ<Edge> pq = new MinPQ<Edge>();
for (Edge e : G.edges()) {
pq.insert(e);
}
// run greedy algorithm
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V() - 1) {
Edge e = pq.delMin();
int v = e.either();
int w = e.other(v);
if (!uf.connected(v, w)) { // v-w does not create a cycle
uf.union(v, w); // merge v and w components
mst.enqueue(e); // add edge e to mst
weight += e.weight();
}
}
// check optimality conditions
assert check(G);
}
public Iterable<Edge> edges() {
return mst;
}
public double weight() {
return weight;
}
// check optimality conditions (takes time proportional to E V lg* V)
private boolean check(EdgeWeightedGraph G) {
// check total weight
double total = 0.0;
for (Edge e : edges()) {
total += e.weight();
}
if (Math.abs(total - weight()) > FLOATING_POINT_EPSILON) {
System.err.printf("Weight of edges does not equal weight(): %f vs. %f
", total, weight());
return false;
}
// check that it is acyclic
UF uf = new UF(G.V());
for (Edge e : edges()) {
int v = e.either(), w = e.other(v);
if (uf.connected(v, w)) {
System.err.println("Not a forest");
return false;
}
uf.union(v, w);
}
// check that it is a spanning forest
for (Edge e : G.edges()) {
int v = e.either(), w = e.other(v);
if (!uf.connected(v, w)) {
System.err.println("Not a spanning forest");
return false;
}
}
// check that it is a minimal spanning forest (cut optimality conditions)
for (Edge e : edges()) {
// all edges in MST except e
uf = new UF(G.V());
for (Edge f : mst) {
int x = f.either(), y = f.other(x);
if (f != e) uf.union(x, y);
}
// check that e is min weight edge in crossing cut
for (Edge f : G.edges()) {
int x = f.either(), y = f.other(x);
if (!uf.connected(x, y)) {
if (f.weight() < e.weight()) {
System.err.println("Edge " + f + " violates cut optimality conditions");
return false;
}
}
}
}
return true;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
