在线建图编辑器

家庭作业

必做

• 图的入度和出度
• 图的表示-邻接矩阵练习
• 图论入门

提高

• 有向图or无向图
• 加几条边平衡

概念

一个图 graph（G），由定点集 vertex（V）和边集 edge（E）构成。每一条边就是一个顶点对（v, w）。如果边都是有方向的，称之为有向图；如果边都是无方向的，称为无向图。

术语

基本组成

• 点
• 边

分类

• 有向图
• 无向图

点的出度

• 有多少条边是以此点为起点

点的入度

• 有多少条边是以此点为终点

权重

• 一条边所对应的值

路径

• 两个顶点之间的走法

连通图

• 无向图中每个顶点之间都有条路径

强连通图

• 有向图中每个顶点之间均能直接相连的图

完全图

• 每个顶点之间均能直接相连的图

生成树

• 仅保留最小数量边的连通图

图的储存

矩阵表示法：利用二维数组的方式完成图的构建

int arr[1005][1005];
for (int i = 0; i < m; i++) {
        int a, b, w;  //边的起点、终点、权值
        cin >> a >> b;
        //无向图
        arr[a][b] = arr[b][a] = 1;
        //有向图
        // arr[a][b] = 1;
}

邻