[数据结构与算法]Day9：图的邻接矩阵C语言实现

1. 结构体定义

typedef struct {
    char *vex;
    int **arc;
    int vexNum, arcNum;
}MatrixGraph;

2. 初始化

void MatrixGraphInit(MatrixGraph *mg, int vexNum, char *vexs)
{
    mg->vexs = vexs;
    mg->vexNum = vexNum;
    mg->arcs = malloc(sizeof(int*) * vexNum);
    for(int i = 0;i < vexNum;i++){
        mg->arcs[i] = malloc(sizeof(int) * vexNum);
        memset(mg->arcs[i], 0, sizeof(int) * vexNum);
    }
    mg->arcNum = 0;
}

3. 定位结点的位置

int MatrixGraphLocateVex(MatrixGraph *mg, char vex)
{
    for(int i = 0;i < mg->vexNum;i++)
        if(vex == mg->vexs[i])
            return i;
    return -1;
}

4. 查找第一个邻接点

char MatrixGraphFirstAdjVex(MatrixGraph *mg, char vex)
{
    int vexNo = MatrixGraphLocateVex(mg, vex);
    if(vexNo < 0)
        return '\0';
    for(int i = 0;i < mg->vexNum;i++)
        if(mg->arcs[vexNo][i] > 0)
            return mg->vexs[i];
    return '\0';
}

5. 查找下一个邻接点

char MatrixGraphNextAdjVex(MatrixGraph *mg, char vex, char pre)
{
    int vexNo = MatrixGraphLocateVex(mg, vex);
    int start = MatrixGraphLocateVex(mg, pre);
    if(vexNo < 0 || start < 0)
        return '\0';
    for(int i = start + 1;i < mg->vexNum;i++)
        if(mg->arcs[vexNo][i] > 0)
            return mg->vexs[i];
    return '\0';
}

6. 插入弧

void MatrixGraphInserArc(MatrixGraph *mg, char vex1, char vex2)
{
    int vexNo1 = MatrixGraphLocateVex(mg, vex1);
    int vexNo2 = MatrixGraphLocateVex(mg, vex2);
    if(vexNo1 < 0 || vexNo2 < 0)
        return;
    mg->arcs[vexNo1][vexNo2] = 1;
    mg->arcs[vexNo2][vexNo1] = 1;
    mg->arcNum++;
}