二.邻接矩阵法

可切换有向图/无向图

邻接矩阵演示
逻辑结构 (可拖拽)
A
B
C
D
A
B
C
D
A
0
1
1
0
B
0
0
1
0
C
0
0
0
1
D
1
0
0
0

1.图的存储--邻接矩阵法

#define MaxVertexNum 100      //顶点数目的最大值
typedef struct {
    char Vex[MaxVertexNum];   //顶点表
    int Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵,边表
    int vexnum, arcnum;    //图的当前顶点数和边数,弧数
};

第i个结点的度 = 第i行（或第i列）的非零元素个数第i个结点的出度 = 第i行的非零元素个数第i个结点的入度 = 第i列的非零元素个数第i个结点的度 = 第i行、第i列的非零元素个数之和

邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O(|V|)

2.邻接矩阵法存储带权图(网)

#define MaxVertexNum 100     // 顶点数目的最大值
#define INFINITY 最大的int值     // 宏定义常量“无穷”
typedef char VertexType;        // 顶点的数据类型
typedef int EdgeType;       // 带权图中边上权值的数据类型
typedef struct {
    VertexType Vex[MaxVertexNum];          // 顶点
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 边的权
    int vexnum, arcnum;                    // 图的当前顶点数和弧数
} MGraph;