网站网络营销推广,湖南网站建设网,网上书城网站开发的目的与意义,西宁网站建设加盟代理一#xff1a;定义 由顶点的集合和边的集合组成#xff1b;常以 G(V,E) 表示#xff0c;G 代表图#xff0c;V代表 顶点的集合#xff0c;E代表边的集合#xff1b;
如图#xff1a;
在G1图中#xff0c;有 0~4 五个顶点#xff0c;有 0-1#xff0c;0-2…
一定义 由顶点的集合和边的集合组成常以 G(V,E) 表示G 代表图V代表 顶点的集合E代表边的集合
如图
在G1图中有 0~4 五个顶点有 0-10-20-41-22-33-4 六条边
二分类
1有/无向图
我们根据 边是否有方向分为 有向图无向图
如图无向图中0可以到11也可以到00和1之间是等价的
无向图中0可以到1但是1不可以到0 2 带/不带权图
我们根据边是否有权重分为带权图不带权图
边的度量可以表示时间距离等具体的量如G3
当然边与边之间的度量可以是不同的如G4
三图的表示
1. 邻接矩阵
即使用二维数据来表示图。
1.1 不带权的邻接矩阵
1代表两顶点连通0代表不连通。某顶点带自身的边一般用0表示 不过也可以根据需要用 1 表示 1.2 带权的邻阶矩阵
顶点之间不连通常用 ∞ 来表示顶点到自身的边一般标记为 0 2.邻接表
使用顺序和链式相结合的方式存储图指针的连接代表相连与有向还是无向带权还是不带权无关 如果需要表示权值的话我们可以在节点中增加额外的数据域进行存储 四实际应用
实际应用时我们通常根据结点和边的个数来选择邻接矩阵或邻接表来表示图
1.稀疏图
边的条数远远小于顶点的个数EV的平方选择邻接表毕竟添加元素方便
2.稠密图
边的条数远远接近顶点的个数E 接近 V的平方选择邻接矩阵
3.特殊情况
比如我们要判断两个顶点之间是否连通需要采用邻接矩阵来表示图因为二维数组遍历的时间复杂度为O(1)这会提高找寻的效率
