数据结构与算法-图的存储

1. 邻接矩阵(顺序)

核心：

• 二维数组
• 顶点数
• 边数
• 对角线对称

1.1 结构

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITYC 0

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义  */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct {
    VertexType vexs[MAXVEX]; /* 顶点表 */
    EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
    int numVertices, numEdges; /* 图中当前的顶点数和边数  */
} MGraph;

1.2 存储与遍历

void CreateMGraph(MGraph *G) {
    int i,j,w;
    printf("输入顶点数和边数:\n");
    scanf("%d %d", &G->numVertices, &G->numEdges); // 读入顶点数和边数，后续录入使用
    printf("顶点数: %d，边数: %d", G->numVertices, G->numEdges);
    
    // 录入顶点对应的字符
    for (i = 0; i < G->numVertices; i++) {
        getchar();
        scanf("%c", &G->vexs[i]);
    }
    
    // 初始化邻接矩阵
    for (i = 0; i < G->numVertices; i++) {
        for (j = 0; j < G->numVertices; j++) {
            G->arc[i][j] = INFINITY;
        }
    }
    
    // 根据边数录入边表信息
    for (i = 0; i < G->numEdges; i++) {
        printf("输入边(vi,vj)上的下标i,下标j,权w\n");
        scanf("%d %d %d", &i, &j, &w);
        G->arc[i][j] = w;
        G->arc[j][i] = w; // 如果为无向图，矩阵沿对角线对称
    }
}

void PrintGraph(MGraph G) {
    // 打印邻接表
    for (int i = 0; i < G.numVertices; i++) {
        printf("\n");
        for (int j = 0; j < G.numVertices; j++) {
            printf("%d ", G.arc[i][j]);
        }
    }
    printf("\n");
}

2. 邻接表(链式)

核心：

• 存储被指向顶点链表的一维顶点数组
• 顶点数组结点
• 被指向结点
• 采用头插法，根据输入与邻接矩阵存储顺序可能不同

2.1 结构

#define M 100
#define true 1
#define false 0

typedef int BOOL;
typedef char VertexType; /* 顶点类型应由用户定义  */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

typedef struct Node {   // 邻接表的节点
    int adj_vex_index;  // 被指向顶点的下标
    EdgeType data;      // 权重值
    struct Node * next; // 边指针
} EdgeNode;

typedef struct vNode {
    VertexType data;      // 顶点代表的字符
    EdgeNode *firstEdge;  // 第一个相连的顶点
} VertexNode;

typedef struct Graph {
    VertexNode adjList[M];  // 顶点数组
    int arc_num;      // 边的个数
    int node_num;     // 节点个数
    BOOL is_directed; // 是不是有向图
} Graph;

2.2 存储与遍历

void creatGraph(Graph *g) {
    int i,j,k;
    EdgeNode *p;
    
    // 1.顶点,边,是否有向
    printf("输入顶点数目,边数和有向？：\n");
    scanf("%d %d %d", &g->node_num, &g->arc_num, &g->is_directed);
    
    // 2.顶点表
    printf("输入顶点信息：\n"); 
    for (i = 0; i < g->node_num; i++) {
        getchar();
        scanf("%c", &g->adjList[i].data);
        g->adjList[i].firstEdge = NULL;
    }
    
    // 3.录入边信息
    printf("输入边信息：\n");
    for (k = 0; k < g->arc_num; k++){
        getchar();
        scanf("%d %d", &i, &j); // i->j
        p = (EdgeNode *)malloc(sizeof(EdgeNode)); // 新建一个节点
        if (!p) exit(OVERFLOW);
        p->adj_vex_index = j; // 被指向顶点的下标
        p->next = g->adjList[i].firstEdge; // 头插法插进去
        g->adjList[i].firstEdge = p; // 头结点变为新结点
        
        if (!g->is_directed) {// j->i
            p = (EdgeNode *)malloc(sizeof(EdgeNode)); // 新建一个节点
            if (!p) exit(OVERFLOW);
            p->adj_vex_index = i; // 被指向顶点的下标
            p->next = g->adjList[j].firstEdge; // 头插法插进去
            g->adjList[j].firstEdge = p; // 头结点变为新结点
        }
    }
}

void PrintGraph(Graph g) {
    printf("邻接表中存储信息:\n");
    // 顶点数组索引遍历，每个数组元素里面是链表遍历
    for (int i = 0; i < g.node_num; i++) {
        EdgeNode * p = g.adjList[i].firstEdge;
        while (p) {
            printf("%c->%c ", g.adjList[i].data, g.adjList[p->adj_vex_index].data);
            p = p->next;
        }
        printf("\n");
    }
}