一 圖的定義與操作

A 定義
圖是有頂點(diǎn)集合(Vertex)及頂點(diǎn)間的關(guān)系集合(Edge)組成的一種數(shù)據(jù)結(jié)構(gòu)
Graph=(V,E)

無向邊
1.頂點(diǎn)x和y之間的邊沒有方向,則稱該邊為 無向邊
2.(x,y)與(y,x)意義相同，表示x和y之間有連接
無向圖
圖中任意兩個(gè)頂點(diǎn)之間的邊均是無向邊，則稱該圖為無向圖
有向邊
1.頂點(diǎn)x和y之間的邊有方向，則稱該邊為有向邊
2.<x,y>與<y,x>意義不同，前項(xiàng)表示從x連接到y(tǒng)，后項(xiàng)表示從y連接到x
有向圖
圖中任意兩個(gè)頂點(diǎn)之間的邊鈞是有向邊，則稱該圖為有向圖

頂點(diǎn)鄰接的定義
1.無向圖--如果(x,y)屬于E,則稱x和y互為鄰接
2.有向圖--如果<x,y>屬于E,則稱頂點(diǎn)x鄰接到頂點(diǎn)y
度(Degree)的定義
1.頂點(diǎn)v的度是和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)
a.入度:以v為頭的邊的數(shù)目，記為ID(v)
b.出度:以v為尾的邊的數(shù)目，記為OD(v)

權(quán)(Weight)的定義
1.與圖的邊相關(guān)的數(shù)據(jù)元素叫權(quán)
2.權(quán)常用來表示圖中頂點(diǎn)間的距離或者耗費(fèi)

圖的一些常用操作
1.設(shè)置頂點(diǎn)的值 2.獲取頂點(diǎn)的值 3.獲取鄰接頂點(diǎn) 4.設(shè)置邊的值
5.刪除邊 6.獲取頂點(diǎn)數(shù) 等等

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：申請域名、網(wǎng)站空間、營銷軟件、網(wǎng)站建設(shè)、多倫網(wǎng)站維護(hù)、網(wǎng)站推廣。

template <typename V,typename E>
class Graph:public Object
{
public:
        virtual V getVertex(int x)=0;
        virtual bool getVertex(int x,V& value)=0;
        virtual bool setVertex(int i,const V& value)=0;
        virtual SharedPointer<Array<int>>getAdjacent(int i)=0;
        virtual E getEdge(int i,int j)=0;
        virtual bool getEdge(int i, int j,E& value)=0;
        virtual bool setEdge(int i, int j,const E& value)=0;
        virtual bool removeEdge(int i,int j)=0;
        virtual int vCount()=0;
        virtual int eCount()=0;
        virtual int OD(int i)=0;
        virtual int ID(int i)=0;
                virtual int TD(int i);
}；

二 圖的存儲結(jié)構(gòu)

基本思想
1.用一維數(shù)組存儲頂點(diǎn):描述頂點(diǎn)相關(guān)的數(shù)據(jù)
2.用二維數(shù)組存儲邊:描述頂點(diǎn)間的關(guān)系和權(quán)

鄰接矩陣法
-設(shè)圖A=(V,E)是一個(gè)有n個(gè)頂點(diǎn)的圖，圖的鄰接矩陣為Edge[n][n],則

實(shí)現(xiàn)方法一：直接使用數(shù)組表示頂點(diǎn)集和邊集

template <int N,typename V,typename E>
class MatrixGraph:public Graph<V,E>
{
    protected:
        V m_vertexes[N];
        E m_edges[N][N];
        int m_eCount;
    public:
    //......
};

問題：
1.構(gòu)造效率低下--圖對象初始化時(shí)，頻繁調(diào)用頂點(diǎn)類型和邊類型的構(gòu)造函數(shù)
2.空間使用率低下--圖對象占用大量空間，而大多數(shù)空間處于閑置狀態(tài)
3.無法表示空值--無法用統(tǒng)一的方式表示為空的情形
實(shí)現(xiàn)方式二：使用指針數(shù)組表示頂點(diǎn)集和邊集

template <int N,typename V,typename E>
class MatrixGraph:public Graph<V,E>
{
    protected:
        V* m_vertexes[N];
        E* m_edges[N][N];
        int m_eCount;
    public:
    //......
};

問題的解決：
1.構(gòu)造效率--初始化圖像時(shí)，只需要將數(shù)組元素賦值為空
2.空間使用率--頂點(diǎn)數(shù)據(jù)元素和邊數(shù)據(jù)元素在需要時(shí)動態(tài)創(chuàng)建
3.空值的表示--任意的頂點(diǎn)類型和邊類型都使用NULL表示空值

圖的遍歷
1.廣度優(yōu)先--以二叉樹層次遍歷的思想對圖進(jìn)行遍歷
2.深度優(yōu)先--以二叉樹先序遍歷的思想對圖進(jìn)行遍歷
A.廣度優(yōu)先算法
-原料：隊(duì)列 LinkQueue<T>
-步驟
1.將起始頂點(diǎn)壓入隊(duì)列中
2.隊(duì)頭頂點(diǎn)v彈出，判斷是否已經(jīng)標(biāo)記
3.標(biāo)記頂點(diǎn)v，并將頂點(diǎn)v的鄰接頂點(diǎn)壓入隊(duì)列中
4.判斷隊(duì)列是否為空

B.深度優(yōu)先算法
-原料：class LinkStack<T>;
-步驟：
1.將起始點(diǎn)壓入棧中
2.彈出棧頂頂點(diǎn)v，判斷是否已經(jīng)標(biāo)記
3.標(biāo)記頂點(diǎn)v，并將頂點(diǎn)v的鄰接頂點(diǎn)壓入棧中
4.判斷棧是否為空

代碼實(shí)現(xiàn)

 SharedPointer<Array<int>>BFS(int i)
        {
            DynamicArray<int>* ret=NULL;

            if((0<=i)&&(i<vCount()))
            {
                LinkQueue<int>q;
                LinkQueue<int>r;
                DynamicArray<bool>visited(vCount());

                for(int i=0;i<visited.length();i++)
                {
                    visited[i]=false;
                }

                q.add(i);

               while(q.length()>0)
                {
                    int v=q.front();

                    q.remove();

                    if(!visited[v])
                    {
                        SharedPointer< Array<int> >aj=getAdjacent(v);

                        for(int j=0;j<aj->length();j++)
                        {
                            q.add((*aj)[j]);
                        }

                        r.add(v);

                        visited[v]=true;
                    }
                }
                ret=toArray(r);
            }
            else
            {
                THROW_EXCEPTION(InvalidParameterException,"0.0");
            }

            return ret;
        }

        SharedPointer<Array<int>>DFS(int i)
        {
            DynamicArray<int>* ret=NULL;

            if((0<=i)&&(i<vCount()))
            {
                LinkStack<int>s;
                LinkQueue<int>r;
                DynamicArray<bool>visited(vCount());

                for(int j=0;j<visited.length();j++)
                {
                    visited[j]=false;
                }

                s.push(i);

               while(s.size()>0)
                {
                    int v=s.top();

                    s.pop();

                    if(!visited[v])
                    {
                        SharedPointer<Array<int>>aj=getAdjacent(v);

                        for(int j=aj->length()-1;j>=0;j--)
                        {
                            s.push((*aj)[j]);
                        }

                        r.add(v);
                        visited[v]=true;
                    }
                }
                ret=toArray(r);
            }
            else
            {
                THROW_EXCEPTION(InvalidParameterException,"...");
            }
            return ret;
        }

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

文章題目：數(shù)據(jù)結(jié)構(gòu)--圖-創(chuàng)新互聯(lián)
本文路徑：http://chinadenli.net/article32/ddihsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊、移動網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)公司、營銷型網(wǎng)站建設(shè)、軟件開發(fā)

廣告

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