数据结构（17.2）图之邻接表存储

￡神魔★判官ぃ 2023-03-01 03:30 10阅读 0赞

### 数据结构（17.2）图之邻接表存储 ###

*   *   *  前言
         *  图的初始化
         *  顶点和边的插入
         *   *  顶点的插入
             *  边的插入
         *  顶点和边的删除
         *   *  边的删除
             *  顶点的删除
         *  全部代码
         *   *  GrapLnk.h
             *  GrapLnk.c
             *  Main.c

### 前言 ###

在上一篇文章中，已经详细介绍了图的四种存储结构的区别，这里我们就不再过多说明了。

图的邻接表存储里，每一个顶点类似于一个单链表，头结点即顶点结点，其余的结点即边结点；每一个顶点又需要存储到一个列表中，就形成了一个邻接表。

![img\_1][img_1]

无论是头结点还是边结点，都有数据域和指针域两个部分。顶点结点的指针域指向其第一个边结点，而边结点的指针域指向本顶点的下一个边结点，类似于单链表的next指针。注意：边结点的数据域存储的是另一端顶点的地址，只是因为在数组中，因此是int类型；假设存储顶点的列表也是单链表，则其类型应该是顶点的指类型。

//边的结构
    typedef struct Edge{ 
        //顶点的下标
        //顶点列表为单链表：struct Vertex* dest;
        int dest;
        //下一条边
        struct Edge* Link;
    }Edge;
    
    //顶点的结构
    typedef struct Vertex{ 
        //顶点
        T data;
        //边
        Edge *adj;
    }Vertex;
    
    //图本身的结构
    typedef struct GraphLnk{ 
        //最大顶点数量
        int MaxVertices;
        //当前顶点数量
        int NumVertices;
        //当前边的数量
        int NumEdges;
        //顶点的列表
        Vertex *NodeTable;
    }GraphLnk;

本次我们实现的是无向图。

### 图的初始化 ###

初始化包括两个部分，即数据的初始化和空间的开辟。在邻接表表示法中，还需要注意顶点的列表开辟完空间后，也需要初始化里面的数据。

//初始化图
    void InitGraph(GraphLnk *g){ 
        //初始化值
        g->MaxVertices = DEFAULT_VERTEX_SIZE;
        g->NumVertices = g->NumEdges = 0;
        
        //开辟空间
        g->NodeTable = (Vertex *)malloc(sizeof(Vertex) * g->MaxVertices);
        assert(g->NodeTable != NULL);
        
        //初始化
        for (int i = 0; i < g->MaxVertices; i ++) { 
            g->NodeTable[i].data = '\0';
            g->NodeTable[i].adj = NULL;
        }
    }

### 顶点和边的插入 ###

#### 顶点的插入 ####

这里顶点的列表和邻接矩阵表示法一样，是一个数组。因此插入顶点只需要将顶点存入即可。

//插入顶点
    void InsertVertex(GraphLnk *g,T v){ 
        if (g->NumVertices >= g->MaxVertices) { 
            printf("顶点数量已达到最大\n");
            return;
        }
        g->NodeTable[g->NumVertices ++].data = v;
    }

#### 边的插入 ####

插入边即在顶点的边列表中存入边的信息，因此首先需要找到顶点。

//找到顶点在列表中的位置
    int GetVertexPos(GraphLnk *g,T v){ 
        for (int i = 0; i < g->NumVertices; i ++) { 
            if (g->NodeTable[i].data == v) { 
                return i;
            }
        }
        return -1;
    }

找到顶点后，需要创建一个边结点，然后将该结点存入链表中。因为我们实现的是无向图，所以两个顶点的链表都需要修改，也就是说需要创建两个边结点。

//插入边
    void InsertEdge(GraphLnk *g,T v1, T v2){ 
        int p1 = GetVertexPos(g, v1);
        int p2 = GetVertexPos(g, v2);
        
        if (p1 == -1 || p2 == -1) { 
            printf("有顶点不存在\n");
            return;
        }
        
        
        //创造边结点1
        Edge *s1 = (Edge *)malloc(sizeof(Edge));
        assert(s1 != NULL);
        s1->dest = p2;
        
        //插入
        s1->Link = g->NodeTable[p1].adj;
        g->NodeTable[p1].adj = s1;
        
        //创造边结点2
        Edge *s2 = (Edge *)malloc(sizeof(Edge));
        assert(s2!= NULL);
        s2->dest = p1;
        
        //插入
        s2->Link = g->NodeTable[p2].adj;
        g->NodeTable[p2].adj = s2;
    }

### 顶点和边的删除 ###

#### 边的删除 ####

边的删除思路上很简单：要删除两个顶点之间的边，首先得到要顶点的边列表，遍历这个链表找到要删除的边结点，然后删除即可。

由于是在单链表上做删除，还需要一个指针（v）来指向要删除结点（s）的前驱，这样删除即 `v->Link = s->Link;`。可能还有人记得，如果单链表是没有头结点的结构，做删除时需要对第一个顶点特判（因为第一个顶点没有前驱）。

同时，我们做的是无线图，因此两个结点的边列表都要删除，假如我们在遍历第一个结点的边列表时就发现没有要删除的边，可以直接退出函数。

//删除边
    void RemoveEdge(GraphLnk *g,T v1,T v2){ 
        int p1 = GetVertexPos(g, v1);
        int p2 = GetVertexPos(g, v2);
        if (p1 == -1 || p2 == -1) { 
            printf("有结点不存在\n");
            return;
        }
        
        Edge *s = g->NodeTable[p1].adj;
        //指向s的前驱
        Edge *v = NULL;
        while (s != NULL && s->dest != p2) { 
            v = s;
            s = s->Link;
        }
        if (s != NULL) { 
            //找到了
            if (v == NULL) { 
                //找到的是第一个结点
                g->NodeTable[p1].adj = s->Link;
            }else{ 
                v->Link = s->Link;
            }
            free(s);
        }else{ 
            printf("要删除的边不存在\n");
            return;
        }
        
        s = g->NodeTable[p2].adj;
        v = NULL;
        while (s != NULL && s->dest != p1) { 
            v = s;
            s = s->Link;
        }
        if (s != NULL) { 
            //找到了
            if (v == NULL) { 
                //找到的是第一个结点
                g->NodeTable[p2].adj = s->Link;
            }else{ 
                v->Link = s->Link;
            }
            free(s);
        }
    }

#### 顶点的删除 ####

删除顶点，先将顶点有关的边全部删除，再将顶点删除。由于顶点有自己的边链表，因此删除边非常容易，只需要遍历链表依次释放空间即可。

但是有两点需要注意：

1.  我们实现的是无向图，因此除了删除本顶点的边以外，还要在要删除的边的另一个顶点处，删除这条边的信息
2.  我们在对顶点进行删除时，还是有两种方法：数组中后续的顶点向前移动覆盖掉被删除的顶点，或者使用最后一个顶点结点替换掉删除的顶点。
    
    但是，我们的顶点列表使用的是一个数组，因此边结点中存放的地址信息是顶点的下标。无论采用哪种方法来做删除，都会让顶点的下标（相当于位置）发生改变。由于是无向图，另一头的边结点中也存放着顶点的下标，这样，在修改顶点时，还需要去更新另一头的边结点的下标。
    
    显然，直接使用最后一个顶点来替换掉被删除的顶点，只需要修改一个顶点的有关信息；比用后续顶点覆盖节省很多操作。
    
    但是使用邻接表来存储无向图还是有些麻烦的，因此可以使用邻接多重表；或者说顶点列表也用单链表来存储，这样就省去了修改下标的操作。

//删除顶点
    void RemoveVertex(GraphLnk *g,T vertex){ 
        int v = GetVertexPos(g, vertex);
        if (v == -1) { 
            return;
        }
        
        //删除边
        Edge *p = g->NodeTable[v].adj;
        
        //边的另一个顶点
        int k;
        Edge *pres = NULL;
        Edge *s = NULL;
        //遍历要删除顶点的边列表
        while (p != NULL) { 
            //在另一个顶点中找到这条边
            k = p->dest;
            s = g->NodeTable[k].adj;
            while (s != NULL && s->dest != v) { 
                pres = s;
                s = s->Link;
            }
            //删除
            if (s != NULL) { 
                if (pres == NULL) { 
                    g->NodeTable[k].adj = s->Link;
                }else{ 
                    pres->Link = s->Link;
                }
                free(s);
            }
            //删除本结点中的这条边
            g->NodeTable[v].adj = p->Link;
            free(p);
            //继续删除属于本结点的下一条边
            p = g->NodeTable[v].adj;
        }
        
        //删除点
        g->NumVertices --;
        g->NodeTable[v].data = g->NodeTable[g->NumVertices].data;
        g->NodeTable[v].adj = g->NodeTable[g->NumVertices].adj;
            
        /* 遍历边列表，找到边的另一个顶点 修改另一个顶点中边结点的地址 */
        s = g->NodeTable[v].adj;
        while (s != NULL) { 
            //在另一个顶点中找到这条边
            k = s->dest;
            p = g->NodeTable[k].adj;
            while (p != NULL) { 
                //修改边中顶点的地址
                if (p->dest == g->NumVertices) { 
                    p->dest = v;
                    break;
                }
                p = p->Link;
            }
            s = s->Link;
        }
    }

### 全部代码 ###

#### GrapLnk.h ####

#ifndef GraphLnk_h
    #define GraphLnk_h
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    #define DEFAULT_VERTEX_SIZE 10
    #define T char
    
    //边的结构
    typedef struct Edge{ 
        //顶点的下标
        int dest;
        //下一条边
        struct Edge* Link;
    }Edge;
    
    //顶点的结构
    typedef struct Vertex{ 
        //顶点
        T data;
        //边
        Edge *adj;
    }Vertex;
    
    typedef struct GraphLnk{ 
        //最大顶点数量
        int MaxVertices;
        //当前顶点数量
        int NumVertices;
        //当前边的数量
        int NumEdges;
        //顶点的列表
        Vertex *NodeTable;
    }GraphLnk;
    
    //初始化图
    void InitGraph(GraphLnk *g);
    
    //展示图
    void ShowGraph(GraphLnk *g);
    //找到某个结点的位置
    int GetVertexPos(GraphLnk *g,T v);
    
    //插入顶点
    void InsertVertex(GraphLnk *g,T v);
    //插入边
    void InsertEdge(GraphLnk *g,T v1, T v2);
    
    //删除顶点
    void RemoveVertex(GraphLnk *g,T vertex);
    //删除边
    void RemoveEdge(GraphLnk *g,T v1,T v2);
    
    //摧毁
    void DestroyGraph(GraphLnk *g);
    
    //获取第一个邻接顶点
    int GetFirstNeighbor(GraphLnk *g,T vertex);
    //获取下一个邻接顶点
    int GetNextNeighbor(GraphLnk *g,T vertex1,T vertex2);
    
    #endif /* GraphLnk_h */

#### GrapLnk.c ####

#include "GraphLnk.h"
    
    //初始化图
    void InitGraph(GraphLnk *g){ 
        //初始化值
        g->MaxVertices = DEFAULT_VERTEX_SIZE;
        g->NumVertices = g->NumEdges = 0;
        
        //开辟空间
        g->NodeTable = (Vertex *)malloc(sizeof(Vertex) * g->MaxVertices);
        assert(g->NodeTable != NULL);
        
        //初始化
        for (int i = 0; i < g->MaxVertices; i ++) { 
            g->NodeTable[i].data = '\0';
            g->NodeTable[i].adj = NULL;
        }
    }
    //展示图
    void ShowGraph(GraphLnk *g){ 
        
        Edge *p;
        for (int i = 0; i < g->NumVertices; i ++) { 
            //打印顶点
            printf("%d %c:",i,g->NodeTable[i].data);
            
            //打印边
            p = g->NodeTable[i].adj;
            while (p != NULL) { 
                printf("%2d",p->dest);
                p = p->Link;
            }
            printf("\n");
        }
        printf("\n");
    }
    
    
    
    //找到某个结点的位置
    int GetVertexPos(GraphLnk *g,T v){ 
        for (int i = 0; i < g->NumVertices; i ++) { 
            if (g->NodeTable[i].data == v) { 
                return i;
            }
        }
        return -1;
    }
    
    //插入顶点
    void InsertVertex(GraphLnk *g,T v){ 
        if (g->NumVertices >= g->MaxVertices) { 
            printf("顶点数量已达到最大\n");
            return;
        }
        g->NodeTable[g->NumVertices ++].data = v;
    }
    
    //插入边
    void InsertEdge(GraphLnk *g,T v1, T v2){ 
        int p1 = GetVertexPos(g, v1);
        int p2 = GetVertexPos(g, v2);
        
        if (p1 == -1 || p2 == -1) { 
            printf("有顶点不存在\n");
            return;
        }
        
        
        //创造边结点1
        Edge *s1 = (Edge *)malloc(sizeof(Edge));
        assert(s1 != NULL);
        s1->dest = p2;
        
        //插入
        s1->Link = g->NodeTable[p1].adj;
        g->NodeTable[p1].adj = s1;
        
        //创造边结点2
        Edge *s2 = (Edge *)malloc(sizeof(Edge));
        assert(s2!= NULL);
        s2->dest = p1;
        
        //插入
        s2->Link = g->NodeTable[p2].adj;
        g->NodeTable[p2].adj = s2;
    }
    
    //删除顶点
    void RemoveVertex(GraphLnk *g,T vertex){ 
        int v = GetVertexPos(g, vertex);
        if (v == -1) { 
            return;
        }
        
        //删除边
        Edge *p = g->NodeTable[v].adj;
        
        //边的另一个顶点
        int k;
        Edge *pres = NULL;
        Edge *s = NULL;
        //遍历要删除顶点的边列表
        while (p != NULL) { 
            //在另一个顶点中找到这条边
            k = p->dest;
            s = g->NodeTable[k].adj;
            while (s != NULL && s->dest != v) { 
                pres = s;
                s = s->Link;
            }
            //删除
            if (s != NULL) { 
                if (pres == NULL) { 
                    g->NodeTable[k].adj = s->Link;
                }else{ 
                    pres->Link = s->Link;
                }
                free(s);
            }
            //删除本结点中的这条边
            g->NodeTable[v].adj = p->Link;
            free(p);
            //继续删除属于本结点的下一条边
            p = g->NodeTable[v].adj;
        }
        
        //删除点
        g->NumVertices --;
        g->NodeTable[v].data = g->NodeTable[g->NumVertices].data;
        g->NodeTable[v].adj = g->NodeTable[g->NumVertices].adj;
            
        /* 遍历边列表，找到边的另一个顶点 修改另一个顶点中边结点的地址 */
        s = g->NodeTable[v].adj;
        while (s != NULL) { 
            //在另一个顶点中找到这条边
            k = s->dest;
            p = g->NodeTable[k].adj;
            while (p != NULL) { 
                //修改边中顶点的地址
                if (p->dest == g->NumVertices) { 
                    p->dest = v;
                    break;
                }
                p = p->Link;
            }
            s = s->Link;
        }
    }
    //删除边
    void RemoveEdge(GraphLnk *g,T v1,T v2){ 
        int p1 = GetVertexPos(g, v1);
        int p2 = GetVertexPos(g, v2);
        if (p1 == -1 || p2 == -1) { 
            printf("有结点不存在\n");
            return;
        }
        
        Edge *s = g->NodeTable[p1].adj;
        //指向s的前驱
        Edge *v = NULL;
        while (s != NULL && s->dest != p2) { 
            v = s;
            s = s->Link;
        }
        if (s != NULL) { 
            //找到了
            if (v == NULL) { 
                //找到的是第一个结点
                g->NodeTable[p1].adj = s->Link;
            }else{ 
                v->Link = s->Link;
            }
            free(s);
        }else{ 
            printf("要删除的边不存在\n");
            return;
        }
        
        s = g->NodeTable[p2].adj;
        v = NULL;
        while (s != NULL && s->dest != p1) { 
            v = s;
            s = s->Link;
        }
        if (s != NULL) { 
            //找到了
            if (v == NULL) { 
                //找到的是第一个结点
                g->NodeTable[p2].adj = s->Link;
            }else{ 
                v->Link = s->Link;
            }
            free(s);
        }
    }
    
    //摧毁
    void DestroyGraph(GraphLnk *g){ 
        
        //释放结点
        Edge *p;
        for (int i = 0; i < g->NumVertices; i++) { 
            p = g->NodeTable[i].adj;
            while (p != NULL) { 
                g->NodeTable[i].adj = p->Link;
                free(p);
                p = g->NodeTable[i].adj;
            }
        }
        
        //释放结构表
        free(g->NodeTable);
        g->NodeTable = NULL;
        g->MaxVertices = g->NumEdges = g->NumVertices = 0;
    }
    
    //获取第一个邻接顶点
    int GetFirstNeighbor(GraphLnk *g,T vertex){ 
        int v = GetVertexPos(g, vertex);
        if (v == -1) { 
            return -1;
        }
        Edge *p = g->NodeTable[v].adj;
        return p == NULL ? -1 : p->dest;
    }
    //获取下一个邻接顶点
    int GetNextNeighbor(GraphLnk *g,T vertex1,T vertex2){ 
        int v1 = GetVertexPos(g, vertex1);
        int v2 = GetVertexPos(g, vertex2);
        if (v1 == -1 || v2 == -1) { 
            return -1;
        }
        Edge *p = g->NodeTable[v1].adj;
        while (p != NULL && p->dest != v2) { 
            p = p->Link;
        }
        if (p != NULL && p->Link != NULL) { 
            return p->Link->dest;
        }
        return -1;
    }

#### Main.c ####

#include "GraphLnk.h"
    
    int main(int argc, const char * argv[]) { 
        GraphLnk gl;
        InitGraph(&gl);
        
        InsertVertex(&gl, 'A');
        InsertVertex(&gl, 'B');
        InsertVertex(&gl, 'C');
        InsertVertex(&gl, 'D');
        InsertVertex(&gl, 'E');
        
        InsertEdge(&gl, 'A', 'B');
        InsertEdge(&gl, 'A', 'D');
        InsertEdge(&gl, 'B', 'C');
        InsertEdge(&gl, 'B', 'E');
        InsertEdge(&gl, 'C', 'D');
        InsertEdge(&gl, 'C', 'E');
        
        ShowGraph(&gl);
        
        
        RemoveEdge(&gl, 'A', 'D');
        RemoveVertex(&gl, 'A');
        ShowGraph(&gl);
        
        int v = GetFirstNeighbor(&gl, 'A');
        printf("%d\n",v);
        
        int d = GetNextNeighbor(&gl, 'A', 'D');
        printf("%d\n",d);
        
        DestroyGraph(&gl);
        
        return 0;
    }

[img_1]: /images/20230209/34c55935034f4c3b837e4c231ede483a.png