一 圖的定義與操作

A 定義
圖是有頂點集合(Vertex)及頂點間的關系集合(Edge)組成的一種數據結構
Graph=(V,E)

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

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

權(Weight)的定義
1.與圖的邊相關的數據元素叫權
2.權常用來表示圖中頂點間的距離或者耗費

圖的一些常用操作
1.設置頂點的值 2.獲取頂點的值 3.獲取鄰接頂點 4.設置邊的值
5.刪除邊 6.獲取頂點數 等等

創(chuàng)新互聯公司長期為1000多家客戶提供的網站建設服務，團隊從業(yè)經驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯網生態(tài)環(huán)境。為樅陽企業(yè)提供專業(yè)的成都網站建設、網站建設，樅陽網站改版等技術服務。擁有10年豐富建站經驗和眾多成功案例,為您定制開發(fā)。

template 
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>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);
}；

二 圖的存儲結構

基本思想
1.用一維數組存儲頂點:描述頂點相關的數據
2.用二維數組存儲邊:描述頂點間的關系和權

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

實現方法一：直接使用數組表示頂點集和邊集

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

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

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

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

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

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

代碼實現

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

            if((0<=i)&&(iq;
                LinkQueuer;
                DynamicArrayvisited(vCount());

                for(int i=0;i0)
                {
                    int v=q.front();

                    q.remove();

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

                        for(int j=0;jlength();j++)
                        {
                            q.add((*aj)[j]);
                        }

                        r.add(v);

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

            return ret;
        }

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

            if((0<=i)&&(is;
                LinkQueuer;
                DynamicArrayvisited(vCount());

                for(int j=0;j0)
                {
                    int v=s.top();

                    s.pop();

                    if(!visited[v])
                    {
                        SharedPointer>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;
        }