天天看點
傳回

【資料結構】圖的實作

文章目錄

    • 圖
      • 1.圖的基本概念
      • 2.圖的存儲結構
      • 3.鄰接矩陣
        • 3.1鄰接矩陣的優缺點
        • 3.2鄰接矩陣的實作
      • 4.鄰接表
        • 4.1鄰接表的實作
      • 5.圖的周遊
        • 5.1廣度優先周遊
        • 5.2深度優先周遊
        • 5.3如何周遊不連通的圖？

圖

1.圖的基本概念

圖是由頂點集合及頂點間的關系組成的一種資料結構：G = (V， E)，其中：

  • 頂點集合V = {x|x屬于某個資料對象集}是有窮非空集合；

  • E = {(x,y)|x,y屬于V}或者E = {<x, y>|x,y屬于V && Path(x, y)}是頂點間關系的有窮集合，也叫

    做邊的集合。

  • (x, y)表示x到y的一條雙向通路，即(x, y)是無方向的；Path(x, y)表示從x到y的一條單向通路，即Path(x, y)是有方向的。
圖相關的概念
  • 頂點和邊：圖中結點稱為頂點，第i個頂點記作vi。兩個頂點vi和vj相關聯稱作頂點vi和頂點vj之間有一條邊，圖中的第k條邊記作ek，ek = (vi，vj)或<vi，vj>。
  • 有向圖和無向圖：在有向圖中，頂點對<x, y>是有序的，頂點對<x，y>稱為頂點x到頂點y的一條邊(弧)，<x, y>和<y, x>是兩條不同的邊，比如下圖G3和G4為有向圖；在無向圖中，頂點對(x, y)是無序的，頂點對(x,y)稱為頂點x和頂點y相關聯的一條邊，這條邊沒有特定方向，(x, y)和(y，x)是同一條邊，比如下圖G1和G2為無向圖。注意：無向邊(x, y)等于有向邊<x, y>和<y, x>。
【資料結構】圖的實作
完全圖
  • 無向完全圖：即圖中每兩個頂點都有邊。在有n個頂點的無向圖中，若有n * (n-1)/2條邊，即任意兩個頂點之間有且僅有一條邊，則稱此圖為無向完全圖 。
  • 有向完全圖：在n個頂點的有向圖中，若有n * (n-1)條邊，即任意兩個頂點之間有且僅有方向相反的邊，則稱此圖為有向完全圖。
頂點的度
  • 頂點的度：頂點v的度是指與它相關聯的邊的條數，記作deg(v)。在有向圖中，頂點的度等于該頂點的入度與出度之和。在無向圖中頂點的度等于該頂點的入度和出度，即dev(v)=indev(v) = outdev(v)。
路徑
  • 路徑：在圖G = (V， E)中，若從頂點vi出發有一組邊使其可到達頂點vj，則稱頂點vi到頂點vj的頂點序列為從頂點vi到頂點vj的路徑
  • 路徑長度：對于不帶權的圖，一條路徑的路徑長度是指該路徑上的邊的條數；**對于帶權的圖，一條路徑的路徑長度是指該路徑上各個邊權值的總和。 **
【資料結構】圖的實作
子圖

子圖：設圖G = {V, E}和圖G1 = {V1，E1}，若V1屬于V且E1屬于E，則稱G1是G的子圖。

【資料結構】圖的實作

**連通圖：**在無向圖中，若從頂點v1到頂點v2有路徑，則稱頂點v1與頂點v2是連通的。如果圖中任

意一對頂點都是連通的，則稱此圖為連通圖。

**強連通圖：**在有向圖中，若在每一對頂點vi和vj之間都存在一條從vi到vj的路徑，也存在一條從vj

到vi的路徑，則稱此圖是強連通圖

生成樹：一個連通圖的最小連通子圖稱作該圖的生成樹。有n個頂點的連通圖的生成樹有n個頂點

和n-1條邊。

2.圖的存儲結構

圖的存儲方式主要有兩種，一種叫鄰接矩陣，一種叫做鄰接表。

3.鄰接矩陣

因為節點與節點之間的關系就是連通與否，即為0或者1，是以鄰接矩陣(二維數組)即是：先用一

個數組将定點儲存，然後采用矩陣來表示節點與節點之間的關系。

無向圖
【資料結構】圖的實作
有向圖
【資料結構】圖的實作

注意：

無向圖的鄰接矩陣是一個對稱圖；第i行(列)元素之和，就是頂點i的度。有向圖的鄰接矩陣則不一

定是對稱的，第i行(列)元素之後就是頂點i 的出(入)度。

帶權圖

對于有權值的圖：邊的關系就用權值代替，如果兩個頂點不通，則使用無窮大代替。

【資料結構】圖的實作

3.1鄰接矩陣的優缺點

優點：

  • 能夠快速知道兩個頂點是否連通。

缺點：

  • 頂點比較多，邊比較少時，矩陣中存儲了大量的0成為系數矩陣，比較浪費空間，并且要求兩個節點之間的路徑不是很好求。

3.2鄰接矩陣的實作

基本接口架構：包括構造函數，邊的添加函數，傳回下标等

namespace matrix
{
    template <class V, class W, W MAX_W = INT64_MAX, bool Direction = false>
    class Graph
    {
        struct edge
        {
            size_t _srci; //起點下标
            size_t _dsti; //指向下标
            W _w;         //權值
            edge(size_t srci, size_t dsti, W w) : _srci(srci), _dsti(dsti), _w(w)
            {
            }
            bool operator>(const edge &e) const
            {
                return _w > e._w;
            }
        };

        typedef Graph<V, W, MAX_W, Direction> self;

    public:
        Graph() = default;
        //構造函數
        Graph(const V *v, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                _vertexs.push_back(v[i]);
                _indexmap[v[i]] = i;
            }
            //為存儲邊的矩陣開辟空間
            _matrix.resize(n);
            for (size_t i = 0; i < _matrix.size(); i++)
            {
                _matrix[i].resize(n, MAX_W);
            }
        }
        
        //傳回頂點的下标
        size_t GetVertexIndex(const V &v);
        
        //邊的添加函數
        void addedge(const V &src, const V &dst, const W &w);
        
        
        //列印鄰接矩陣函數
        void Print();
     private:
        unordered_map<V, int> _indexmap; //記錄頂點和下标的映射關系
        vector<V> _vertexs;              // 頂點集合的集合
        vector<vector<W>> _matrix;       // 存儲邊集合的矩陣
    };
}
傳回頂點的下标

頂點和頂點下标的映射關系，由一個Hash表存儲。可以直接通路Hash表得到頂點的下标

//擷取頂點的下标API
size_t GetVertexIndex(const V &v)
{
    auto it = _indexmap.find(v);
    if (it != _indexmap.end())
    {
        return _indexmap[v];
    }
    else
    {
        std::cout << "不存在這樣的節點" << std::endl;
        return -1;
    }
}
添加邊API

添加邊時，需要判斷圖是否為有向圖。如果是一個無向圖，那麼天需要添加兩次。

void _addedge(size_t srci, size_t dsti, const W &w)
{
    _matrix[srci][dsti] = w;
    if (Direction == false)
    {
        _matrix[dsti][srci] = w;
    }
}
void addedge(const V &src, const V &dst, const W &w)
{
    size_t srci = GetVertexIndex(src);
    size_t dsti = GetVertexIndex(dst);
    assert(srci != -1);
    assert(dsti != -1);
    _addedge(srci, dsti, w);
}
列印臨界矩陣

如果兩個頂點直接沒有邊，就使用*表示

void Print()
{
    //先列印頂點
    for (int i = 0; i < _vertexs.size(); i++)
    {
        cout << "[" << i << "]"
             << "->" << _vertexs[i]<<endl;
    }
    cout << endl;
    // 橫下标
    cout << "  ";
    for (size_t i = 0; i < _vertexs.size(); ++i)
    {
        // cout << i << " ";
        printf("%4d", i);
    }
    cout << endl;
    for (size_t i = 0; i < _matrix.size(); ++i)
    {
        cout << i << " "; // 豎下标
        for (size_t j = 0; j < _matrix[i].size(); ++j)
        {
            // cout << _matrix[i][j] << " ";
            if (_matrix[i][j] == MAX_W)
            {
                // cout << "* ";
                printf("%4c", '*');
            }
            else
            {
                // cout << _matrix[i][j] << " ";
                printf("%4d", _matrix[i][j]);
            }
        }
        cout << endl;
    }
    cout << endl;
}
接口測試結果 
void test_matrix(){
    matrix::Graph<char, int, INT64_MAX, true> g("0123", 4);
    g.addedge('0', '1', 1);
    g.addedge('0', '3', 4);
    g.addedge('1', '3', 2);
    g.addedge('1', '2', 9);
    g.addedge('2', '3', 8);
    g.addedge('2', '1', 5);
    g.addedge('2', '0', 3);
    g.addedge('3', '2', 6);
    g.Print();
}
int main()
{
    test_matrix();
    return 0;
}
【資料結構】圖的實作

4.鄰接表

鄰接表：使用數組表示頂點的集合，使用連結清單表示邊的關系。

無向圖鄰接表
【資料結構】圖的實作

**注意：**無向圖中同一條邊在鄰接表中出現了兩次。如果想知道頂點vi的度，隻需要知道頂點vi邊連結清單集合中結點的數目即可。

有向圖鄰接表
【資料結構】圖的實作

**注意：**有向圖中每條邊在鄰接表中隻出現一次，與頂點vi對應的鄰接表所含結點的個數，就是該頂點的出度，也稱出度表，要得到vi頂點的入度，必須檢測其他所有頂點對應的邊連結清單，看有多少邊頂點的dst取值是i。

4.1鄰接表的實作

基本接口架構：包括構造函數，邊的添加函數，傳回下标等；

namespace link_table
{

    template <class V, class W, W MAX_W = INT64_MAX, bool Direction = false>
    class Graph
    {
        typedef Graph<V, W, MAX_W, Direction> self;
        struct edge
        {
            //由于是連結清單，起點就是目前點，是以一般都省略
            // int _srci;
            size_t _dsti; //目标點
            W _w;        //權值

            //用一個連結清單将于該頂點相連的頂點連接配接起來
            edge *_next;
            edge(size_t dsti, const W& w)
                : _dsti(dsti), _w(w), _next(nullptr)
            {
            }
        };

    public:
        //構造函數
        Graph() = default;
        Graph(const V *a, size_t n)
        {
            _vertexs.reserve(n);
            //添加頂點
            for (size_t i = 0; i < n; i++)
            {
                _vertexs.push_back(a[i]);
                _indexmap[a[i]] = i;
            }
            _tables.resize(n, nullptr);
        }

        //擷取頂點的下标
        size_t GetVertexIndex(const V &v);

        //添加邊的API
        void addedge(const V &src, const V &dst, const W &w);
        
	   //列印接口API
        void Print();

    private:
        unordered_map<V, int> _indexmap; //記錄頂點和下标的映射關系
        vector<V> _vertexs;              // 頂點集合的集合
        vector<edge *> _tables;          //鄰接表
    };
};
擷取頂點的下标

頂點和頂點下标的映射關系，由一個Hash表存儲。可以直接通路Hash表得到頂點的下标。

//擷取頂點的下标
size_t GetVertexIndex(const V &v)
{
    auto it = _indexmap.find(v);
    if (it != _indexmap.end())
    {
        return _indexmap[v];
    }
    else
    {
        std::cout << "不存在這樣的節點" << std::endl;
        return -1;
    }
}
添加邊 
//添加邊
void addedge(const V &src, const V &dst, const W &w)
{
    size_t srci = GetVertexIndex(src);
    size_t dsti = GetVertexIndex(dst);
    //頭插的方式
    edge *head = _tables[srci];
    edge *eg = new edge(dsti, w);
    eg->_next = head;
    _tables[srci] = eg;
    //如果是無向圖
    if (Direction == false)
    {
        edge *eg = new edge(srci, w);
        eg->_next = _tables[dsti];
        _tables[dsti] = eg;
    }
}
列印鄰接表 
void Print()
{
    //列印頂點
    for (size_t i = 0; i < _vertexs.size(); i++)
    {
        cout << "[" << i << "]"
             << "->" << _vertexs[i] << endl;
    }

    //列印邊
    for (size_t i = 0; i < _tables.size(); i++)
    {
        cout << _vertexs[i] << "[ " << i << "]->";
        edge *cur = _tables[i];
        while (cur)
        {
            cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
            cur = cur->_next;
        }
        cout << "nullptr" << endl;
    }
}
測試鄰接表的實作 
void test_table()
{
    string a[] = {"張三", "李四", "王五", "趙六"};
    link_table::Graph<string, int> g1(a, 4);
    g1.addedge("張三", "李四", 100);
    g1.addedge("張三", "王五", 200);
    g1.addedge("王五", "趙六", 30);
    g1.Print();
}
int main()
{
    test_table();
    return 0;
}
【資料結構】圖的實作

5.圖的周遊

圖的周遊有兩種方式，一種是廣度優先周遊(BFS),另一種是深度優先周遊(DFS)。下面以鄰接矩陣為例，實作圖的廣度優先周遊和深度優先周遊。

5.1廣度優先周遊

比如現在你需要找你的鑰匙，有三個抽屜，東西在哪個抽屜不清楚，現在要将其找到，廣度優先周遊的做法是：

  • 先将三個抽屜打開，在三個抽屜的最外層找一遍
  • 依次打開三個抽屜的第二層，再找一遍。
  • 如果沒有找到，依次打開第三個抽屜的第三層，再找一邊…
  • 重複上面的操作，直到找到鑰匙…
【資料結構】圖的實作
鄰接矩陣的廣度優先周遊實作

思路：像樹的層序周遊一樣，借助一個隊列實作廣度周遊。

【資料結構】圖的實作

但是可能會出現重複周遊的問題，造成死循環。

解決辦法：使用一個标記數組，記錄頂點是否已經被周遊。如果頂點已經被周遊，則不再入隊列。
【資料結構】圖的實作
void BFS(const V &src)
{
    size_t srci = GetVertexIndex(src);
    //周遊隊列
    queue<int> q;
    //标記數組
    vector<bool> visited(_vertexs.size(), false);
    q.push(srci);
    visited[srci] = true;
    int n = _vertexs.size();
    int num = 0;
    int size = 1;
    while (!q.empty())
    {
        cout << "第" << num << "層：" << endl;
        for (int i = 0; i < size; i++)
        {
            int front = q.front();
            q.pop();
            cout << front << ":" << _vertexs[front] << " ";
            for (int i = 0; i < n; i++)
            {
                if (_matrix[front][i] != MAX_W && !visited[i])
                {
                    q.push(i);
                    visited[i] = true;
                }
            }
            cout << endl;
        }
        num++;
        size = q.size();
    }
    cout << endl;
}
測試程式 
void test_matrix()
{
    matrix::Graph<char, int, INT64_MAX, false> g("ABCDEFGHI", 9);
    g.addedge('A','B',1);
    g.addedge('A','C',1);
    g.addedge('A','D',1);
    g.addedge('B','E',1);
    g.addedge('B','C',1);
    g.addedge('C','F',1);
    g.addedge('D','F',1);
    g.addedge('E','G',1);
    g.addedge('F','H',1);
    g.addedge('H','I',1);
    g.Print();
    g.BFS('A');
}
【資料結構】圖的實作
美團的面試題：六度人脈理論
【資料結構】圖的實作

這個題的思路需要用到廣度優先周遊，每一層就是小點的一度人脈。

void test_matrix()
{
    string name[]={"小美","小團","小卓","小越","小誠","小信"};
    matrix::Graph<string, int> g(name, 6);
    g.addedge("小美","小團",1);
    g.addedge("小美","小卓",1);
    g.addedge("小美","小誠",1);
    g.addedge("小團","小誠",1);
    g.addedge("小卓","小越",1);
    g.addedge("小卓","小信",1);
    g.addedge("小信","小越",1);
    g.BFS("小美");
}
【資料結構】圖的實作

5.2深度優先周遊

【資料結構】圖的實作

深度優先周遊的周遊順序與頂點插入順序有關，不同的插入順序可能有不同的周遊結果。

【資料結構】圖的實作
void _DFS(size_t srci, vector<bool> &visited)
{
    cout << srci << ":" << _vertexs[srci] << " ";
    visited[srci] = true;
    for (int i = 0; i < _vertexs.size(); i++)
    {
        if (_matrix[srci][i] != MAX_W && !visited[i])
        {
            _DFS(i, visited);
        }
    }
}
void DFS(const V &src)
{
    size_t srci = GetVertexIndex(src);
    vector<bool> visited(_vertexs.size(), false);
    _DFS(srci, visited);
    cout << endl;
}
測試結果 
void test_matrix()
{
    matrix::Graph<char, int, INT64_MAX, false> g("ABCDEFGHI", 9);
    g.addedge('A','B',1);
    g.addedge('A','C',1);
    g.addedge('A','D',1);
    g.addedge('B','E',1);
    g.addedge('B','C',1);
    g.addedge('C','F',1);
    g.addedge('D','F',1);
    g.addedge('E','G',1);
    g.addedge('F','H',1);
    g.addedge('H','I',1);
    g.Print();
    g.DFS('A');
}
【資料結構】圖的實作

5.3如何周遊不連通的圖？

【資料結構】圖的實作

比如上面的圖：

在進行圖的周遊的時候，我們使用了一個周遊數組記錄該頂點是否被周遊。

如何周遊不連通的圖：在bool數組中尋找還沒有周遊過的點進行周遊。

以上面的圖為例：

void test_matrix()
{

    matrix::Graph<char, int> g("ABCDEFGHI",9);
    g.addedge('A','B',1);
    g.addedge('A','D',1);
    g.addedge('B','E',1);
    g.addedge('E','G',1);
    g.addedge('C','F',1);
    g.addedge('F','H',1);
    g.addedge('H','I',1);
    g.BFS('A');
}
廣度優先周遊 
void _BFS(size_t srci, vector<bool> &visited)
{
    //周遊隊列
    queue<int> q;
    q.push(srci);
    visited[srci] = true;
    int n = _vertexs.size();
    int num = 0;
    int size = 1;
    while (!q.empty())
    {
        cout << "第" << num << "層：" << endl;
        for (int i = 0; i < size; i++)
        {
            int front = q.front();
            q.pop();
            cout << front << ":" << _vertexs[front] << " ";
            for (int i = 0; i < n; i++)
            {
                if (_matrix[front][i] != MAX_W && !visited[i])
                {
                    q.push(i);
                    visited[i] = true;
                }
            }
            cout << endl;
        }
        num++;
        size = q.size();
    }
    cout << endl;
}

void BFS(const V &src)
{

    //标記數組
    vector<bool> visited(_vertexs.size(), false);
    size_t srci = GetVertexIndex(src);
    _BFS(srci, visited);
    for (int i = 0; i < visited.size(); i++)
    {
        if (!visited[i])
        {
            cout << endl;
            _BFS(i, visited);
        }
    }
}
【資料結構】圖的實作
深度優先周遊 
void _DFS(size_t srci, vector<bool> &visited)
{
    cout << srci << ":" << _vertexs[srci] << " ";
    visited[srci] = true;
    for (int i = 0; i < _vertexs.size(); i++)
    {
        if (_matrix[srci][i] != MAX_W && !visited[i])
        {
            _DFS(i, visited);
        }
    }
}
//非連通圖的周遊
void DFS(const V &src)
{
    size_t srci = GetVertexIndex(src);
    vector<bool> visited(_vertexs.size(), false);
    _DFS(srci, visited);
    for (int i = 0; i < visited.size(); i++)
    {
        if (!visited[i])
        {
            cout << endl;
            _DFS(i, visited);
        }
    }
    cout << endl;
}
【資料結構】圖的實作
資料結構筆記 資料結構 圖論 算法
上一篇: 實驗二：程序的建立與可執行程式的加載
下一篇: 第六周 JDBK使用及基本封裝JDBC技術day4 - idea使用 &amp; JDBC(四)

繼續閱讀