14、图-邻接矩阵

1、邻接矩阵的定义和初始化

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

#define Default_Vertices_Size 10
//顶点 
#define T char

//无向不带权的图 
typedef struct GraphMtx{
    int MaxVertices;//最大的顶点数 
    int NumVertices;//真实的顶点数
    int NumEdges;//边数 
    
    T *VerticesList;//存储点 
    int **Edge;//采用邻边矩阵[二维数组]存储边 
}GraphMtx; 

void InitGraph(GraphMtx* gm){
    gm->MaxVertices = Default_Vertices_Size;
    gm->NumVertices = 0;
    gm->NumEdges = 0;
    
    gm->VerticesList = (T*)malloc(sizeof(T) * gm->MaxVertices);
    assert(gm->VerticesList != NULL);
    //先开辟二级[行]指针
    gm->Edge = (int**)malloc(sizeof(int*) * gm->MaxVertices);
    //在开辟一级[列]指针
    int i = 0;
    for(i = 0;i < gm->MaxVertices;i++){
        gm->Edge[i] = (int*)malloc(sizeof(int) * gm->MaxVertices); 
    } 
    //对矩阵进行初始化
    for(i = 0;i < gm->MaxVertices;i++){
        int j;
        for(j = 0;j < gm->MaxVertices;j++){
            gm->Edge[i][j] = 0;
        }
    } 
}

2、增加顶点

//增加顶点 
void InsertVertex(GraphMtx* g,T v){
    if(g->NumVertices >= g->MaxVertices)
        return;
    g->VerticesList[g->NumVertices++] = v;
}

3、删除顶点

int GetVertexPos(GraphMtx* g,T key){
    int i = 0;
    for(i = 0;i < g->NumVertices;i++){
        if(g->VerticesList[i] == key)
            return i;
    } 
    return -1;
} 

//在v1 和 v2 之间插入边[注意是无向图]
void InsertEdge(GraphMtx* g,T v1,T v2){
    int p1 = GetVertexPos(g,v1);
    int p2= GetVertexPos(g,v2);
    //如果v1或者v2不合法 
    if(p1 == -1 || p2 == -1)
        return;
    if(g->Edge[p1][p2] != 0)    
        return;//说明边已存在 
    //无向图所以要对两个地方操作 
    g->Edge[p1][p2] = g->Edge[p2][p1] = 1;
    //总边数+1
    g->NumEdges++; 
} 

4、删除边

//删除v1 - v2的边[注意是无向图]
void RemoveEdge(GraphMtx* g,T v1,T v2){
    int p1 = GetVertexPos(g,v1);
    int p2= GetVertexPos(g,v2);
    //如果v1或者v2不合法 
    if(p1 == -1 || p2 == -1)
        return;
    if(g->Edge[p1][p2] == 0)    
        return;//说明边不存在 
    //无向图所以要对两个地方操作 
    g->Edge[p1][p2] = g->Edge[p2][p1] = 0;
    //总边数-1
    g->NumEdges--; 
} 

5、删除点

//删除点 
void RemoveVertex(GraphMtx* g,T v){
    int p1 = GetVertexPos(g,v);
    if(p1 == -1)
        return;
    int i = 0,j = 0;
    //V顶点的边数
    int numEdges = 0;
    for(i = 0;i < g->NumVertices;i++){
        if(g->Edge[i][p1] == 1)
            numEdges++;
        g->Edge[i][p1] = g->Edge[i][g->NumVertices - 1];
    }
    for(i = 0;i < g->NumVertices;i++){
        g->Edge[p1][i] = g->Edge[g->NumVertices - 1][i];
    }
    g->Edge[p1][p1] = 0;
    g->VerticesList[p1] = g->VerticesList[g->NumVertices - 1];
    g->NumVertices--;
    g->NumEdges -= numEdges;
} 

6、其他方法

void ShowGraph(GraphMtx* g){
    int i = 0,j = 0;
    printf("   ");
    for(i = 0;i < g->NumVertices;i++)
        printf("%c  ",g->VerticesList[i]);
    printf("\n");
    for(i = 0;i < g->NumVertices;i++){
        printf("%c",g->VerticesList[i]);
        for(j = 0;j < g->NumVertices;j++){
            printf("  %d",g->Edge[i][j]);
        }
        printf("\n");
    }
    printf("Edeges=%d\n",g->NumEdges);
}

void destroy(GraphMtx* g){
    free(g->VerticesList);
    g->VerticesList = NULL;
    int i = 0;
    for(i = 0;i < g->NumVertices;i++){
        free(g->Edge[i]);
    }
    free(g->Edge);
    g->Edge = NULL;
}

int GetFirstNeighbor(GraphMtx* g,T v){
    int p = GetVertexPos(g,v);
    if(p == -1)    return -1;
    int i = 0;
    for(i = 0;i < g->NumVertices;i++){
        if(g->Edge[p][i] == 1)
            return i;
    }
    return -1;
}

int GetNextNeighbor(GraphMtx* g,T v,T w){
    int pv = GetVertexPos(g,v);
    int pw = GetVertexPos(g,w);
    if(pv == -1 || pw == -1) return -1;
    int i = 0;
    for(i = pw;i < g->NumVertices;i++){
        if(g->Edge[pv][i] == 1)
            return i;
    }
    return -1;
}
int main(){
    GraphMtx gm;
    InitGraph(&gm);
    InsertVertex(&gm,'A');
    InsertVertex(&gm,'B');
    InsertVertex(&gm,'C');
    InsertVertex(&gm,'D');
    InsertVertex(&gm,'E');
    
    InsertEdge(&gm,'A','B');
    InsertEdge(&gm,'A','D');
    InsertEdge(&gm,'B','C');
    InsertEdge(&gm,'C','D');
    InsertEdge(&gm,'C','E');
    ShowGraph(&gm);
    
    int p = GetNextNeighbor(&gm,'C','D');
    printf("GetNextNeighbor: %d",p);
    
    RemoveEdge(&gm,'B','C');
    ShowGraph(&gm);

    RemoveVertex(&gm,'B');
    ShowGraph(&gm);
    return 0;
}