欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

帶你了解Java數(shù)據(jù)結構和算法之無權無向圖

 更新時間:2022年01月23日 16:51:58   作者:YSOcean  
這篇文章主要為大家介紹了Java數(shù)據(jù)結構和算法之無權無向圖?,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助

1、圖的定義

我們知道,前面討論的數(shù)據(jù)結構都有一個框架,而這個框架是由相應的算法實現(xiàn)的,比如二叉樹搜索樹,左子樹上所有結點的值均小于它的根結點的值,右子樹所有結點的值均大于它的根節(jié)點的值,類似這種形狀使得它容易搜索數(shù)據(jù)和插入數(shù)據(jù),樹的邊表示了從一個節(jié)點到另一個節(jié)點的快捷方式。

而圖通常有個固定的形狀,這是由物理或抽象的問題所決定的。比如圖中節(jié)點表示城市,而邊可能表示城市間的班機航線。如下圖是美國加利福利亞簡化的高速公路網(wǎng):

①、鄰接:

如果兩個頂點被同一條邊連接,就稱這兩個頂點是鄰接的,如上圖 I 和 G 就是鄰接的,而 I 和 F 就不是。有時候也將和某個指定頂點鄰接的頂點叫做它的鄰居,比如頂點 G 的鄰居是 I、H、F。

②、路徑:

路徑是邊的序列,比如從頂點B到頂點J的路徑為 BAEJ,當然還有別的路徑 BCDJ,BACDJ等等。

③、連通圖和非連通圖:

如果至少有一條路徑可以連接起所有的頂點,那么這個圖稱作連通的;如果假如存在從某個頂點不能到達另外一個頂點,則稱為非聯(lián)通的。

④、有向圖和無向圖:

如果圖中的邊沒有方向,可以從任意一邊到達另一邊,則稱為無向圖;比如雙向高速公路,A城市到B城市可以開車從A駛向B,也可以開車從B城市駛向A城市。但是如果只能從A城市駛向B城市的圖,那么則稱為有向圖。

⑤、有權圖和無權圖:

圖中的邊被賦予一個權值,權值是一個數(shù)字,它能代表兩個頂點間的物理距離,或者從一個頂點到另一個頂點的時間,這種圖被稱為有權圖;反之邊沒有賦值的則稱為無權圖。

本篇博客我們討論的是無權無向圖。

2、在程序中表示圖

我們知道圖是由頂點和邊組成,那么在計算機中,怎么來模擬頂點和邊?

①、頂點:

在大多數(shù)情況下,頂點表示某個真實世界的對象,這個對象必須用數(shù)據(jù)項來描述。比如在一個飛機航線模擬程序中,頂點表示城市,那么它需要存儲城市的名字、海拔高度、地理位置和其它相關信息,因此通常用一個頂點類的對象來表示一個頂點,這里我們僅僅在頂點中存儲了一個字母來標識頂點,同時還有一個標志位,用來判斷該頂點有沒有被訪問過(用于后面的搜索)。

/**
 * 頂點類
 * @author vae
 */
public class Vertex {
    public char label;
    public boolean wasVisited;
    public Vertex(char label){
        this.label = label;
        wasVisited = false;
    }
}

頂點對象能放在數(shù)組中,然后用下標指示,也可以放在鏈表或其它數(shù)據(jù)結構中,不論使用什么結構,存儲只是為了使用方便,這與邊如何連接點是沒有關系的。

②、邊:

在前面講解各種樹的數(shù)據(jù)結構時,大多數(shù)樹都是每個節(jié)點包含它的子節(jié)點的引用,比如紅黑樹、二叉樹。也有用數(shù)組表示樹,樹組中節(jié)點的位置決定了它和其它節(jié)點的關系,比如堆就是用數(shù)組表示。

然而圖并不像樹,圖沒有固定的結構,圖的每個頂點可以與任意多個頂點相連,為了模擬這種自由形式的組織結構,用如下兩種方式表示圖:鄰接矩陣和鄰接表(如果一條邊連接兩個頂點,那么這兩個頂點就是鄰接的)

鄰接矩陣:

鄰接矩陣是一個二維數(shù)組,數(shù)據(jù)項表示兩點間是否存在邊,如果圖中有 N 個頂點,鄰接矩陣就是 N*N 的數(shù)組。上圖用鄰接矩陣表示如下:  

1表示有邊,0表示沒有邊,也可以用布爾變量true和false來表示。頂點與自身相連用 0 表示,所以這個矩陣從左上角到右上角的對角線全是 0 。

注意:這個矩陣的上三角是下三角的鏡像,兩個三角包含了相同的信息,這個冗余信息看似低效,但是在大多數(shù)計算機中,創(chuàng)造一個三角形數(shù)組比較困難,所以只好接受這個冗余,這也要求在程序處理中,當我們增加一條邊時,比如更新鄰接矩陣的兩部分,而不是一部分。

鄰接表:

鄰接表是一個鏈表數(shù)組(或者是鏈表的鏈表),每個單獨的鏈表表示了有哪些頂點與當前頂點鄰接。

   

3、搜索

在圖中實現(xiàn)最基本的操作之一就是搜索從一個指定頂點可以到達哪些頂點,比如從武漢出發(fā)的高鐵可以到達哪些城市,一些城市可以直達,一些城市不能直達?,F(xiàn)在有一份全國高鐵模擬圖,要從某個城市(頂點)開始,沿著鐵軌(邊)移動到其他城市(頂點),有兩種方法可以用來搜索圖:深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。它們最終都會到達所有連通的頂點,深度優(yōu)先搜索通過棧來實現(xiàn),而廣度優(yōu)先搜索通過隊列來實現(xiàn),不同的實現(xiàn)機制導致不同的搜索方式。

①、深度優(yōu)先搜索(DFS)

深度優(yōu)先搜索算法有如下規(guī)則:

規(guī)則1:如果可能,訪問一個鄰接的未訪問頂點,標記它,并將它放入棧中。

規(guī)則2:當不能執(zhí)行規(guī)則 1 時,如果棧不為空,就從棧中彈出一個頂點。

規(guī)則3:如果不能執(zhí)行規(guī)則 1 和規(guī)則 2 時,就完成了整個搜索過程。

對于上圖,應用深度優(yōu)先搜索如下:假設選取 A 頂點為起始點,并且按照字母優(yōu)先順序進行訪問,那么應用規(guī)則 1 ,接下來訪問頂點 B,然后標記它,并將它放入棧中;再次應用規(guī)則 1,接下來訪問頂點 F,再次應用規(guī)則 1,訪問頂點 H。我們這時候發(fā)現(xiàn),沒有 H 頂點的鄰接點了,這時候應用規(guī)則 2,從棧中彈出 H,這時候回到了頂點 F,但是我們發(fā)現(xiàn) F 也除了 H 也沒有與之鄰接且未訪問的頂點了,那么再彈出 F,這時候回到頂點 B,同理規(guī)則 1 應用不了,應用規(guī)則 2,彈出 B,這時候棧中只有頂點 A了,然后 A 還有未訪問的鄰接點,所有接下來訪問頂點 C,但是 C又是這條線的終點,所以從棧中彈出它,再次回到 A,接著訪問 D,G,I,最后也回到了 A,然后訪問 E,但是最后又回到了頂點 A,這時候我們發(fā)現(xiàn) A沒有未訪問的鄰接點了,所以也把它彈出?!,F(xiàn)在棧中已無頂點,于是應用規(guī)則 3,完成了整個搜索過程。

深度優(yōu)先搜索在于能夠找到與某一頂點鄰接且沒有訪問過的頂點。這里以鄰接矩陣為例,找到頂點所在的行,從第一列開始向后尋找值為1的列;列號是鄰接頂點的號碼,檢查這個頂點是否未訪問過,如果是這樣,那么這就是要訪問的下一個頂點,如果該行沒有頂點既等于1(鄰接)且又是未訪問的,那么與指定點相鄰接的頂點就全部訪問過了(后面會用算法實現(xiàn))。

②、廣度優(yōu)先搜索(BFS)

深度優(yōu)先搜索要盡可能的遠離起始點,而廣度優(yōu)先搜索則要盡可能的靠近起始點,它首先訪問起始頂點的所有鄰接點,然后再訪問較遠的區(qū)域,這種搜索不能用棧實現(xiàn),而是用隊列實現(xiàn)。

規(guī)則1:訪問下一個未訪問的鄰接點(如果存在),這個頂點必須是當前頂點的鄰接點,標記它,并把它插入到隊列中。

規(guī)則2:如果已經(jīng)沒有未訪問的鄰接點而不能執(zhí)行規(guī)則 1 時,那么從隊列列頭取出一個頂點(如果存在),并使其成為當前頂點。

規(guī)則3:如果因為隊列為空而不能執(zhí)行規(guī)則 2,則搜索結束。

對于上面的圖,應用廣度優(yōu)先搜索:以A為起始點,首先訪問所有與 A 相鄰的頂點,并在訪問的同時將其插入隊列中,現(xiàn)在已經(jīng)訪問了 A,B,C,D和E。這時隊列(從頭到尾)包含 BCDE,已經(jīng)沒有未訪問的且與頂點 A 鄰接的頂點了,所以從隊列中取出B,尋找與B鄰接的頂點,這時找到F,所以把F插入到隊列中。已經(jīng)沒有未訪問且與B鄰接的頂點了,所以從隊列列頭取出C,它沒有未訪問的鄰接點。因此取出 D 并訪問 G,D也沒有未訪問的鄰接點了,所以取出E,現(xiàn)在隊列中有 FG,在取出 F,訪問 H,然后取出 G,訪問 I,現(xiàn)在隊列中有 HI,當取出他們時,發(fā)現(xiàn)沒有其它為訪問的頂點了,這時隊列為空,搜索結束。

③、程序實現(xiàn)

實現(xiàn)深度優(yōu)先搜索的棧StackX.class

package com.ys.graph;
public class StackX {
    private final int SIZE = 20;
    private int[] st;
    private int top;
    public StackX(){
        st = new int[SIZE];
        top = -1;
    }
    public void push(int j){
        st[++top] = j;
    }
    public int pop(){
        return st[top--];
    }
    public int peek(){
        return st[top];
    }
    public boolean isEmpty(){
        return (top == -1);
    }
}

實現(xiàn)廣度優(yōu)先搜索的隊列Queue.class

package com.ys.graph;
public class Queue {
    private final int SIZE = 20;
    private int[] queArray;
    private int front;
    private int rear;
    public Queue(){
        queArray = new int[SIZE];
        front = 0;
        rear = -1;
    }
    public void insert(int j) {
        if(rear == SIZE-1) {
            rear = -1;
        }
        queArray[++rear] = j;
    }
    public int remove() {
        int temp = queArray[front++];
        if(front == SIZE) {
            front = 0;
        }
        return temp;
    }
    public boolean isEmpty() {
        return (rear+1 == front || front+SIZE-1 == rear);
    }
}

圖代碼 Graph.class

package com.ys.graph;
public class Graph {
    private final int MAX_VERTS = 20;//表示頂點的個數(shù)
    private Vertex vertexList[];//用來存儲頂點的數(shù)組
    private int adjMat[][];//用鄰接矩陣來存儲 邊,數(shù)組元素0表示沒有邊界,1表示有邊界
    private int nVerts;//頂點個數(shù)
    private StackX theStack;//用棧實現(xiàn)深度優(yōu)先搜索
    private Queue queue;//用隊列實現(xiàn)廣度優(yōu)先搜索
    /**
     * 頂點類
     * @author vae
     */
    class Vertex {
        public char label;
        public boolean wasVisited;
        public Vertex(char label){
            this.label = label;
            wasVisited = false;
        }
    }
    public Graph(){
        vertexList = new Vertex[MAX_VERTS];
        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;//初始化頂點個數(shù)為0
        //初始化鄰接矩陣所有元素都為0,即所有頂點都沒有邊
        for(int i = 0; i < MAX_VERTS; i++) {
            for(int j = 0; j < MAX_VERTS; j++) {
                adjMat[i][j] = 0;
            }
        }
        theStack = new StackX();
        queue = new Queue();
    }
    //將頂點添加到數(shù)組中,是否訪問標志置為wasVisited=false(未訪問)
    public void addVertex(char lab) {
        vertexList[nVerts++] = new Vertex(lab);
    }
    //注意用鄰接矩陣表示邊,是對稱的,兩部分都要賦值
    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }
    //打印某個頂點表示的值
    public void displayVertex(int v) {
        System.out.print(vertexList[v].label);
    }
    /**深度優(yōu)先搜索算法:
     * 1、用peek()方法檢查棧頂?shù)捻旤c
     * 2、用getAdjUnvisitedVertex()方法找到當前棧頂點鄰接且未被訪問的頂點
     * 3、第二步方法返回值不等于-1則找到下一個未訪問的鄰接頂點,訪問這個頂點,并入棧
     *    如果第二步方法返回值等于 -1,則沒有找到,出棧
     */
    public void depthFirstSearch() {
        //從第一個頂點開始訪問
        vertexList[0].wasVisited = true; //訪問之后標記為true
        displayVertex(0);//打印訪問的第一個頂點
        theStack.push(0);//將第一個頂點放入棧中
        while(!theStack.isEmpty()) {
            //找到棧當前頂點鄰接且未被訪問的頂點
            int v = getAdjUnvisitedVertex(theStack.peek());
            if(v == -1) {   //如果當前頂點值為-1,則表示沒有鄰接且未被訪問頂點,那么出棧頂點
                theStack.pop();
            }else { //否則訪問下一個鄰接頂點
                vertexList[v].wasVisited = true;
                displayVertex(v);
                theStack.push(v);
            }
        }
        //棧訪問完畢,重置所有標記位wasVisited=false
        for(int i = 0; i < nVerts; i++) {
            vertexList[i].wasVisited = false;
        }
    }
    //找到與某一頂點鄰接且未被訪問的頂點
    public int getAdjUnvisitedVertex(int v) {
        for(int i = 0; i < nVerts; i++) {
            //v頂點與i頂點相鄰(鄰接矩陣值為1)且未被訪問 wasVisited==false
            if(adjMat[v][i] == 1 && vertexList[i].wasVisited == false) {
                return i;
            }
        }
        return -1;
    }
    /**
     * 廣度優(yōu)先搜索算法:
     * 1、用remove()方法檢查棧頂?shù)捻旤c
     * 2、試圖找到這個頂點還未訪問的鄰節(jié)點
     * 3、 如果沒有找到,該頂點出列
     * 4、 如果找到這樣的頂點,訪問這個頂點,并把它放入隊列中
     */
    public void breadthFirstSearch(){
        vertexList[0].wasVisited = true;
        displayVertex(0);
        queue.insert(0);
        int v2;
        while(!queue.isEmpty()) {
            int v1 = queue.remove();
            while((v2 = getAdjUnvisitedVertex(v1)) != -1) {
                vertexList[v2].wasVisited = true;
                displayVertex(v2);
                queue.insert(v2);
            }
        }
        //搜索完畢,初始化,以便于下次搜索
        for(int i = 0; i < nVerts; i++) {
            vertexList[i].wasVisited = false;
        }
    }
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');
        graph.addVertex('E');
        graph.addEdge(0, 1);//AB
        graph.addEdge(1, 2);//BC
        graph.addEdge(0, 3);//AD
        graph.addEdge(3, 4);//DE
        System.out.println("深度優(yōu)先搜索算法 :");
        graph.depthFirstSearch();//ABCDE
        System.out.println();
        System.out.println("----------------------");
        System.out.println("廣度優(yōu)先搜索算法 :");
        graph.breadthFirstSearch();//ABDCE
    }
}

測試結果:

4、最小生成樹

對于圖的操作,還有一個最常用的就是找到最小生成樹,最小生成樹就是用最少的邊連接所有頂點。對于給定的一組頂點,可能有很多種最小生成樹,但是最小生成樹的邊的數(shù)量 E 總是比頂點 V 的數(shù)量小1,即:

V = E + 1

這里不用關心邊的長度,不是找最短的路徑(會在帶權圖中講解),而是找最少數(shù)量的邊,可以基于深度優(yōu)先搜索和廣度優(yōu)先搜索來實現(xiàn)。

比如基于深度優(yōu)先搜索,我們記錄走過的邊,就可以創(chuàng)建一個最小生成樹。因為DFS 訪問所有頂點,但只訪問一次,它絕對不會兩次訪問同一個頂點,但她看到某條邊將到達一個已訪問的頂點,它就不會走這條邊,它從來不遍歷那些不可能的邊,因此,DFS 算法走過整個圖的路徑必定是最小生成樹。

//基于深度優(yōu)先搜索找到最小生成樹
public void mst(){
    vertexList[0].wasVisited = true;
    theStack.push(0);
    while(!theStack.isEmpty()){
        int currentVertex = theStack.peek();
        int v = getAdjUnvisitedVertex(currentVertex);
        if(v == -1){
            theStack.pop();
        }else{
            vertexList[v].wasVisited = true;
            theStack.push(v);
            displayVertex(currentVertex);
            displayVertex(v);
            System.out.print(" ");
        }
    }
    //搜索完畢,初始化,以便于下次搜索
    for(int i = 0; i < nVerts; i++) {
        vertexList[i].wasVisited = false;
    }
}

5、總結

圖是由邊連接的頂點組成,圖可以表示許多真實的世界情況,包括飛機航線、電子線路等等。搜索算法以一種系統(tǒng)的方式訪問圖中的每個頂點,主要通過深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS),深度優(yōu)先搜索通過棧來實現(xiàn),廣度優(yōu)先搜索通過隊列來實現(xiàn)。最后需要知道最小生成樹是包含連接圖中所有頂點所需要的最少數(shù)量的邊。

本篇文章就到這里了,希望能夠給你帶來幫助,也希望您能夠多多關注腳本之家的更多內(nèi)容!

相關文章

  • 全面解析Java main方法

    全面解析Java main方法

    main方法是我們學習Java語言學習的第一個方法,也是每個java使用者最熟悉的方法,每個Java應用程序都必須有且僅有一個main方法。這篇文章通過實例代碼給大家介紹java main方法的相關知識,感興趣的朋友跟隨腳本之家小編一起學習吧
    2018-05-05
  • IDEA修改idea64.exe.vmoptions文件以及解決coding卡頓問題

    IDEA修改idea64.exe.vmoptions文件以及解決coding卡頓問題

    IDEA修改idea64.exe.vmoptions文件以及解決coding卡頓問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-04-04
  • Spring?Boot中記錄用戶系統(tǒng)操作流程

    Spring?Boot中記錄用戶系統(tǒng)操作流程

    這篇文章主要介紹了如何在Spring?Boot中記錄用戶系統(tǒng)操作流程,將介紹如何在Spring?Boot中使用AOP(面向切面編程)和日志框架來實現(xiàn)用戶系統(tǒng)操作流程的記錄,需要的朋友可以參考下
    2023-07-07
  • druid配置數(shù)據(jù)庫連接使用密文密碼方式

    druid配置數(shù)據(jù)庫連接使用密文密碼方式

    這篇文章主要介紹了druid配置數(shù)據(jù)庫連接使用密文密碼方式,具有很好的參考價值,希望對大家有所幫助,
    2023-12-12
  • 舉例講解Java設計模式中的對象池模式編程

    舉例講解Java設計模式中的對象池模式編程

    這篇文章主要介紹了Java設計模式中的對象池模式編程示例分享,對象池模式經(jīng)常在多線程開發(fā)時被用到,需要的朋友可以參考下
    2016-02-02
  • Spring boot使用spring retry重試機制的方法示例

    Spring boot使用spring retry重試機制的方法示例

    這篇文章主要介紹了Spring boot使用spring retry重試機制的方法示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-01-01
  • Java利用正則表達式提取數(shù)據(jù)的方法

    Java利用正則表達式提取數(shù)據(jù)的方法

    最近由于項目需求需要提取txt里的數(shù)據(jù),之前用C#實現(xiàn)過,由于最近學習了java,所以嘗試用java實現(xiàn)下,這篇文章主要介紹了Java利用正則表達式提取數(shù)據(jù)的方法,需要的朋友可以參考下,下面來一起看看吧。
    2016-12-12
  • Spring Security組件一鍵接入驗證碼登錄和小程序登錄的詳細過程

    Spring Security組件一鍵接入驗證碼登錄和小程序登錄的詳細過程

    這篇文章主要介紹了Spring Security 一鍵接入驗證碼登錄和小程序登錄,簡單介紹一下這個插件包的相關知識,本文結合示例代碼給大家介紹的非常詳細,需要的朋友參考下吧
    2022-04-04
  • 關于在Java中使用預定義類

    關于在Java中使用預定義類

    這篇文章主要介紹了關于在Java中使用預定義類,預定義類就是Java類庫(或第三方庫)中已經(jīng)定義好的類,例如,Math 類和 Date 類,需要的朋友可以參考下
    2023-05-05
  • spring注入配置文件屬性到java類

    spring注入配置文件屬性到java類

    這篇文章主要為大家介紹了spring注入配置文件屬性到java類實現(xiàn)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-07-07

最新評論