国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)-學(xué)習(xí)-23-圖之鄰接矩陣與鄰接表

2年前作者：陽光九葉草LXGZXJ分類：Toy博客閱讀(18)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)-學(xué)習(xí)-23-圖之鄰接矩陣與鄰接表。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

目錄

一、定義和術(shù)語

二、存儲(chǔ)結(jié)構(gòu)

1、鄰接矩陣

1.1、鄰接矩陣優(yōu)點(diǎn)

1.2、鄰接矩陣缺點(diǎn)

2、鄰接表

3、鄰接矩陣和鄰接表的區(qū)別和用途

3.1、區(qū)別

3.2、用途

三、宏定義

四、結(jié)構(gòu)體定義

1、鄰接矩陣

2、鄰接表

3、網(wǎng)數(shù)據(jù)類型（造測試數(shù)據(jù)）

五、函數(shù)定義

1、使用鄰接矩陣創(chuàng)建無向網(wǎng)

2、使用鄰接表創(chuàng)建無向網(wǎng)

3、銷毀使用鄰接矩陣創(chuàng)建的無向網(wǎng)

4、銷毀使用鄰接表創(chuàng)建的無向網(wǎng)

六、Linux環(huán)境編譯測試

一、定義和術(shù)語

名詞 描述
圖 Graph = ( Vertex , Edge )
Vertex:頂點(diǎn)（數(shù)據(jù)元素）的有窮非空集合。
Edge:邊的有窮集合。
無向圖 每條邊都是無方向的。
有向圖 每條邊都是有方向的。
完全圖 任意兩個(gè)點(diǎn)都有一條邊相連。
無向完全圖：n個(gè)頂點(diǎn)，n * (n - 1) / 2條邊。
有向完全圖：n個(gè)頂點(diǎn)，n * (n - 1)條邊。
稀疏圖 有很少的邊或弧的圖。e < nlog2(n)
稠密圖 有較多的邊或弧的圖。e >= nlog2(n)
網(wǎng) 邊/弧帶權(quán)的圖。
鄰接 有邊/弧相連的兩個(gè)頂點(diǎn)之間的關(guān)系。
存在(vi, vj)，則稱vi和vj互為鄰接點(diǎn)。
存在<vi, vj>，則稱vi鄰接到vj，vj鄰接到vi。
關(guān)聯(lián)（依附） 邊/弧與頂點(diǎn)之間的關(guān)系。
存在(vi, vj) /?<vi, vj>，則稱該邊/弧關(guān)聯(lián)于vi和vj。
頂點(diǎn)的度

于該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，記作TD(v),在有向圖中，頂點(diǎn)的度等于該頂點(diǎn)的入度于出度之和。
頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù)，記作ID(v)。
頂點(diǎn)v的出度是以v為始點(diǎn)的有向邊的條數(shù)，記作OD(v)。
有向樹 當(dāng)有向圖中僅一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度為1.
路徑 接續(xù)的邊構(gòu)成的頂點(diǎn)序列。
路徑長度 路徑上邊或弧的數(shù)目/權(quán)值之和。
回路（環(huán)） 第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同路徑。
簡單路徑 除路徑起點(diǎn)和終點(diǎn)可以相同外，其余頂點(diǎn)均不相同的路徑。
簡單回路（簡單環(huán)） 除路徑起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)均不相同的路徑。
連通圖（強(qiáng)連通圖） 在無（有）向圖G = (V, {E})中，若對(duì)任何兩個(gè)頂點(diǎn)v，u都存在從v到u的路徑，則稱G是連通圖（強(qiáng)連通圖）。
權(quán)與網(wǎng) 圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。
帶權(quán)的圖稱為網(wǎng)。
子圖 設(shè)有兩個(gè)圖G = (V, {E})、G1 = (V1, {E1})，V1∈V，E1∈E，則稱G1是G的子圖。
連通分量（強(qiáng)連通分量） 無向圖G的極大連通子圖稱為G的連通分量。
極大連通子圖 該子圖是G的連通子圖，將G的任何不在該子圖中的頂點(diǎn)加入，子圖不再是連通。
強(qiáng)連通分量 有向圖G的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。
極大強(qiáng)連通子圖 該子圖是G的強(qiáng)連通子圖，將G的任何不在該子圖中的頂點(diǎn)加入，子圖不再是強(qiáng)連通。
極小連通子圖 該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。。
生成樹 包含無向圖G所有頂點(diǎn)的極小連通子圖。
生成森林 對(duì)非連通圖，由各個(gè)連通分量的生成樹的集合。

二、存儲(chǔ)結(jié)構(gòu)

圖的邏輯結(jié)構(gòu)是多對(duì)多的，具體分類如下：

分類名 描述
數(shù)組存儲(chǔ)結(jié)構(gòu) 1、鄰接矩陣。（本文介紹）
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1、鄰接表。（本文介紹）
2、鄰接多重表。
3、十字鏈表。

?這里以無向網(wǎng)為例，我們要畫一個(gè)這樣的。

鄰接表空間復(fù)雜度,# 數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)學(xué)習(xí),數(shù)據(jù)結(jié)構(gòu),算法,c語言,學(xué)習(xí),開發(fā)語言

測試數(shù)據(jù)：

舉例說明一下{0,3,10}，A->D且權(quán)值為10。

{'A','B','C','D','E'};
{{0,3,10},{0,1,20},{0,2,30},{2,3,10},{1,4,50},{3,4,20}};

1、鄰接矩陣

建立一個(gè)頂點(diǎn)表（記錄各個(gè)頂點(diǎn)信息）和一個(gè)鄰接矩陣（表示各個(gè)頂點(diǎn)之間關(guān)系）。

生成的鄰接矩陣如下：

VertexArray    : [A ,B ,C ,D ,E ]
ArcArray       :
[32767 ,20    ,30    ,10    ,32767 ]
[20    ,32767 ,32767 ,32767 ,50    ]
[30    ,32767 ,32767 ,10    ,32767 ]
[10    ,32767 ,10    ,32767 ,20    ]
[32767 ,50    ,32767 ,20    ,32767 ]

[32767 ,20 ? ?,30 ? ?,10 ? ?,32767 ]第一行表示：A->A不通，A->B通，A->C通，A->D通，A->E不通。

特性1：無向網(wǎng)的鄰接矩陣是對(duì)稱的。

特性2：頂點(diǎn)i的度等于第i行中非極大值（32767）的個(gè)數(shù)。

特別：完全網(wǎng)的鄰接矩陣中，對(duì)角元素為32767，其余皆為非32767。

1.1、鄰接矩陣優(yōu)點(diǎn)

（1）直觀好理解。

（2）容易判斷兩個(gè)頂點(diǎn)間是否存在邊或弧。

（3）容易查找任意頂點(diǎn)的所有鄰接點(diǎn)。

（4）方便計(jì)算任意頂點(diǎn)的度。

1.2、鄰接矩陣缺點(diǎn)

（1）添加和刪除頂點(diǎn)不方便。

（2）存儲(chǔ)稀疏圖時(shí)浪費(fèi)空間。

（3）統(tǒng)計(jì)稀疏圖一共有多少條邊浪費(fèi)時(shí)間。

2、鄰接表

頂點(diǎn)：按編號(hào)順序?qū)㈨旤c(diǎn)數(shù)據(jù)存儲(chǔ)在一維數(shù)組中。

關(guān)聯(lián)同一頂點(diǎn)的邊（以頂點(diǎn)為尾的弧）：用線性鏈表存儲(chǔ)。

生成的鄰接表如下：

A : [ (2, 30, 0x15ac8b0),(1, 20, 0x15ac870),(3, 10, (nil))]
B : [ (4, 50, 0x15ac8d0),(0, 20, (nil))]
C : [ (3, 10, 0x15ac910),(0, 30, (nil))]
D : [ (4, 20, 0x15ac950),(2, 10, 0x15ac890),(0, 10, (nil))]
E : [ (3, 20, 0x15ac990),(1, 50, (nil))]

A : [ (2, 30, 0x15ac8b0),(1, 20, 0x15ac870),(3, 10, (nil))]第一行表示：A->C通、權(quán)值30、下一個(gè)結(jié)點(diǎn)指針，A->B通、權(quán)值20、下一個(gè)結(jié)點(diǎn)指針，A->D通、權(quán)值10、下一個(gè)結(jié)點(diǎn)指針。

特性1：鄰接表不唯一。

特性2：若無向網(wǎng)中有n個(gè)頂點(diǎn)、e條邊，則其鄰接表需要n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。存儲(chǔ)稀疏圖比較合適。

特性3：無向網(wǎng)中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)。

特性4：鄰接表出度易找，入度難找。逆鄰接表出度難找，入度易找。

3、鄰接矩陣和鄰接表的區(qū)別和用途

3.1、區(qū)別

（1）對(duì)于任一確定的無向網(wǎng)，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一。

（2）鄰接矩陣的空間復(fù)雜度是O(n^2)，鄰接表為O(n + e)。

（3）鄰接矩陣的時(shí)間復(fù)雜度是O(n^2)，鄰接表為O(elog2(e))。

3.2、用途

鄰接矩陣多用于稠密圖。

鄰接表多用于稀疏圖。文章來源地址http://www.zghlxwxcb.cn/news/detail-623533.html

三、宏定義

#define MAX_INT_TYPE_NUM      32767 //網(wǎng)中代表無窮大，也代表頂點(diǎn)個(gè)數(shù)。
#define MAX_VERTEX_NUM        10000 //頂點(diǎn)數(shù)組中存放頂點(diǎn)的最大個(gè)數(shù)。
#define NET_DIRECTION_FLAG    0     //有向網(wǎng)的標(biāo)志
#define NET_UNDIRECTION_FLAG  1     //無向網(wǎng)的標(biāo)志

四、結(jié)構(gòu)體定義

1、鄰接矩陣

//鄰接矩陣圖
typedef struct AdjacencyMatrixGraph
{
    VertexType VertexArray[MAX_VERTEX_NUM];
    ArcType    ArcArray[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int        CurVertexNum; //頂點(diǎn)數(shù)組中當(dāng)前的頂點(diǎn)數(shù)。
    int        CurArcNum;    //弧數(shù)組中當(dāng)前的弧個(gè)數(shù)。
}AMGraph;

2、鄰接表

//鄰接表
typedef struct ArcNode
{
    VertexIndexType EndVertexIndex;
    WeightType      Weight;
    struct ArcNode* NextNodePtr;
}ArcNode;

typedef struct VertexNode
{
    VertexType Vertex;
    ArcNode*   FirstArcNodePtr;
}VertexNode;

typedef struct AdjacencyGragh
{
    VertexNode* Vertices;
    int         VertexNum;        //鄰接表中的頂點(diǎn)數(shù)。
    int         ArcNum;           //鄰接表中的弧個(gè)數(shù)。        
}AGraph;

3、網(wǎng)數(shù)據(jù)類型（造測試數(shù)據(jù)）

//網(wǎng)數(shù)據(jù)類型
typedef struct NetArcDataType
{
    VertexIndexType StartVertexIndex;//起始頂點(diǎn)。
    VertexIndexType EndVertexIndex;  //結(jié)束頂點(diǎn)。
    WeightType      Weight;          //權(quán)值。
}NetArcDataType;                     //數(shù)據(jù)為網(wǎng)的弧或邊的信息。

// NetArcDataType  NetArcDataArray[MAX_VERTEX_NUM * (MAX_VERTEX_NUM - 1)]。
// 問題簡記，如果MAX_VERTEX_NUM為1000時(shí)，在malloc NetDataType*類型內(nèi)存時(shí)，會(huì)出現(xiàn)段錯(cuò)誤。
typedef struct NetDataType
{
    VertexType*     VertexArray;
    NetArcDataType* NetArcDataArray;  //有向圖完全圖的邊最多，頂點(diǎn)n,邊最多為n*(n-1)。
    int             VertexNum;        //頂點(diǎn)數(shù)據(jù)數(shù)組中的頂點(diǎn)數(shù)。
    int             ArcNum;           //弧數(shù)據(jù)數(shù)組中的弧個(gè)數(shù)。
    int             DirectionFlag;    //無向圖還是有向圖的標(biāo)志。
}NetDataType;                         //數(shù)據(jù)為網(wǎng)的信息。

五、函數(shù)定義

1、使用鄰接矩陣創(chuàng)建無向網(wǎng)

Status CreateUndirectionNetUseAMGraph(AMGraph** AMG, NetDataType NDT)
{
    *AMG = (AMGraph*)MyMalloc(sizeof(AMGraph));    

    int i,j;

    (*AMG)->CurVertexNum = NDT.VertexNum;  //頂點(diǎn)數(shù)復(fù)制。
    (*AMG)->CurArcNum    = NDT.ArcNum * 2; //邊數(shù)復(fù)制，由于無向圖是雙向的，所以需要乘2。
        
    //頂點(diǎn)數(shù)組復(fù)制。
    memcpy((*AMG)->VertexArray, NDT.VertexArray, sizeof(VertexType) * ((*AMG)->CurVertexNum));

    //初始化網(wǎng)中弧或邊數(shù)組，統(tǒng)一初始化為無窮大，這里設(shè)置為int的最大值32767。
    for(i = 0; i < (*AMG)->CurVertexNum; i++)
    {
        for(j = 0; j < (*AMG)->CurVertexNum; j++)
        {   
            (*AMG)->ArcArray[i][j] = MAX_INT_TYPE_NUM;
        }
    }

    //把網(wǎng)數(shù)據(jù)中的弧或邊數(shù)據(jù)填充到鄰接矩陣圖中。
    for(i = 0; i < NDT.ArcNum; i++)
    {
        (*AMG)->ArcArray[NDT.NetArcDataArray[i].StartVertexIndex][NDT.NetArcDataArray[i].EndVertexIndex] = NDT.NetArcDataArray[i].Weight;
        (*AMG)->ArcArray[NDT.NetArcDataArray[i].EndVertexIndex][NDT.NetArcDataArray[i].StartVertexIndex] = NDT.NetArcDataArray[i].Weight;
    }
    Log("Create Undirection Net Use AMGraph : OK\n",Info);
    return SuccessFlag;
}

2、使用鄰接表創(chuàng)建無向網(wǎng)

Status CreateUndirectionNetUseAGraph(AGraph** AG, NetDataType NDT)
{
    (*AG) = (AGraph*)MyMalloc(sizeof(AGraph));

    (*AG)->VertexNum = NDT.VertexNum;
    (*AG)->ArcNum    = NDT.ArcNum * 2;

    //init adjacency graph
    (*AG)->Vertices = (VertexNode*)MyMalloc(sizeof(VertexNode) * (*AG)->VertexNum);
    int i;
    for(i = 0; i < (*AG)->VertexNum; i++)
    {
        (*AG)->Vertices[i].Vertex          = NDT.VertexArray[i];
        (*AG)->Vertices[i].FirstArcNodePtr = NULL;
    }

    //add arc to adjacency graph
    ArcNode* TmpArcNode  = NULL;
    for(i = 0; i < NDT.ArcNum; i++)
    {
        //printf("%d, %d, %d\n",NDT.NetArcDataArray[i].StartVertexIndex,NDT.NetArcDataArray[i].EndVertexIndex,NDT.NetArcDataArray[i].Weight);
        ArcNode* NewArcNode        = (ArcNode*)MyMalloc(sizeof(ArcNode));
        NewArcNode->EndVertexIndex = NDT.NetArcDataArray[i].EndVertexIndex;
        NewArcNode->Weight         = NDT.NetArcDataArray[i].Weight;
        NewArcNode->NextNodePtr    = NULL;

        TmpArcNode = (*AG)->Vertices[NDT.NetArcDataArray[i].StartVertexIndex].FirstArcNodePtr;
        if(TmpArcNode == NULL)//說明弧結(jié)點(diǎn)鏈表頭部為空
        {
            (*AG)->Vertices[NDT.NetArcDataArray[i].StartVertexIndex].FirstArcNodePtr = NewArcNode;
        }
        else
        {
            NewArcNode->NextNodePtr                                                  = TmpArcNode;
            (*AG)->Vertices[NDT.NetArcDataArray[i].StartVertexIndex].FirstArcNodePtr = NewArcNode; //頭插法,效率高。
        }

        ArcNode* NewArcNode1        = (ArcNode*)MyMalloc(sizeof(ArcNode));
        NewArcNode1->EndVertexIndex = NDT.NetArcDataArray[i].StartVertexIndex;
        NewArcNode1->Weight         = NDT.NetArcDataArray[i].Weight;
        NewArcNode1->NextNodePtr    = NULL;

        TmpArcNode = (*AG)->Vertices[NDT.NetArcDataArray[i].EndVertexIndex].FirstArcNodePtr;
        if(TmpArcNode == NULL)//說明弧結(jié)點(diǎn)鏈表頭部為空
        {
            (*AG)->Vertices[NDT.NetArcDataArray[i].EndVertexIndex].FirstArcNodePtr = NewArcNode1;
        }
        else
        {
            NewArcNode1->NextNodePtr                                               = TmpArcNode;
            (*AG)->Vertices[NDT.NetArcDataArray[i].EndVertexIndex].FirstArcNodePtr = NewArcNode1;
        }
    }
    Log("Create Undirection Net Use AGraph  : OK\n",Info);
    return SuccessFlag;
}

3、銷毀使用鄰接矩陣創(chuàng)建的無向網(wǎng)

Status DestoryUndirectionNetUseAMGraph(AMGraph** AMG)
{
    JudgeAllNullPointer(AMG);
    JudgeAllNullPointer(*AMG);
    free(*AMG);
    *AMG = NULL;
    Log("Destory Undirection Net Use AMGraph: OK\n",Info);
    return SuccessFlag;
}

4、銷毀使用鄰接表創(chuàng)建的無向網(wǎng)

Status DestoryUndirectionNetUseAGraph(AGraph** AG)
{
    JudgeAllNullPointer(AG);
    JudgeAllNullPointer(*AG);

    ArcNode* TmpArcNode = NULL;
    ArcNode* CurArcNode = NULL;   

    //free All ArcNode
    int i;
    for(i = 0; i < (*AG)->VertexNum; i++)
    {
        (*AG)->Vertices[i].Vertex = '\0';
        TmpArcNode = (*AG)->Vertices[i].FirstArcNodePtr;
        CurArcNode = TmpArcNode;
        while(CurArcNode != NULL)
        {
            TmpArcNode = CurArcNode->NextNodePtr;
            free(CurArcNode);
            CurArcNode = TmpArcNode;
        }
    }
    
    //free VertexNode
    free((*AG)->Vertices);
    (*AG)->Vertices = NULL;

    //free AGraph
    (*AG)->VertexNum = 0;
    (*AG)->ArcNum    = 0;
    free(*AG);    
    *AG              = NULL;

    Log("Destory Undirection Net Use AGraph : OK\n",Info);
    return SuccessFlag;
}

六、Linux環(huán)境編譯測試

[gbase@czg2 Graph]$ make
gcc -Wall -Wextra -g ../Log/Log.c /APP/Tpl/Home/Default/PublicFunction/PublicFunction.c /APP/Tpl/Home/Default/PublicFunction/SqQueue/SqQueue.c Graph.c main.c -o TestGraph -I ../Log/ -I /APP/Tpl/Home/Default/PublicFunction/ -I ../Select/ -I /APP/Tpl/Home/Default/PublicFunction/SqQueue/

[gbase@czg2 Graph]$ ./TestGraph 
[2023-5]--[ Info  ]--Create Net Data                    : OK
[2023-5]--[ Info  ]--Create Undirection Net Use AMGraph : OK
[2023-5]--[ Debug ]--Printf AMGraph                     :
VertexArray    : [A ,B ,C ,D ,E ]
ArcArray       :
[32767 ,20    ,30    ,10    ,32767 ]
[20    ,32767 ,32767 ,32767 ,50    ]
[30    ,32767 ,32767 ,10    ,32767 ]
[10    ,32767 ,10    ,32767 ,20    ]
[32767 ,50    ,32767 ,20    ,32767 ]
CurVertexNum   : 5
CurArcNum      : 12
[2023-5]--[ Info  ]--Create Undirection Net Use AGraph  : OK
[2023-5]--[ Debug ]--Printf AGraph                      :
A : [ (2, 30, 0xe078b0),(1, 20, 0xe07870),(3, 10, (nil))]
B : [ (4, 50, 0xe078d0),(0, 20, (nil))]
C : [ (3, 10, 0xe07910),(0, 30, (nil))]
D : [ (4, 20, 0xe07950),(2, 10, 0xe07890),(0, 10, (nil))]
E : [ (3, 20, 0xe07990),(1, 50, (nil))]
VertexNum      : 5
ArcNum         : 12

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)-學(xué)習(xí)-23-圖之鄰接矩陣與鄰接表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包