好像又是接近半個(gè)月沒有更新，這半個(gè)月忙著結(jié)婚的各項(xiàng)事情搜贤，本來預(yù)計(jì)的學(xué)習(xí)任務(wù)也拖拖拉拉谆沃，進(jìn)度緩慢。吐槽一句仪芒，拍婚紗照真的是最非常非常累的一件事情唁影，不想再有下次了耕陷。

好吧，言歸正傳据沈，今天就在這周緩慢的學(xué)習(xí)進(jìn)度中哟沫，抽取出來一個(gè)比較有代表性的知識點(diǎn)，記錄一下吧卓舵。

首先南用，首次接觸圖這個(gè)類型的數(shù)據(jù)結(jié)構(gòu)，我們先來看一下圖的定義掏湾，了解一下到底什么是圖裹虫。

圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間的邊的集合組成，通常表示為:G(V,E), 其中G表示一個(gè)圖融击，V是圖G中頂點(diǎn)的集合筑公，E是圖G中邊的集合。

接下來我們把圖的定義與線性表定義的進(jìn)行一下對比尊浪，讓我們來更好的體會(huì)一下圖的各種定義與其他數(shù)據(jù)結(jié)構(gòu)的差異:

• 線性表中匣屡，我們把數(shù)據(jù)元素叫做元素，樹種將數(shù)據(jù)元素叫結(jié)點(diǎn)拇涤，在圖中的數(shù)據(jù)元素捣作，我們則稱之為頂點(diǎn)。
• 線性表中沒有數(shù)據(jù)元素鹅士，稱為空表券躁。樹種可以沒有結(jié)點(diǎn)，叫做空樹掉盅。但是在圖結(jié)構(gòu)中也拜，不允許沒有頂點(diǎn)。在定義中趾痘，若V是頂點(diǎn)的集合慢哈，則強(qiáng)調(diào)了頂點(diǎn)集合V是有窮非空的。
• 線性表中永票，相鄰的數(shù)據(jù)元素之間具有線性關(guān)系卵贱，樹結(jié)構(gòu)中，相鄰兩層的結(jié)點(diǎn)具有層次關(guān)系瓦侮，而圖中艰赞，任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系，頂點(diǎn)之間的邏輯關(guān)系用邊來表示肚吏，邊集可以是空的方妖。

圖的定義我們就暫時(shí)講到這里，更細(xì)致的定義希望大家自己在網(wǎng)絡(luò)或者書籍中獲取資料罚攀，畢竟我寫的再多党觅，也不如教科書詳盡雌澄，今天我們就來講一個(gè)圖的應(yīng)用，關(guān)于路徑查找的問題杯瞻。在這里我想先說明镐牺，我們的路徑查找是一種針對無向圖的路徑查找，比如給出起始點(diǎn)A魁莉，查詢頂點(diǎn)A至頂點(diǎn)B是否有路徑睬涧，若是有路徑，則打印出A至B的路徑旗唁。而這個(gè)路徑畦浓，我們尋找的不一定是最短路徑。

其實(shí)分析這個(gè)問題就可以知道检疫，這是對圖的深度優(yōu)先遍歷(Depth-First-Search 簡稱DFS)的一個(gè)應(yīng)用讶请，若是我們能實(shí)現(xiàn)了圖的深度優(yōu)先遍歷，那么查找路徑的問題也就迎刃而解屎媳。

接下來就先給出C++的代碼夺溢，來展示解決查詢路徑問題的思路：

#include <iostream>
#include <vector>
#include <stack>
#include <cassert>

using namespace std;

// 路徑查詢
template<typename Graph>
class Path {

private:
    Graph &G; // 圖的引用
    int s;    // 起始點(diǎn)
    bool* visited; // 記錄dfs的過程中節(jié)點(diǎn)是否被訪問
    int* from; // 記錄路徑，from[i]表示查找的路徑上i的上一個(gè)節(jié)點(diǎn)

    // 圖的深度優(yōu)先遍歷
    void dfs( int v ) {
        visited[v] = true;

        typename Graph::adjIterator adj(G, v);
        for (int i = adj.begin(); !adj.end(); i = adj.next()) {
            if (!visited[i]) {
                from[i] = v;
                dfs(i);
            }
        }
    } 

public:
    // 構(gòu)造函數(shù)烛谊、尋路算法风响、尋找圖graph從s點(diǎn)到其他點(diǎn)的路徑
    Path(Graph &graph, int s): G(graph) {

        // 算法初始化
        assert( s >= 0 && s < G.V() );

        visited = new bool[G.V()];
        from = new int[G.V()];

        for (int i = 0; i < G.V(); i++) {
            visited[i] = false;
            from[i] = -1;
        }

        this->s = s;

        // 尋路算法
        dfs(s);
    }

    // 析構(gòu)函數(shù)
    ~Path() {
        delete[] visited;
        delete[] from;
    }

    // 查詢從s點(diǎn)到w點(diǎn)是否有路徑
    bool hasPath( int w ) {
        assert( w >= 0 && w < G.V() );
        return visited[w];
    }

    // 查詢s點(diǎn)到w點(diǎn)的路徑，存放在vec中
    void path( int w, vector<int> &vec ) {
        assert( hasPath(w) );

        stack<int> stack;
        // 通過from數(shù)組逆向查找到從s到w的路徑丹禀，存放在棧中
        int p = w;
        while (p != -1) {
            stack.push(p);
            p = from[p];
        }

        // 從棧中依次取出元素钞诡，獲得順序從s到w的路徑
        vec.clear();
        while ( !stack.empty() ) {
            vec.push_back( stack.top() );
            stack.pop();
        }
    }

    // 打印從s點(diǎn)到w點(diǎn)的路徑
    void showPath( int w ) { 
        assert( hasPath(w) );

        vector<int> vec;
        path(w, vec);
        for (int i = 0; i < vec.size(); i++) {
            cout << vec[i];
            if (i == vec.size() - 1)
                cout << endl;
            else
                cout << " -> ";
        }
    }
};

?
通過上面的代碼可以得知，我們首先在構(gòu)造函數(shù)中傳入我們的圖數(shù)據(jù)結(jié)構(gòu)graph湃崩，以及?我們標(biāo)記的起始點(diǎn)S。而通過showPath()函數(shù)我們能夠展示起始點(diǎn)S至任意點(diǎn)的路徑接箫，測試代碼就如下所示:

int main() {
    string filename = "testG2.txt";
    SparseGraph g = SparseGraph(7, false);
    ReadGraph<SparseGraph> readGraph(g, filename);
    g.show();
    cout << endl;

    // 比較使用深度優(yōu)先遍歷和廣度優(yōu)先遍歷獲得路徑的不同
    // 廣度優(yōu)先遍歷獲得的是無權(quán)圖的最短路徑
    Path<SparseGraph> dfs(g, 0);
    cout << "DFS : " << endl;
    dfs.showPath(6);

    ShortestPath<SparseGraph> bfs(g, 0);
    cout << "BFS : ";
    bfs.showPath(6);    
    
    return 0;
}

而Java版本的代碼也是類似攒读，只是某些函數(shù)的返回值變化了一點(diǎn)，代碼如下:

public class Path {

    private Graph G;  // 圖的引用
    private int s;  // 起始點(diǎn)
    private boolean[] visited;  // 記錄dfs的過程中節(jié)點(diǎn)是否被訪問
    private int[] from;  // 記錄路徑辛友，from[i]表示查找的路徑上i的上一個(gè)節(jié)點(diǎn)

    /**
     * 構(gòu)造函數(shù)薄扁，尋路算法，尋找圖graph從點(diǎn)s到其他點(diǎn)的路徑
     * @param graph graph
     * @param s 尋路起始點(diǎn)s
     */
    public Path(Graph graph, int s) {
        assert s >= 0 && s < graph.V();

        this.G = graph;
        this.s = s;

        visited = new boolean[G.V()];
        from = new int[G.V()];

        for (int i = 0; i < G.V(); i++) {
            visited[i] = false;
            from[i] = -1;
        }

        dfs(s);
    }

    /**
     * 深度優(yōu)先遍歷
     * @param v 從v點(diǎn)開始深度優(yōu)先遍歷
     */
    private void dfs(int v) {
        visited[v] = true;

        for (int i: G.adj(v)) {
            if (!visited[i]) {
                from[i] = v;
                dfs(i);
            }
        }
    }

    // 查詢從s點(diǎn)到w點(diǎn)是否存在路徑
    public boolean hasPath(int w) {
        assert w >= 0 && w < G.V();
        return visited[w];
    }

    // 查詢點(diǎn)s到點(diǎn)w的路徑废累，存放在vec中
    public Vector<Integer> path(int w) {
        assert(hasPath(w));

        Stack<Integer> stack = new Stack<Integer>();
        int p = w;
        while (p != -1) {
            stack.push(p);
            p = from[p];
        }

        Vector<Integer> vec = new Vector<Integer>();
        while (!stack.isEmpty()) {
            vec.add(stack.pop());
        }

        return vec;
    }

    // 打印出從點(diǎn)s到點(diǎn)w的路徑
    public void showPath(int w) {
        assert (hasPath(w));

        Vector<Integer> vec = path(w);
        for (int i = 0; i < vec.size(); i++) {
            System.out.print(vec.elementAt(i));
            if (i == vec.size() - 1) {
                System.out.println();
            } else {
                System.out.print(" -> ");
            }
        }
    }
}

今天的無權(quán)圖的路徑問題就講解到這里邓梅，之后的知識點(diǎn)等學(xué)習(xí)整理之后，再行記錄邑滨。