【C语言数据结构】图-邻接矩阵法

朱雀 2024-02-22 09:06 103阅读 0赞

--------------------

#### 图-邻接矩阵法 ####

*  代码实现

--------------------

## 代码实现 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    //定义最大顶点数为100，也就是这个图里最多有100个顶点
    #define MaxVertexNum 100
    
    //给顶点类型设置为char(其实本质是给char取了个别名叫VertexType)，也就是说顶点为'A'点，'B'点等。
    typedef char VertexType;
    
    //同理，给边的类型设置为int，其实对于邻接矩阵法来说，边为1代表有连接，边为0代表无连接。
    typedef int EdgeType;
    
    typedef struct {
        
        //建立一个一维数组，存储对应的顶点，也就是G=(V,E)中的V
        VertexType Vertex[MaxVertexNum];
    
        //建立一个二维数组，存储对应的边的集合，也就是G=(V,E)中的E
        EdgeType Edge[MaxVertexNum][MaxVertexNum];
    
        //定义顶点的数量和边的数量(英文中arc有弧的意思，这里指边)
        int vexnum, arcnum;
    } MGraph;
    
    void FindVertex(MGraph *G, VertexType x, VertexType y, int *index_x, int *index_y);
    
    //初始化邻接矩阵的图
    void InitGraph(MGraph *G) {
        
        G->vexnum = 0;
        G->arcnum = 0;
    }
    
    //添加顶点
    bool InsertVertex(MGraph *G, VertexType vertex) {
        
        //如果顶点已满,添加失败
        if (G->vexnum >= MaxVertexNum)
            return false;
    
        G->Vertex[G->vexnum] = vertex;
        G->vexnum++;
        return true;
    }
    
    //判断是否有边(x,y)或<x,y>
    void FindVertex(MGraph *G, VertexType x, VertexType y, int *index_x, int *index_y) {
        
        (*index_x) = -1;
        (*index_y) = -1;//定义x顶点和y顶点的索引
    //遍历赋值,找出x和y的索引
        for (int i = 0; i < (*G).vexnum; i++) {
        
            if ((*G).Vertex[i] == x)
                (*index_x) = i;
            else if ((*G).Vertex[i] == y)
                (*index_y) = i;
            if ((*index_x) != -1 && (*index_y) != -1)
                break;
        }
    }
    
    bool Adjacent(MGraph G, VertexType x, VertexType y) {
        
        int index_x;
        int index_y;
        FindVertex(&G, x, y, &index_x, &index_y);
    
        //如果有索引未找到，那么就说明不存在边(或者说其中某个点不存在)
        if (index_x == -1 || index_y == -1)
            return false;
    
        //如果有边，那么edge就为1
        return G.Edge[index_x][index_y] == 1;
    }
    
    /*懒得写了，就简单的写一下构建图有关的函数就行了，以下函数先欠着，有时间再写:
        Neighbors(G,x)
        InsertVertex(G,x)
        DeleteVertex(G,x)
        AddEdge(G,x,y)
        RemoveEdge(G,x,y)
        FirstNeighbor(G,x)
        NextNeighbor(G,x,y)
        Get_edge_value(G,x,y)
        Set_edge_value(G,x,y,v)
    */
    
    //创建边(无向图)
    bool AddEdgeU(MGraph *G, VertexType x, VertexType y) {
        
        //先判断顶点是否存在
        int index_x;
        int index_y;
        FindVertex(G, x, y, &index_x, &index_y);
        //如果有索引未找到，那么就说明不存在某个顶点
        if (index_x == -1 || index_y == -1)
            return false;
    
        G->Edge[index_x][index_y] = 1;
        G->Edge[index_y][index_x] = 1;
    
        return true;
    }
    
    //创建边(有向图)
    bool AddEdgeD(MGraph *G, VertexType x, VertexType y) {
        
        //先判断顶点是否存在
        int index_x;
        int index_y;
        FindVertex(G, x, y, &index_x, &index_y);
        //如果有索引未找到，那么就说明不存在某个顶点
        if (index_x == -1 || index_y == -1)
            return false;
    
        G->Edge[index_x][index_y] = 1;
        return true;
    }
    
    //打印矩阵
    bool PrintGraph(MGraph G) {
        
        printf("\t");
        for(int i = 0;i<G.vexnum;i++)
            printf("%c\t",G.Vertex[i]);
        printf("\n");
        for (int i = 0; i < G.vexnum; i++) {
        
            printf("%c\t",G.Vertex[i]);
            for (int j = 0; j < G.vexnum; j++)
                printf("%d\t", G.Edge[i][j]);
            printf("\n");
        }
    }
    
    int main() {
        
        //创建图
        MGraph G;
        //初始化图
        InitGraph(&G);
    
        //插入顶点
        InsertVertex(&G, 'A');
        InsertVertex(&G, 'B');
        InsertVertex(&G, 'C');
        InsertVertex(&G, 'D');
        InsertVertex(&G, 'E');
    
        //插入边
        AddEdgeU(&G, 'A', 'B');
        AddEdgeU(&G, 'A', 'C');
        AddEdgeU(&G, 'B', 'D');
        AddEdgeU(&G, 'C', 'D');
        AddEdgeU(&G, 'C', 'E');
        AddEdgeU(&G, 'D', 'E');
    
        //打印图邻接矩阵
        PrintGraph(G);
    
        //判断是否存在A-B边
        if(!Adjacent(G,'A','B'))
            printf("不存在A-B边！\n");
        else{
        
            printf("存在A-B边！\n");
        }
    
        return 0;
    }