顶点和边 顶点通过边邻接,边依附于顶点 不考虑顶点到自身有边的情况 n个顶点的有向图,最大边数为n(n-1) n个顶点的无向图,最大边数为n(n-1)/2 达到最大边数的图称为完全( complete)图,边数 接近完全的图称为稠密( dense)图,边数远小于完 全的图称为稀疏( sparse)图 每个顶点所关联的边的数目称为度( degree) 有向图中又分为入度( indegree)和出度( outdegree) 顶点的度和图的边数满足e=∑=1D(v) 2021/2/11 数据结构及其算法第7章图•顶点和边 •顶点通过边邻接，边依附于顶点 •不考虑顶点到自身有边的情况 • n个顶点的有向图，最大边数为n(n-1) • n个顶点的无向图，最大边数为n(n-1)/2 •达到最大边数的图称为完全(complete)图，边数 接近完全的图称为稠密(dense)图，边数远小于完 全的图称为稀疏(sparse)图 •每个顶点所关联的边的数目称为度(degree) • 有向图中又分为入度(indegree)和出度(outdegree) •顶点的度和图的边数满足𝑒 = 1 2 σ𝑖=1 𝑛 𝐷(𝑣𝑖 ) 2021/2/11 数据结构及其算法 第7章 图 7