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

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

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

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

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

• 線性表中，我們把數(shù)據(jù)元素叫做元素，樹種將數(shù)據(jù)元素叫結(jié)點，在圖中的數(shù)據(jù)元素，我們則稱之為頂點。
• 線性表中沒有數(shù)據(jù)元素，稱為空表。樹種可以沒有結(jié)點，叫做空樹。但是在圖結(jié)構(gòu)中，不允許沒有頂點。在定義中，若V是頂點的集合，則強調(diào)了頂點集合V是有窮非空的。
• 線性表中，相鄰的數(shù)據(jù)元素之間具有線性關(guān)系，樹結(jié)構(gòu)中，相鄰兩層的結(jié)點具有層次關(guān)系，而圖中，任意兩個頂點之間都可能有關(guān)系，頂點之間的邏輯關(guān)系用邊來表示，邊集可以是空的。

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

其實分析這個問題就可以知道，這是對圖的深度優(yōu)先遍歷(Depth-First-Search 簡稱DFS)的一個應(yīng)用，若是我們能實現(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;    // 起始點
    bool* visited; // 記錄dfs的過程中節(jié)點是否被訪問
    int* from; // 記錄路徑，from[i]表示查找的路徑上i的上一個節(jié)點

    // 圖的深度優(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點到其他點的路徑
    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點到w點是否有路徑
    bool hasPath( int w ) {
        assert( w >= 0 && w < G.V() );
        return visited[w];
    }

    // 查詢s點到w點的路徑，存放在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點到w點的路徑
    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)記的起始點S。而通過showPath()函數(shù)我們能夠展示起始點S至任意點的路徑，測試代碼就如下所示:

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ù)的返回值變化了一點，代碼如下:

public class Path {

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

    /**
     * 構(gòu)造函數(shù)，尋路算法，尋找圖graph從點s到其他點的路徑
     * @param graph graph
     * @param s 尋路起始點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點開始深度優(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點到w點是否存在路徑
    public boolean hasPath(int w) {
        assert w >= 0 && w < G.V();
        return visited[w];
    }

    // 查詢點s到點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;
    }

    // 打印出從點s到點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)圖的路徑問題就講解到這里，之后的知識點等學(xué)習(xí)整理之后，再行記錄。