圖的存儲之鄰接表-創(chuàng)新互聯(lián)

1、稀疏矩陣

10年積累的做網(wǎng)站、成都網(wǎng)站建設經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先網(wǎng)站制作后付款的網(wǎng)站建設流程，更有羅定免費網(wǎng)站建設讓你可以放心的選擇與我們合作。

 有一個稀疏因子，這是節(jié)省空間的一種存儲方式。

2、鄰接表

 以鄰接矩陣存儲圖結(jié)構(gòu)的話，當實際邊數(shù)遠遠小于圖的大邊數(shù)時，將會存儲很多0，勢必造成存儲空間的巨大浪費；這時，就必須將鄰接矩陣該用為鄰接表；將鄰接矩陣各行組織為一個單鏈表，類哈希的存儲結(jié)構(gòu)。

存儲結(jié)構(gòu)(控制頭)：

int maxVertices;  //大頂點數(shù)
int curVertices;  //當前頂點數(shù)
int curEdges;  //當前邊數(shù)

template<typename Type>
class Edge{  //邊的存儲結(jié)構(gòu)
public:
    Edge(int num) : dest(num), link(NULL){}
public:
    int dest;  //是另一個頂點的下標
    Edge *link;
};
template<typename Type>
class Vertex{  //頂點的存儲結(jié)構(gòu)
public:
    Type data;  //存放的頂點
    Edge<Type> *adj;
};

Vertex<Type> *vertexTable;  //指向頂點的指針，是申請數(shù)組用的

存儲模型：

圖的存儲之鄰接表

3、核心方法

 均由C++實現(xiàn)，無向圖的鄰接表；

 (1)、刪除邊(是鏈表的刪除操作，相對簡單)：

bool removeEdge(const Type &v1, const Type &v2){  //刪除邊
    int i = getVertexIndex(v1);
    int j = getVertexIndex(v2);


    if(i==-1 || j==-1){  //保證頂點的保存在
        return false;
    }
    //v1-->v2
    Edge<Type> *p = vertexTable[i].adj;
    if(p == NULL){  //判斷有沒有邊
        return false;
    }

    if(p->link == NULL && p->dest == j){ //刪除的是第一個邊，其后沒有邊了；
        vertexTable[i].adj = NULL;
        delete p;    
    }else if(p->dest == j){  //刪除的是第一個邊,并且其后還有邊
        vertexTable[i].adj = p->link;
        delete p;
    }else{
        while(p->link != NULL){
            if(p->link->dest == j){
                Edge<Type> *q = p->link;
                p->link = q->link;
                delete q;
            }
            p = p->link;
        }
    }
    //v2-->v1
    Edge<Type> *s = vertexTable[j].adj;
    if(s == NULL){  //判斷有沒有邊
        return false;
    }

    if(s->link == NULL && s->dest == i){ //刪除的是第一個邊，其后沒有邊了；
        vertexTable[j].adj = NULL;
        delete s;
        curEdges--;
        return false;
    }else if(s->dest == i){  //刪除的是第一個邊,并且其后還有邊
        vertexTable[j].adj = s->link;
        delete s;
        curEdges--;
        return true;
    }else{
        while(s->link != NULL){
            if(s->link->dest == i){
                Edge<Type> *q = s->link;
                s->link = q->link;
                delete q;
                curEdges--;
                return true;
            }
            s = s->link;
        }
    }

    return true;
}

 (2)、刪除頂點：

這個算法相對復雜，但是思路比較清晰：

 i>、首先找到要刪除的頂點，將其后上的邊所對應的邊和這個邊都得刪除；

 ii>、將最后一個頂點的data和adj都覆蓋到這個地方；

 iii>、找到其后邊上的dest,更改為當下位置的下標；

大致模型如下：

圖的存儲之鄰接表

bool removeVertex(const Type &v){  //刪除頂點
    int i = getVertexIndex(v);
    if(i == -1){
        return false;
    }

    Edge<Type> *p = vertexTable[i].adj;  //先刪除邊上的dest和此邊
    while(p != NULL){
        vertexTable[i].adj = p->link;
        int k = p->dest;
        Edge<Type> *q = vertexTable[k].adj;
        if(q->dest == i){
            vertexTable[k].adj = q->link;
            delete q;
        }else{
            while(q->link != NULL && q->link->dest != i){
                q = q->link;
            }
            Edge<Type> *t = q->link;
            q->link = t->link;
            delete t;
        }
        delete p;
        p = vertexTable[i].adj;
        curEdges--;
    }

    curVertices--;  //下面實行覆蓋，指針和最后的那個頂點的adj相等;
    vertexTable[i].data = vertexTable[curVertices].data;
    vertexTable[i].adj = vertexTable[curVertices].adj;
    vertexTable[curVertices].adj = NULL;

    int k = curVertices;
    p = vertexTable[i].adj;
    while(p != NULL){  //修改其它頂點的dest.
        Edge<Type> *s = vertexTable[p->dest].adj;
        while(s != NULL){
            if(s->dest == k){
                s->dest = i;
                break;
            }
            s = s->link;
        }
        p = p->link;
    }
    return true;
}

4、鄰接表完整代碼、測試代碼、測試結(jié)果

 (1)完整代碼(用的是繼承，方便寫其它的存儲結(jié)構(gòu)代碼)：

#ifndef _GRAPH_H_
#define _GRAPH_H_

#include<iostream>
using namespace std;

#define VERTEX_DEFAULT_SIZE        10

template<typename Type>    
class Graph{
public:
    bool isEmpty()const{
        return curVertices == 0;
    }
    bool isFull()const{
        if(curVertices >= maxVertices || curEdges >= curVertices*(curVertices-1)/2)
            return true;  //圖滿有2種情況：(1)、當前頂點數(shù)超過了大頂點數(shù)，存放頂點的空間已滿
        return false;     //(2)、當前頂點數(shù)并沒有滿，但是當前頂點所能達到的邊數(shù)已滿
    }
    int getCurVertex()const{
        return curVertices;
    }
    int getCurEdge()const{
        return curEdges;
    }
public:
    virtual bool insertVertex(const Type &v) = 0;  //插入頂點
    virtual bool insertEdge(const Type &v1, const Type &v2) = 0; //插入邊
    virtual bool removeVertex(const Type &v) = 0;  //刪除頂點
    virtual bool removeEdge(const Type &v1, const Type &v2) = 0; //刪除邊
    virtual int getFirstNeighbor(const Type &v) = 0; //得到第一個相鄰頂點
    virtual int getNextNeighbor(const Type &v, const Type &w) = 0; //得到下一個相鄰頂點
public:
    virtual int getVertexIndex(const Type &v)const = 0; //得到頂點下標
    virtual void showGraph()const = 0;  //顯示圖
protected:
    int maxVertices;  //大頂點數(shù)
    int curVertices;  //當前頂點數(shù)
    int curEdges;  //當前邊數(shù)
};

template<typename Type>
class Edge{  //邊的存儲結(jié)構(gòu)
public:
    Edge(int num) : dest(num), link(NULL){}
public:
    int dest;
    Edge *link;
};
template<typename Type>
class Vertex{  //頂點的存儲結(jié)構(gòu)
public:
    Type data;
    Edge<Type> *adj;
};
template<typename Type>
class GraphLnk : public Graph<Type>{
#define maxVertices  Graph<Type>::maxVertices  //因為是模板，所以用父類的數(shù)據(jù)或方法都得加上作用域限定符
#define curVertices  Graph<Type>::curVertices
#define curEdges     Graph<Type>::curEdges
public:
    GraphLnk(int sz = VERTEX_DEFAULT_SIZE){
        maxVertices = sz > VERTEX_DEFAULT_SIZE ? sz : VERTEX_DEFAULT_SIZE;
        vertexTable = new Vertex<Type>[maxVertices];
        for(int i = 0; i < maxVertices; i++){
            vertexTable[i].data = 0;
            vertexTable[i].adj = NULL;
        }

        curVertices = curEdges = 0;
    }
public:
    bool insertVertex(const Type &v){
        if(curVertices >= maxVertices){
            return false;
        }
        vertexTable[curVertices++].data = v;
        return true;
    }
    bool insertEdge(const Type &v1, const Type &v2){
        int v = getVertexIndex(v1);
        int w = getVertexIndex(v2);

        if(v==-1 || w==-1){
            return false;
        }

        Edge<Type> *p = vertexTable[v].adj;
        while(p != NULL){  //這里主要判斷邊是否已經(jīng)存在
            if(p->dest == w){   //無向圖，判斷一邊即可;
                return false;
            }
            p = p->link;
        }
        //v1-->v2  //采用頭插
        Edge<Type> *s = new Edge<Type>(w);
        s->link = vertexTable[v].adj;
        vertexTable[v].adj = s;

        //v2-->v1  //采用頭插
        Edge<Type> *q = new Edge<Type>(v);
        q->link = vertexTable[w].adj;
        vertexTable[w].adj = q;
        
        curEdges++;
        return true;
    }
    bool removeVertex(const Type &v){
        int i = getVertexIndex(v);
        if(i == -1){
            return false;
        }

        Edge<Type> *p = vertexTable[i].adj;
        while(p != NULL){
            vertexTable[i].adj = p->link;
            int k = p->dest;
            Edge<Type> *q = vertexTable[k].adj;
            if(q->dest == i){
                vertexTable[k].adj = q->link;
                delete q;
            }else{
                while(q->link != NULL && q->link->dest != i){
                    q = q->link;
                }
                Edge<Type> *t = q->link;
                q->link = t->link;
                delete t;
            }
            delete p;
            p = vertexTable[i].adj;
            curEdges--;
        }

        curVertices--;  //下面實行覆蓋
        vertexTable[i].data = vertexTable[curVertices].data;
        vertexTable[i].adj = vertexTable[curVertices].adj;
        vertexTable[curVertices].adj = NULL;

        int k = curVertices;
        p = vertexTable[i].adj;
        while(p != NULL){
            Edge<Type> *s = vertexTable[p->dest].adj;
            while(s != NULL){
                if(s->dest == k){
                    s->dest = i;
                    break;
                }
                s = s->link;
            }
            p = p->link;
        }
        return true;
    }
    bool removeEdge(const Type &v1, const Type &v2){
        int i = getVertexIndex(v1);
        int j = getVertexIndex(v2);


        if(i==-1 || j==-1){  //保證頂點的保存在
            return false;
        }
        //v1-->v2
        Edge<Type> *p = vertexTable[i].adj;
        if(p == NULL){  //判斷有沒有邊
            return false;
        }

        if(p->link == NULL && p->dest == j){ //刪除的是第一個邊，其后沒有邊了；
            vertexTable[i].adj = NULL;
            delete p;    
        }else if(p->dest == j){  //刪除的是第一個邊,并且其后還有邊
            vertexTable[i].adj = p->link;
            delete p;
        }else{
            while(p->link != NULL){
                if(p->link->dest == j){
                    Edge<Type> *q = p->link;
                    p->link = q->link;
                    delete q;
                }
                p = p->link;
            }
        }
        //v2-->v1
        Edge<Type> *s = vertexTable[j].adj;
        if(s == NULL){  //判斷有沒有邊
            return false;
        }

        if(s->link == NULL && s->dest == i){ //刪除的是第一個邊，其后沒有邊了；
            vertexTable[j].adj = NULL;
            delete s;
            curEdges--;
            return false;
        }else if(s->dest == i){  //刪除的是第一個邊,并且其后還有邊
            vertexTable[j].adj = s->link;
            delete s;
            curEdges--;
            return true;
        }else{
            while(s->link != NULL){
                if(s->link->dest == i){
                    Edge<Type> *q = s->link;
                    s->link = q->link;
                    delete q;
                    curEdges--;
                    return true;
                }
                s = s->link;
            }
        }

        return true;
    }
    int getFirstNeighbor(const Type &v){
        int i = getVertexIndex(v);
        if(i != -1){
            Edge<Type> *p = vertexTable[i].adj;
            if(p != NULL){
                return p->dest;
            }
        }

        return -1;
    }
    int getNextNeighbor(const Type &v, const Type &w){
        int i = getVertexIndex(v);
        int j = getVertexIndex(w);

        if(i==-1 || j==-1){
            return -1;
        }
        Edge<Type> *p = vertexTable[i].adj;
        while(p != NULL){
            if(p->dest == j && p->link != NULL){
                return p->link->dest;
            }
            p = p->link;
        }

        return -1;
    }
public:
    int getVertexIndex(const Type &v)const{
        for(int i = 0; i < curVertices; i++){
            if(vertexTable[i].data == v){
                return i;
            }
        }

        return -1;
    }
    void showGraph()const{
        for(int i = 0; i < curVertices; i++){
            cout<<vertexTable[i].data<<":-->";
            Edge<Type> *p = vertexTable[i].adj;
            while(p != NULL){
                cout<<p->dest<<"-->";
                p = p->link;
            }
            cout<<"Nul. "<<endl;
        }    
    }
private:
    Vertex<Type> *vertexTable;  //指向頂點的指針，是申請數(shù)組用的
};

#endif

 (2)、測試代碼：

#include"Graph.h"

int main(void){
    GraphLnk<char> gl;
    gl.insertVertex('A');
    gl.insertVertex('B');
    gl.insertVertex('C');
    gl.insertVertex('D');
    gl.insertEdge('A','B');
    gl.insertEdge('A','D');
    gl.insertEdge('B','C');
    gl.insertEdge('C','D');
    gl.showGraph();

    cout<<gl.getFirstNeighbor('A')<<endl;
    cout<<gl.getNextNeighbor('A','B')<<endl;
    gl.removeEdge('B','C');
    cout<<"---------------------"<<endl;
    gl.removeVertex('B');
    gl.showGraph();

    return 0;
}

 (3)、測試結(jié)果：

測試的圖：

圖的存儲之鄰接表

圖的存儲之鄰接表

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

文章標題：圖的存儲之鄰接表-創(chuàng)新互聯(lián)
網(wǎng)頁URL：http://bm7419.com/article40/dgdieo.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、全網(wǎng)營銷推廣、移動網(wǎng)站建設、網(wǎng)站維護、網(wǎng)站設計、App設計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

手機網(wǎng)站建設