图的存储–邻接矩阵法

邻接矩阵存储带权图

邻接矩阵性能分析

回顾：对称矩阵的压缩

邻接矩阵法的性质

总结

代码实现

#include <stdio.h>
#include <stdlib.h>
#define INFINITY 65535 //极大值
#define MAXVEX 100      //最大定点数

typedef char VertexType;    //假设顶点类型为字符型
typedef int  EdgeType;      //假设边的类型为整形

typedef struct {
    VertexType vexs[MAXVEX];        //顶点表
    EdgeType arc[MAXVEX][MAXVEX];   //邻接矩阵
    int numVertexes,numEdges;       //当前图中实际的顶点数和边数
}GraphMatrix;

//利用邻接矩阵表示法，创建无向网(无向有权图）
void CreateGraphMatrix(GraphMatrix* G){
    int i,j,k,w;        //w用于接收权重，i，j，k用于遍历

    printf("请输入顶点数和边数:\n");
    scanf("%d%d",&G->numVertexes,&G->numEdges);
    getchar();
    printf("请输入每个顶点的数据:\n");
    for(i = 0;i < G->numVertexes;i ++)scanf("%c",&G->vexs[i]);

    for(i = 0;i < G->numVertexes;i ++)          //初始化邻接矩阵
        for(j = 0;j < G->numVertexes;j ++){
            G->arc[i][j] = INFINITY;
        }

    for(k = 0;k < G->numEdges;k ++){
        printf("请输入point1、point2及他们之间的权重:\n");
        scanf("%d%d%d",&i,&j,&w);
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];
    }
}

//有向有权图
void Creat_AMGraph_weightd(GraphMatrix* G){
    int i,j,k,w;
    printf("请输入顶点数和边数:\n");
    scanf("%d%d",&G->numVertexes,&G->numEdges);
    getchar();
    printf("请输入每个顶点的数据:\n");
    for(i = 0;i < G->numVertexes;i ++)
    scanf("%c",&G->vexs[i]);
    for(i = 0;i < G->numVertexes;i ++){
        for(j = 0;j < G->numVertexes;j ++){
            G->arc[i][j] = 0;
        }
    }

}

int main() {
    GraphMatrix GM;
    printf("------邻接矩阵的【创建】------\n");
    CreateGraphMatrix(&GM);
    return 0;
}