🔄 图的转换

邻接矩阵定义

#define MAX_VERTERX_NUM 100
typedef char VertexType;
typedef int EdgeType;
typedef struct {
    VertexType vex[MAX_VERTERX_NUM];
    EdgeType arcs[MAX_VERTERX_NUM][MAX_VERTERX_NUM];
    int vexnum, arcnum;
} MGraph;

邻接表定义

#define MAX_VERTERX_NUM 100
typedef char VertexType;
typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;
typedef struct VNode{
    VertexType data;
    ArcNode *firstarc;
} VNode, AdjList[MAX_VERTERX_NUM];
typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

有向图的邻接表转邻接矩阵

void Convert(ALGraph G, MGraph &M) {
    M->vexnum = G.vexnum; //顶点数赋值
    M->arcnum = G.arcnum; //边数赋值
    ArcNode *p;
    for(int i=0; i<G.vexnum; i++) {//依次遍历各顶点表结点为头的边链表
        M->vex[i] = G.vertices[i].data; //顶点信息赋值
        for(p=G.vertices[i].firstarc; p; p=p->nextarc) {
            M->arcs[i][p->adjvex] = 1;
        }
    }
}

有向图的邻接矩阵转邻接表

void Convert(MGraph M, ALGraph &G) {
    G->vexnum = M.vexnum; //顶点数赋值
    G->arcnum = M.arcnum; //边数赋值
    ArcNode *p;
    for(int i=0; i<M.vexnum; i++) {
        G->vertices[i].data = M.vex[i]; //顶点信息赋值
        G->vertices[i].firstarc = NULL; //初始化firstarc指针
    }
    for(int i=0; i<M.vexnum; i++)
        for(int j=0; j<M.vexnum; j++)
            if(M.arcs[i][j]==1){
                p = new ArcNode;
                p->adjvex = j;
                p->nextarc = G->vertices[i].firstarc;
                G->vertices[i].firstarc = p;
            }
}