溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細(xì)講解有關(guān)Java如何求最小生成樹，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。
生成樹（SpanningTree）：一個(gè)連通圖的生成樹是指一個(gè)連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。一顆有n個(gè)頂點(diǎn)的生成樹有且僅有n-1條邊，如果生成樹中再添加一條邊，則必定成環(huán)。
最小生成樹（Minimum Spanning Tree）：在連通圖的所有生成樹中，所有邊的權(quán)值和最小的生成樹，稱為最小生成樹。
在生活中，圖形結(jié)構(gòu)的應(yīng)用是最廣泛的。比如常見的通信網(wǎng)絡(luò)搭建路線選擇，村莊可以看作頂點(diǎn)，村莊之間如果有通信路徑，則算作兩點(diǎn)之間的邊或者弧，兩個(gè)村莊之間的通信成本，可以看作邊或者弧的權(quán)值。
上圖就是生活中通信網(wǎng)絡(luò)搭建路線的選擇映射到圖形結(jié)構(gòu)的案例。頂點(diǎn)作為村莊，村莊之間如果有通信路徑則擁有邊，村莊的之間的通信搭建成本則是邊的權(quán)值。
一種很常見的需求是要求對(duì)于能夠通信的村莊都必須通信，并且通信建設(shè)成本和最小，畢竟經(jīng)費(fèi)“有限”，省下來的經(jīng)費(fèi)，嘿嘿！
上面的問題，轉(zhuǎn)換為數(shù)學(xué)模型，就是求一個(gè)圖的最小生成樹的問題，即：選出一條路線，連通了所有能夠連通頂點(diǎn)，并且權(quán)值和最小。這樣的問題已經(jīng)有了很多種解法，最經(jīng)典的有兩種算法，普里姆（Prim）算法和克魯斯卡爾（Kruskal)算法。
普里姆（Prim）算法是以某頂點(diǎn)為起點(diǎn)，假設(shè)所有頂點(diǎn)均未連接，逐步找各頂點(diǎn)上最小權(quán)值的邊來連接并構(gòu)建最小生成樹。是以點(diǎn)為目標(biāo)去構(gòu)建最小生成樹。
具體的步驟是： 首先隨機(jī)選取一個(gè)頂點(diǎn)a，尋找頂點(diǎn)a可連接所有的頂點(diǎn)，選擇一個(gè)權(quán)值低的頂點(diǎn)進(jìn)行連接；然后尋找與這兩個(gè)頂點(diǎn)或可連接的所有頂點(diǎn)，選擇一個(gè)權(quán)值低的頂點(diǎn)與其中一個(gè)頂點(diǎn)進(jìn)行連接；如此往復(fù)n-1次，每次選擇距離任意一個(gè)已連接末端頂點(diǎn)最短的頂點(diǎn)（而不是距離首個(gè)頂點(diǎn)最短的頂點(diǎn)）進(jìn)行連接，直到所有的頂點(diǎn)都進(jìn)行連接，至此最小生成樹構(gòu)建完畢。
該案例對(duì)應(yīng)著下面實(shí)現(xiàn)代碼中的案例。
在上面的圖中，首先選擇頂點(diǎn)A作為已連接點(diǎn)，尋找頂點(diǎn)A可連接所有的頂點(diǎn)C、D、F，選擇一個(gè)權(quán)值低的頂點(diǎn)進(jìn)行連接，這里選擇A-C；
然后尋找與A或C可連接的所有頂點(diǎn)（排除已連接的點(diǎn)），找到B、D、F，一共有4條邊可選，A-D、A-F、C-B、C-D，選擇一個(gè)權(quán)值低的頂點(diǎn)與其中一個(gè)頂點(diǎn)進(jìn)行連接，這里明顯選擇A-D連接；
然后尋找與A或C或D可連接的所有頂點(diǎn)（排除已連接的點(diǎn)），找到B、F，一共有3條邊可選，C-B、D-B、A-F，選擇一個(gè)權(quán)值低的頂點(diǎn)與其中一個(gè)頂點(diǎn)進(jìn)行連接，這里明顯選擇A-F連接；
然后尋找與A或C或D或F可連接的所有頂點(diǎn)（排除已連接的點(diǎn)），找到B、G，一共有3條邊可選，C-B、D-B、F-G，選擇一個(gè)權(quán)值低的頂點(diǎn)與其中一個(gè)頂點(diǎn)進(jìn)行連接，這里明顯選擇C-B連接；
然后尋找與A或C或D或F或B可連接的所有頂點(diǎn)（排除已連接的點(diǎn)），找到E、G，一共有2條邊可選，B-E、F-G，選擇一個(gè)權(quán)值低的頂點(diǎn)與其中一個(gè)頂點(diǎn)進(jìn)行連接，這里明顯選擇B-E連接；
然后尋找與A或C或D或F或B或E可連接的所有頂點(diǎn)（排除已連接的點(diǎn)），找到G，一共有2條邊可選，E-G、F-G，選擇一個(gè)權(quán)值低的頂點(diǎn)與其中一個(gè)頂點(diǎn)進(jìn)行連接，這里明顯選擇E-G連接；
所有的頂點(diǎn)連接完畢，此時(shí)最小生成樹已經(jīng)構(gòu)建好了，最小權(quán)值為23。
克魯斯卡爾算法（Kruskal）根據(jù)邊的權(quán)值以遞增的方式逐漸建立最小生成樹，是以邊為目標(biāo)去構(gòu)建最小生成樹。
具體的步驟是： 將加權(quán)圖每個(gè)頂點(diǎn)都看做森林，然后將圖中每條鄰接邊的權(quán)值按照升序的方式進(jìn)行排列，接著從排列好的鄰接邊表中抽取權(quán)值最小的邊，寫入該邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)，連接頂點(diǎn)將森林構(gòu)成樹，然后讀取起始結(jié)束頂點(diǎn)的鄰接邊，優(yōu)先抽取權(quán)值小的鄰接邊，繼續(xù)連接頂點(diǎn)將森林構(gòu)成樹。添加鄰接邊的要求是加入到圖中的鄰接邊不構(gòu)成回路（環(huán)）。如此反復(fù)進(jìn)行，直到已經(jīng)添加n-1條邊為止。至此最小生成樹構(gòu)建完畢。
該案例對(duì)應(yīng)著下面實(shí)現(xiàn)代碼中的案例，傳統(tǒng)Kruskal算法過程如下：
首先獲取邊集數(shù)組并按照權(quán)值重小到大進(jìn)行排序，在代碼中的排序本人直接使用的sort排序，也可以自己實(shí)現(xiàn)堆排序，排序后結(jié)果如下：
Edge{from=A, to=C, weight=1}
Edge{from=D, to=A, weight=2}
Edge{from=A, to=F, weight=3}
Edge{from=B, to=C, weight=4}
Edge{from=C, to=D, weight=5}
Edge{from=E, to=G, weight=6}
Edge{from=E, to=B, weight=7}
Edge{from=D, to=B, weight=8}
Edge{from=F, to=G, weight=9}
循環(huán)取出第1條邊A-C，判斷與已經(jīng)找到的最小生成樹不會(huì)形成環(huán)，權(quán)值總和增加1，繼續(xù)；
循環(huán)取出第2條邊D-A，判斷與已經(jīng)找到的最小生成樹不會(huì)形成環(huán)，權(quán)值總和增加2，繼續(xù)；
循環(huán)取出第3條邊A-F，判斷與已經(jīng)找到的最小生成樹不會(huì)形成環(huán)，權(quán)值總和增加3，繼續(xù)；
循環(huán)取出第4條邊B-C，判斷與已經(jīng)找到的最小生成樹不會(huì)形成環(huán)，權(quán)值總和增加4，繼續(xù)；
循環(huán)取出第5條邊C-D，判斷與已經(jīng)找到的最小生成樹會(huì)形成環(huán)，該條邊丟棄，繼續(xù)；
循環(huán)取出第6條邊E-G，判斷與已經(jīng)找到的最小生成樹不會(huì)形成環(huán)，權(quán)值總和增加6，繼續(xù)；
循環(huán)取出第7條邊E-B，判斷與已經(jīng)找到的最小生成樹不會(huì)形成環(huán)，權(quán)值總和增加7，繼續(xù)；
循環(huán)取出第8條邊D-B，判斷與已經(jīng)找到的最小生成樹會(huì)形成環(huán)，該條邊丟棄，繼續(xù)；
循環(huán)取出第9條邊F-G，判斷與已經(jīng)找到的最小生成樹會(huì)形成環(huán)，該條邊丟棄，繼續(xù)；
此時(shí)循環(huán)結(jié)束，那么最小生成樹也已經(jīng)找到了，最小生成樹的權(quán)值總和為23。
上面步驟中，判斷是否形成環(huán)很關(guān)鍵，通常的做法是，對(duì)已經(jīng)找到的最小生成樹的頂點(diǎn)進(jìn)行排序（從起點(diǎn)到終點(diǎn))，然后每新添加一條邊，就使用新添加邊的起點(diǎn)和終點(diǎn)取最小二叉樹中尋找，排序后的終點(diǎn)，找到的終點(diǎn)一致，則說明最小生成樹加上這條邊就會(huì)形成環(huán)，否則說明不會(huì)，那么更新排序的終點(diǎn)。
這里的實(shí)現(xiàn)能夠構(gòu)造一個(gè)基于鄰接矩陣實(shí)現(xiàn)無向加權(quán)圖的類，并且提供深度優(yōu)先遍歷和廣度優(yōu)先遍歷的方法，提供獲取邊集數(shù)組的方法，提供Prim和Kruskal兩種求最小生成樹的方法。
/**
* 無向加權(quán)圖鄰接矩陣實(shí)現(xiàn)
* {@link MatrixPrimAndKruskal#MatrixPrimAndKruskal(E[], Edge[])} 構(gòu)建無向加權(quán)圖
* {@link MatrixPrimAndKruskal#DFS()} 深度優(yōu)先遍歷無向加權(quán)圖
* {@link MatrixPrimAndKruskal#BFS()} 廣度優(yōu)先遍歷無向加權(quán)圖
* {@link MatrixPrimAndKruskal#toString()} 輸出無向加權(quán)圖
* {@link MatrixPrimAndKruskal#prim()} Prim算法實(shí)現(xiàn)最小生成樹
* {@link MatrixPrimAndKruskal#kruskal()} Kruskal算法實(shí)現(xiàn)最小生成樹
* {@link MatrixPrimAndKruskal#kruskalAndPrim()} Kruskal算法結(jié)合Prim算法實(shí)現(xiàn)最小生成樹
* {@link MatrixPrimAndKruskal#getEdges()} 獲取邊集數(shù)組
*
* @author lx
* @date 2020/5/14 18:13
*/
public class MatrixPrimAndKruskal<E> {
/**
* 頂點(diǎn)數(shù)組
*/
private Object[] vertexs;
/**
* 鄰接矩陣
*/
private int[][] matrix;
/**
*
*/
private Edge<E>[] edges;
/**
* 由于是加權(quán)圖,這里設(shè)置一個(gè)邊的權(quán)值上限,任何邊的最大權(quán)值不能大于等于該值，在實(shí)際應(yīng)用中，該值應(yīng)該根據(jù)實(shí)際情況確定
*/
private static final int NO_EDGE = 99;
/**
* 邊對(duì)象,具有權(quán)值,在構(gòu)建加權(quán)無向圖時(shí)使用
*/
private static class Edge<E> {
private E from;
private E to;
private int weight;
public Edge(E from, E to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
/**
* 創(chuàng)建無向加權(quán)圖
*
* @param vertexs 頂點(diǎn)數(shù)組
* @param edges 邊對(duì)象數(shù)組
*/
public MatrixPrimAndKruskal(Object[] vertexs, Edge<E>[] edges) {
//初始化邊數(shù)組
this.edges = edges;
// 初始化頂點(diǎn)數(shù)組,并添加頂點(diǎn)
this.vertexs = Arrays.copyOf(vertexs, vertexs.length);
// 初始化邊矩陣,并預(yù)先填充邊信息
this.matrix = new int[vertexs.length][vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
if (i == j) {
this.matrix[i][j] = 0;
} else {
this.matrix[i][j] = NO_EDGE;
}
}
}
for (Edge<E> edge : edges) {
// 讀取一條邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)索引值
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
//對(duì)稱的兩個(gè)點(diǎn)位都置為edge.weight,無向圖可以看作相互可達(dá)的有向圖
this.matrix[p1][p2] = edge.weight;
this.matrix[p2][p1] = edge.weight;
}
}
/**
* 獲取某條邊的某個(gè)頂點(diǎn)所在頂點(diǎn)數(shù)組的索引位置
*
* @param e 頂點(diǎn)的值
* @return 所在頂點(diǎn)數(shù)組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == e) {
return i;
}
}
return -1;
}
/**
* 深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,
*/
public void DFS() {
//新建頂點(diǎn)訪問標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點(diǎn)都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
DFS(i, visited);
}
}
System.out.println();
}
/**
* 深度優(yōu)先搜索遍歷圖的遞歸實(shí)現(xiàn),類似于樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點(diǎn)索引
* @param visited 訪問標(biāo)志數(shù)組
*/
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
// 遍歷該頂點(diǎn)的所有鄰接點(diǎn)。若該鄰接點(diǎn)是沒有訪問過，那么繼續(xù)遞歸遍歷領(lǐng)接點(diǎn)
for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
if (!visited[w]) {
DFS(w, visited);
}
}
}
/**
* 廣度優(yōu)先搜索圖,類似于樹的層序遍歷
* 因此模仿樹的層序遍歷,同樣借用隊(duì)列結(jié)構(gòu)
*/
public void BFS() {
// 輔組隊(duì)列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點(diǎn)訪問標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
boolean[] visited = new boolean[vertexs.length];
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
for (int i = 0; i < vertexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i] + " ");
indexLinkedList.add(i);
}
if (!indexLinkedList.isEmpty()) {
//j索引出隊(duì)列
Integer j = indexLinkedList.poll();
//繼續(xù)訪問j的鄰接點(diǎn)
for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k] + " ");
//繼續(xù)入隊(duì)列
indexLinkedList.add(k);
}
}
}
}
System.out.println();
}
/**
* 返回頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)的索引，失敗則返回-1
*
* @param v 頂點(diǎn)v在數(shù)組中的索引
* @return 返回頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)的索引，失敗則返回-1
*/
private int firstVertex(int v) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1)) {
return -1;
}
/*根據(jù)鄰接矩陣的規(guī)律:頂點(diǎn)索引v對(duì)應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
* 從i=0開始*/
for (int i = 0; i < vertexs.length; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) {
return i;
}
}
return -1;
}
/**
* 返回頂點(diǎn)v相對(duì)于w的下一個(gè)鄰接頂點(diǎn)的索引，失敗則返回-1
*
* @param v 頂點(diǎn)索引
* @param w 第一個(gè)鄰接點(diǎn)索引
* @return 返回頂點(diǎn)v相對(duì)于w的下一個(gè)鄰接頂點(diǎn)的索引，失敗則返回-1
*/
private int nextVertex(int v, int w) {
//如果索引超出范圍,則返回-1
if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
return -1;
}
/*根據(jù)鄰接矩陣的規(guī)律:頂點(diǎn)索引v對(duì)應(yīng)著邊二維矩陣的matrix[v][i]一行記錄
* 由于鄰接點(diǎn)w的索引已經(jīng)獲取了,所以從i=w+1開始尋找*/
for (int i = w + 1; i < vertexs.length; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != NO_EDGE) {
return i;
}
}
return -1;
}
/**
* 輸出圖
*
* @return 輸出圖字符串
*/
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
stringBuilder.append(matrix[i][j]).append("\t");
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
/**
* Prim算法求最小生成樹
*/
public void prim() {
System.out.println("prim: ");
//對(duì)應(yīng)節(jié)點(diǎn)應(yīng)該被連接的前驅(qū)節(jié)點(diǎn),用來輸出
//默認(rèn)為0,即前驅(qū)結(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)
int[] mid = new int[matrix.length];
//如果某頂點(diǎn)作為末端頂點(diǎn)被連接，對(duì)應(yīng)位置應(yīng)該為true
//第一個(gè)頂點(diǎn)默認(rèn)被連接
boolean[] connected = new boolean[matrix.length];
connected[0] = true;
//存儲(chǔ)未連接頂點(diǎn)到已連接頂點(diǎn)的最短距離(最小權(quán))
int[] dis = new int[matrix.length];
//首先將矩陣第一行即其他頂點(diǎn)到0索引頂點(diǎn)的權(quán)值拷貝進(jìn)去
System.arraycopy(matrix[0], 0, dis, 0, matrix.length);
//存儲(chǔ)路徑長(zhǎng)度
int sum = 0;
//最小權(quán)值
int min;
/*默認(rèn)第一個(gè)頂點(diǎn)已經(jīng)找到了,因此最多還要需要大循環(huán)n-1次*/
for (int k = 1; k < matrix.length; k++) {
min = NO_EDGE;
//最小權(quán)值的頂點(diǎn)的索引
int minIndex = 0;
/*尋找權(quán)值最小的且未被連接的頂點(diǎn)索引*/
for (int i = 1; i < matrix.length; i++) {
//排除已連接的頂點(diǎn),排除權(quán)值等于0的值,這里權(quán)值等于0表示已生成的最小生成樹的頂點(diǎn)都未能與該頂點(diǎn)連接
if (!connected[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIndex = i;
}
}
//如果沒找到,那么該圖可能不是連通圖,直接返回了,此時(shí)最小生成樹沒啥意義
if (minIndex == 0) {
return;
}
//權(quán)值和增加
sum += min;
//該新連接頂點(diǎn)對(duì)應(yīng)的索引值變成true,表示已被連接,后續(xù)判斷時(shí)跳過該頂點(diǎn)
connected[minIndex] = true;
//輸出對(duì)應(yīng)的前驅(qū)頂點(diǎn)到該最小頂點(diǎn)的權(quán)值
System.out.println(vertexs[mid[minIndex]] + " ---> " + vertexs[minIndex] + " 權(quán)值:" + min);
/*在新頂點(diǎn)minIndex加入之前的其他所有頂點(diǎn)到連接頂點(diǎn)最小的權(quán)值已經(jīng)計(jì)算過了
因此只需要更新其他未連接頂點(diǎn)到新連接頂點(diǎn)minIndex是否還有更短的權(quán)值,有的話就更新找到距離已連接的頂點(diǎn)權(quán)最小的頂點(diǎn)*/
for (int i = 1; i < matrix.length; i++) {
//如果該頂點(diǎn)未連接
if (!connected[i]) {
/*如果新頂點(diǎn)到未連接頂點(diǎn)i的權(quán)值不為0,并且比原始頂點(diǎn)到未連接頂點(diǎn)i的權(quán)值還要小,那么更新對(duì)應(yīng)位置的最小權(quán)值*/
if (matrix[minIndex][i] != 0 && dis[i] > matrix[minIndex][i]) {
//更新最小權(quán)值
dis[i] = matrix[minIndex][i];
//更新前驅(qū)節(jié)點(diǎn)索引為新加入節(jié)點(diǎn)索引
mid[i] = minIndex;
}
}
}
}
System.out.println("sum: " + sum);
}
/**
* Kruskal算法求最小生成樹傳統(tǒng)實(shí)現(xiàn),要求知道邊集數(shù)組,和頂點(diǎn)數(shù)組
*/
public void kruskal() {
System.out.println("Kruskal: ");
//由于創(chuàng)建圖的時(shí)候保存了邊集數(shù)組,這里直接使用就行了
//Edge[] edges = getEdges();
//this.edges=edges;
//對(duì)邊集數(shù)組進(jìn)行排序
Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
// 用于保存已有最小生成樹中每個(gè)頂點(diǎn)在該最小樹中的最終終點(diǎn)的索引
int[] vends = new int[this.edges.length];
//能夠知道終點(diǎn)索引范圍是[0,this.edges.length-1],因此填充edges.length表示沒有終點(diǎn)
Arrays.fill(vends, this.edges.length);
int sum = 0;
for (Edge<E> edge : this.edges) {
// 獲取第i條邊的起點(diǎn)索引from
int from = getPosition(edge.from);
// 獲取第i條邊的終點(diǎn)索引to
int to = getPosition(edge.to);
// 獲取頂點(diǎn)from在"已有的最小生成樹"中的終點(diǎn)
int m = getEndIndex(vends, from);
// 獲取頂點(diǎn)to在"已有的最小生成樹"中的終點(diǎn)
int n = getEndIndex(vends, to);
// 如果m!=n，意味著沒有形成環(huán)路,則可以添加,否則直接跳過,進(jìn)行下一條邊的判斷
if (m != n) {
//添加設(shè)置原始終點(diǎn)索引m在已有的最小生成樹中的終點(diǎn)為n
vends[m] = n;
System.out.println(vertexs[from] + " ---> " + vertexs[to] + " 權(quán)值:" + edge.weight);
sum += edge.weight;
}
}
System.out.println("sum: " + sum);
//System.out.println(Arrays.toString(this.edges));
}
/**
* 獲取頂點(diǎn)索引i的終點(diǎn)如果沒有終點(diǎn)則返回頂點(diǎn)索引本身
*
* @param vends 頂點(diǎn)在最小生成樹中的終點(diǎn)
* @param i 頂點(diǎn)索引
* @return 頂點(diǎn)索引i的終點(diǎn)如果沒有終點(diǎn)則返回頂點(diǎn)索引本身
*/
private int getEndIndex(int[] vends, int i) {
//這里使用循環(huán)查找的邏輯,尋找的是最終的終點(diǎn)
while (vends[i] != this.edges.length) {
i = vends[i];
}
return i;
}
/**
* 如果沒有現(xiàn)成的邊集數(shù)組，那么根據(jù)鄰接矩陣結(jié)構(gòu)獲取圖中的邊集數(shù)組
*
* @return 圖的邊集數(shù)組
*/
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
/*遍歷矩陣數(shù)組 只需要遍歷一半就行了*/
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
//如果存在邊
if (matrix[i][j] != NO_EDGE && matrix[i][j] != 0) {
edges.add(new Edge<>(vertexs[i], vertexs[j], matrix[i][j]));
//edges[index++] = new Edge(vertexs[i], vertexs[j], matrix[i][j]);
}
}
}
return edges.toArray(new Edge[0]);
}
/**
* Kruskal結(jié)合Prim算法.不需要知道邊集,只需要矩陣數(shù)組,和頂點(diǎn)數(shù)組
* 同樣是求最小權(quán)值的邊,但是有一個(gè)默認(rèn)起點(diǎn)頂點(diǎn),該起點(diǎn)可以是要求[0,頂點(diǎn)數(shù)量-1]之間的任意值，同時(shí)查找最小權(quán)的邊。
* 可能會(huì)有Bug,目前未發(fā)現(xiàn)
*/
public void kruskalAndPrim() {
System.out.println("kruskalAndPrim: ");
//已經(jīng)找到的邊攜帶的頂點(diǎn)對(duì)應(yīng)的索引將變?yōu)閠rue,其余未找到邊對(duì)應(yīng)的頂點(diǎn)將是false
boolean[] connected = new boolean[matrix.length];
//這里選擇第一個(gè)頂點(diǎn)為起點(diǎn),表示以該頂點(diǎn)開始尋找包含該頂點(diǎn)的最小邊
connected[0] = true;
int sum = 0, n1 = 0, n2 = 0;
//最小權(quán)值
int min;
while (true) {
min = NO_EDGE;
/*找出所有帶有已找到頂點(diǎn)的邊中,最小權(quán)值的邊,只需要尋找對(duì)稱矩陣的一半即可*/
//第一維
for (int i = 0; i < matrix.length; i++) {
//第二維
for (int j = i + 1; j < matrix.length; j++) {
//排除等于0的,排除兩個(gè)頂點(diǎn)都找到了的,這里實(shí)際上已經(jīng)隱含了排除環(huán)的邏輯,如果某條邊的兩個(gè)頂點(diǎn)都找到了,那么如果算上該條邊,肯定會(huì)形成環(huán)
//尋找剩下的最小的權(quán)值的邊
if (matrix[i][j] != 0 && connected[i] != connected[j] && matrix[i][j] < min) {
min = matrix[i][j];
n1 = i;
n2 = j;
}
}
}
//如果沒找到最小權(quán)值,該圖可能不是連通圖,或者已經(jīng)尋找完畢,直接返回
if (min == NO_EDGE) {
System.out.println(" sum:" + sum);
return;
}
//已經(jīng)找到的邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)都置為true
connected[n1] = true;
connected[n2] = true;
//輸出找到的邊和最小權(quán)值
System.out.println(vertexs[n1] + " ---> " + vertexs[n2] + " 權(quán)值:" + min);
sum += min;
}
}
public static void main(String[] args) {
//頂點(diǎn)數(shù)組
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊數(shù)組,加權(quán)值
Edge[] edges = {
new Edge<>('A', 'C', 1),
new Edge<>('D', 'A', 2),
new Edge<>('A', 'F', 3),
new Edge<>('B', 'C', 4),
new Edge<>('C', 'D', 5),
new Edge<>('E', 'G', 6),
new Edge<>('E', 'B', 7),
new Edge<>('D', 'B', 8),
new Edge<>('F', 'G', 9)};
//構(gòu)建圖
MatrixPrimAndKruskal<Character> matrixPrimAndKruskal = new MatrixPrimAndKruskal<Character>(vexs, edges);
//輸出圖
System.out.println(matrixPrimAndKruskal);
//深度優(yōu)先遍歷
matrixPrimAndKruskal.DFS();
//廣度優(yōu)先遍歷
matrixPrimAndKruskal.BFS();
//Prim算法輸出最小生成樹
matrixPrimAndKruskal.prim();
//Kruskal算法輸出最小生成樹
matrixPrimAndKruskal.kruskal();
//Kruskal算法結(jié)合Prim算法輸出最小生成樹,可能會(huì)有Bug,目前未發(fā)現(xiàn)
matrixPrimAndKruskal.kruskalAndPrim();
//獲取邊集數(shù)組
Edge[] edges1 = matrixPrimAndKruskal.getEdges();
System.out.println(Arrays.toString(edges1));
}
}這里的實(shí)現(xiàn)能夠構(gòu)造一個(gè)基于鄰接表實(shí)現(xiàn)無向加權(quán)圖的類；并且提供深度優(yōu)先遍歷和廣度優(yōu)先遍歷的方法，提供獲取邊集數(shù)組的方法，提供Prim和Kruskal兩種求最小生成樹的方法。
/**
* 無向加權(quán)圖鄰接表實(shí)現(xiàn)
* {@link ListPrimAndKruskal#ListPrimAndKruskal(E[], Edge[])} 構(gòu)建無向加權(quán)圖
* {@link ListPrimAndKruskal#DFS()} 深度優(yōu)先遍歷無向加權(quán)圖
* {@link ListPrimAndKruskal#BFS()} 廣度優(yōu)先遍歷無向加權(quán)圖
* {@link ListPrimAndKruskal#toString()} 輸出無向加權(quán)圖
* {@link ListPrimAndKruskal#prim()} Prim算法實(shí)現(xiàn)最小生成樹
* {@link ListPrimAndKruskal#kruskal()} Kruskal算法實(shí)現(xiàn)最小生成樹
* {@link ListPrimAndKruskal#getEdges()} 獲取邊集數(shù)組
*
* @author lx
* @date 2020/5/14 23:31
*/
public class ListPrimAndKruskal<E> {
/**
* 頂點(diǎn)類
*
* @param <E>
*/
private class Node<E> {
/**
* 頂點(diǎn)信息
*/
E data;
/**
* 指向第一條依附該頂點(diǎn)的邊
*/
LNode firstLNode;
public Node(E data, LNode firstLNode) {
this.data = data;
this.firstLNode = firstLNode;
}
}
/**
* 邊表節(jié)點(diǎn)類
*/
private class LNode {
/**
* 該邊所指向的頂點(diǎn)的索引位置
*/
int vertex;
/**
* 該邊的權(quán)值
*/
int weight;
/**
* 指向下一條邊的指針
*/
LNode nextLNode;
}
/**
* 邊對(duì)象,具有權(quán)值,在構(gòu)建加權(quán)無向圖時(shí)使用
*/
private static class Edge<E> {
private E from;
private E to;
private int weight;
public Edge(E from, E to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
/**
* 頂點(diǎn)數(shù)組
*/
private Node<E>[] vertexs;
/**
* 邊數(shù)組
*/
private Edge<E>[] edges;
/**
* 由于是加權(quán)圖,這里設(shè)置一個(gè)邊的權(quán)值上限,任何邊的最大權(quán)值不能大于等于該值，在實(shí)際應(yīng)用中，該值應(yīng)該根據(jù)實(shí)際情況確定
*/
private static final int NO_EDGE = 99;
/**
* 創(chuàng)建無向加權(quán)圖
*
* @param vexs 頂點(diǎn)數(shù)組
* @param edges 邊二維數(shù)組
*/
public ListPrimAndKruskal(E[] vexs, Edge<E>[] edges) {
this.edges = edges;
/*初始化頂點(diǎn)數(shù)組,并添加頂點(diǎn)*/
vertexs = new Node[vexs.length];
for (int i = 0; i < vertexs.length; i++) {
vertexs[i] = new Node<>(vexs[i], null);
}
/*初始化邊表,并添加邊節(jié)點(diǎn)到邊表尾部,即采用尾插法*/
for (Edge<E> edge : edges) {
// 讀取一條邊的起始頂點(diǎn)和結(jié)束頂點(diǎn)索引值
int p1 = getPosition(edge.from);
int p2 = getPosition(edge.to);
int weight = edge.weight;
/*這里需要相互添加邊節(jié)點(diǎn),無向圖可以看作相互可達(dá)的有向圖*/
// 初始化lnode1邊節(jié)點(diǎn)
LNode lnode1 = new LNode();
lnode1.vertex = p2;
lnode1.weight = weight;
// 將LNode鏈接到"p1所在鏈表的末尾"
if (vertexs[p1].firstLNode == null) {
vertexs[p1].firstLNode = lnode1;
} else {
linkLast(vertexs[p1].firstLNode, lnode1);
}
// 初始化lnode2邊節(jié)點(diǎn)
LNode lnode2 = new LNode();
lnode2.vertex = p1;
lnode2.weight = weight;
// 將lnode2鏈接到"p2所在鏈表的末尾"
if (vertexs[p2].firstLNode == null) {
vertexs[p2].firstLNode = lnode2;
} else {
linkLast(vertexs[p2].firstLNode, lnode2);
}
}
}
/**
* 獲取某條邊的某個(gè)頂點(diǎn)所在頂點(diǎn)數(shù)組的索引位置
*
* @param e 頂點(diǎn)的值
* @return 所在頂點(diǎn)數(shù)組的索引位置, 或者-1 - 表示不存在
*/
private int getPosition(E e) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i].data == e) {
return i;
}
}
return -1;
}
/**
* 將lnode節(jié)點(diǎn)鏈接到邊表的最后,采用尾插法
*
* @param first 邊表頭結(jié)點(diǎn)
* @param node 將要添加的節(jié)點(diǎn)
*/
private void linkLast(LNode first, LNode node) {
while (true) {
if (first.vertex == node.vertex) {
return;
}
if (first.nextLNode == null) {
break;
}
first = first.nextLNode;
}
first.nextLNode = node;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < vertexs.length; i++) {
stringBuilder.append(i).append("(").append(vertexs[i].data).append("): ");
LNode node = vertexs[i].firstLNode;
while (node != null) {
stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append("-").append(node.weight).append(")");
node = node.nextLNode;
if (node != null) {
stringBuilder.append("->");
} else {
break;
}
}
stringBuilder.append("\n");
}
return stringBuilder.toString();
}
/**
* 深度優(yōu)先搜索遍歷圖的遞歸實(shí)現(xiàn),類似于樹的先序遍歷
* 因此模仿樹的先序遍歷,同樣借用棧結(jié)構(gòu),這里使用的是方法的遞歸,隱式的借用棧
*
* @param i 頂點(diǎn)索引
* @param visited 訪問標(biāo)志數(shù)組
*/
private void DFS(int i, boolean[] visited) {
//索引索引標(biāo)記為true ,表示已經(jīng)訪問了
visited[i] = true;
System.out.print(vertexs[i].data + " ");
//獲取該頂點(diǎn)的邊表頭結(jié)點(diǎn)
LNode node = vertexs[i].firstLNode;
//循環(huán)遍歷該頂點(diǎn)的鄰接點(diǎn),采用同樣的方式遞歸搜索
while (node != null) {
if (!visited[node.vertex]) {
DFS(node.vertex, visited);
}
node = node.nextLNode;
}
}
/**
* 深度優(yōu)先搜索遍歷圖,類似于樹的前序遍歷,
*/
public void DFS() {
//新建頂點(diǎn)訪問標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點(diǎn)都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("DFS: ");
/*循環(huán)搜索*/
for (int i = 0; i < vertexs.length; i++) {
//如果對(duì)應(yīng)索引的頂點(diǎn)的訪問標(biāo)記為false,則搜索該頂點(diǎn)
if (!visited[i]) {
DFS(i, visited);
}
}
/*走到這一步,說明頂點(diǎn)訪問標(biāo)記數(shù)組全部為true,說明全部都訪問到了,深度搜索結(jié)束*/
System.out.println();
}
/**
* 廣度優(yōu)先搜索圖,類似于樹的層序遍歷
* 因此模仿樹的層序遍歷,同樣借用隊(duì)列結(jié)構(gòu)
*/
public void BFS() {
// 輔組隊(duì)列
Queue<Integer> indexLinkedList = new LinkedList<>();
//新建頂點(diǎn)訪問標(biāo)記數(shù)組,對(duì)應(yīng)每個(gè)索引對(duì)應(yīng)相同索引的頂點(diǎn)數(shù)組中的頂點(diǎn)
boolean[] visited = new boolean[vertexs.length];
//初始化所有頂點(diǎn)都沒有被訪問
for (int i = 0; i < vertexs.length; i++) {
visited[i] = false;
}
System.out.println("BFS: ");
for (int i = 0; i < vertexs.length; i++) {
//如果訪問方劑為false,則設(shè)置為true,表示已經(jīng)訪問,然后開始訪問
if (!visited[i]) {
visited[i] = true;
System.out.print(vertexs[i].data + " ");
indexLinkedList.add(i);
}
//判斷隊(duì)列是否有值,有就開始遍歷
if (!indexLinkedList.isEmpty()) {
//出隊(duì)列
Integer j = indexLinkedList.poll();
LNode node = vertexs[j].firstLNode;
while (node != null) {
int k = node.vertex;
if (!visited[k]) {
visited[k] = true;
System.out.print(vertexs[k].data + " ");
//繼續(xù)入隊(duì)列
indexLinkedList.add(k);
}
node = node.nextLNode;
}
}
}
System.out.println();
}
/**
* Prim算法求最小生成樹
*/
public void prim() {
System.out.println("prim: ");
//對(duì)應(yīng)節(jié)點(diǎn)應(yīng)該被連接的前驅(qū)節(jié)點(diǎn),用來輸出
//默認(rèn)為0,即前驅(qū)結(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)
int[] mid = new int[vertexs.length];
int start = 0;
int min, tmp, sum = 0;
int num = vertexs.length;
//頂點(diǎn)間邊的權(quán)值
//存儲(chǔ)未連接頂點(diǎn)到已連接頂點(diǎn)的最短距離(最小權(quán))
int[] dis = new int[num];
// 初始化"頂點(diǎn)的權(quán)值數(shù)組"，
// 將每個(gè)頂點(diǎn)的權(quán)值初始化為"第start個(gè)頂點(diǎn)"到"該頂點(diǎn)"的權(quán)值。
//首先將其他頂點(diǎn)到0索引頂點(diǎn)的權(quán)值存儲(chǔ)進(jìn)去
for (int i = 0; i < num; i++) {
dis[i] = getWeight(start, i);
}
//如果某頂點(diǎn)作為末端頂點(diǎn)被連接，對(duì)應(yīng)位置應(yīng)該為true
//第一個(gè)頂點(diǎn)默認(rèn)被連接
boolean[] connected = new boolean[vertexs.length];
connected[0] = true;
/*默認(rèn)第一個(gè)頂點(diǎn)已經(jīng)找到了,因此最多還要需要大循環(huán)n-1次*/
for (int k = 1; k < num; k++) {
min = NO_EDGE;
//最小權(quán)值的頂點(diǎn)的索引
int minIndex = 0;
// 在未被加入到最小生成樹的頂點(diǎn)中，找出權(quán)值最小的頂點(diǎn)。
for (int i = 1; i < vertexs.length; i++) {
//排除已連接的頂點(diǎn),排除權(quán)值等于0的值,因?yàn)檫@里默認(rèn)頂點(diǎn)指向自己的權(quán)值為0
if (!connected[i] && dis[i] != 0 && dis[i] < min) {
min = dis[i];
minIndex = i;
}
}
//如果沒找到,那么該圖可能不是連通圖,直接返回了,此時(shí)最小生成樹沒啥意義
if (minIndex == 0) {
return;
}
//權(quán)值和增加
sum += min;
//該新連接頂點(diǎn)對(duì)應(yīng)的索引值變成true,表示已被連接,后續(xù)判斷時(shí)跳過該頂點(diǎn)
connected[minIndex] = true;
//輸出對(duì)應(yīng)的前驅(qū)頂點(diǎn)到該最小頂點(diǎn)的權(quán)值
System.out.println(vertexs[mid[minIndex]].data + " ---> " + vertexs[minIndex].data + " 權(quán)值:" + min);
/*在新頂點(diǎn)minIndex加入之前的其他所有頂點(diǎn)到連接頂點(diǎn)最小的權(quán)值已經(jīng)計(jì)算過了
因此只需要更新其他頂點(diǎn)到新連接頂點(diǎn)minIndex是否還有更短的權(quán)值,有的話就更新找到距離已連接的頂點(diǎn)權(quán)最小的頂點(diǎn)*/
for (int i = 1; i < num; i++) {
//如果該頂點(diǎn)未連接
if (!connected[i]) {
// 獲取minindex頂點(diǎn)到未連接頂點(diǎn)i的權(quán)值
tmp = getWeight(minIndex, i);
/*如果新頂點(diǎn)到未連接頂點(diǎn)i的權(quán)值不為0,并且比原始頂點(diǎn)到未連接頂點(diǎn)i的權(quán)值還要小,那么更新對(duì)應(yīng)位置的最小權(quán)值*/
if (tmp != 0 && dis[i] > tmp) {
dis[i] = tmp;
//更新前驅(qū)節(jié)點(diǎn)索引為新加入節(jié)點(diǎn)索引
mid[i] = minIndex;
}
}
}
}
System.out.println("sum: " + sum);
}
/**
* 嘗試獲取邊起點(diǎn)start到邊終點(diǎn)end的邊的權(quán)值,當(dāng)然可能獲取不到
*
* @param start 邊起點(diǎn)
* @param end 邊終點(diǎn)
* @return 返回權(quán)值; 如果起點(diǎn)和終點(diǎn)相同則返回0;如果邊起點(diǎn)和邊終點(diǎn)之間并沒有邊, 則返回NO_EDGE
*/
private int getWeight(int start, int end) {
//如果start=end，則返回0
if (start == end) {
return 0;
}
//獲取該頂點(diǎn)的邊表的第一個(gè)值
LNode node = vertexs[start].firstLNode;
//循環(huán)查找邊表,看能否找到對(duì)應(yīng)的索引=end,找不到就返回NO_EDGE,表示兩個(gè)頂點(diǎn)未連接。
while (node != null) {
if (end == node.vertex) {
return node.weight;
}
node = node.nextLNode;
}
return NO_EDGE;
}
/**
* Kruskal算法求最小生成樹,可以說鄰接矩陣和鄰接鏈表的實(shí)現(xiàn)方式是完全一致的
*/
public void kruskal() {
//由于創(chuàng)建圖的時(shí)候保存了邊集數(shù)組,這里直接使用就行了
//Edge[] edges = getEdges();
//this.edges=edges;
//對(duì)邊集數(shù)組進(jìn)行排序
Arrays.sort(this.edges, Comparator.comparingInt(o -> o.weight));
// 用于保存已有最小生成樹中每個(gè)頂點(diǎn)在該最小樹中的最終終點(diǎn)的索引
int[] vends = new int[this.edges.length];
//能夠知道終點(diǎn)索引范圍是[0,this.edges.length-1],因此填充edges.length表示沒有終點(diǎn)
Arrays.fill(vends, this.edges.length);
int sum = 0;
for (Edge<E> edge : this.edges) {
// 獲取第i條邊的起點(diǎn)索引from
int from = getPosition(edge.from);
// 獲取第i條邊的終點(diǎn)索引to
int to = getPosition(edge.to);
// 獲取頂點(diǎn)from在"已有的最小生成樹"中的終點(diǎn)
int m = getEndIndex(vends, from);
// 獲取頂點(diǎn)to在"已有的最小生成樹"中的終點(diǎn)
int n = getEndIndex(vends, to);
// 如果m!=n，意味著沒有形成環(huán)路,則可以添加,否則直接跳過,進(jìn)行下一條邊的判斷
if (m != n) {
//添加設(shè)置原始終點(diǎn)索引m在已有的最小生成樹中的終點(diǎn)為n
vends[m] = n;
System.out.println(vertexs[from].data + " ---> " + vertexs[to].data + " 權(quán)值:" + edge.weight);
sum += edge.weight;
}
}
System.out.println("sum: " + sum);
//System.out.println(Arrays.toString(this.edges));
}
/**
* 獲取頂點(diǎn)索引i的終點(diǎn)如果沒有終點(diǎn)則返回頂點(diǎn)索引本身
*
* @param vends 頂點(diǎn)在最小生成樹中的終點(diǎn)
* @param i 頂點(diǎn)索引
* @return 頂點(diǎn)索引i的終點(diǎn)如果沒有終點(diǎn)則返回頂點(diǎn)索引本身
*/
private int getEndIndex(int[] vends, int i) {
//這里使用循環(huán)查找的邏輯,尋找的是最終的終點(diǎn)
while (vends[i] != this.edges.length) {
i = vends[i];
}
return i;
}
/**
* 如果沒有現(xiàn)成的邊集數(shù)組，那么根據(jù)鄰接表結(jié)構(gòu)獲取圖中的邊集數(shù)組
*
* @return 圖的邊集數(shù)組
*/
private Edge[] getEdges() {
List<Edge> edges = new ArrayList<>();
//遍歷頂點(diǎn)數(shù)組
for (int i = 0; i < vertexs.length; i++) {
LNode node = vertexs[i].firstLNode;
while (node != null) {
//只需添加起點(diǎn)索引小于終點(diǎn)索引的邊就行了
if (node.vertex > i) {
edges.add(new Edge<>(vertexs[i].data, vertexs[node.vertex].data, node.weight));
}
node = node.nextLNode;
}
}
return edges.toArray(new Edge[0]);
}
public static void main(String[] args) {
//頂點(diǎn)數(shù)組
Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//邊數(shù)組,加權(quán)值
Edge[] edges = {
new Edge('A', 'C', 1),
new Edge('D', 'A', 2),
new Edge('A', 'F', 3),
new Edge('B', 'C', 4),
new Edge('C', 'D', 5),
new Edge('E', 'G', 6),
new Edge('E', 'B', 7),
new Edge('D', 'B', 8),
new Edge('F', 'G', 9)};
//構(gòu)建圖
ListPrimAndKruskal<Character> listPrimAndKruskal = new ListPrimAndKruskal<Character>(vexs, edges);
//輸出圖
System.out.println(listPrimAndKruskal);
//深度優(yōu)先遍歷
//DFS:
//A C B E G F D
listPrimAndKruskal.DFS();
//廣度優(yōu)先遍歷
//BFS:
//A C D F B G E
listPrimAndKruskal.BFS();
//Prim算法求最小生成樹
listPrimAndKruskal.prim();
//Kruskal算法求最小生成樹
listPrimAndKruskal.kruskal();
//獲取邊集數(shù)組
Edge[] edges1 = listPrimAndKruskal.getEdges();
System.out.println(Arrays.toString(edges1));
}
}關(guān)于“Java如何求最小生成樹”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼