连通图 连通分支或者连通分量 对无向图G=(v,E)而言,如 无向图的最大连通子图 果从V1到V2有一条路径(从V2 ■强连通分支(强连通分量) 到V1也一定有一条路径),则称 V1和v2是连通的 (connected) ■强连通 网络 自由树( free tree) 带权的连通图 ■不带有简单回路的无向图,它是 连通的,并且具有V|-1条边 15 亡 权新有,轴彩光 回 62图的抽象数据类型 结点、边怎么表示? class Graph /图的ADT public ■结点:增?、删、查?、改 int VerticesNumo;∥/返回图的顶点个数 int EdgesNum();//返回图的边教 ■边:增、删、查?、改 /返回与顶点 onevertex相关联的第一条边 Edge FirstEdge(int onevertex); /返回与边 PreEdge有相同关联顶点 one vertex的 /下一条边 Edge NextEdge(Edge preEdge); 值惠单3 北京大学信息学院 ©版权所有，转载或翻印必究 Page 13 连通图 „ 对无向图G=（V，E）而言，如 果从V1到V2有一条路径（从V2 到V1也一定有一条路径），则称 V1和V2是连通的 （connected） „ 强连通 北京大学信息学院 ©版权所有，转载或翻印必究 Page 14 连通分支或者连通分量 „ 无向图的最大连通子图 „ 强连通分支（强连通分量） v0 v5 北京大学信息学院 ©版权所有，转载或翻印必究 Page 15 网络 „ 带权的连通图 北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 自由树（free tree） „ 不带有简单回路的无向图，它是 连通的，并且具有|V|-1条边 北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 6.2 图的抽象数据类型 „ 结点、边怎么表示？ „ 结点：增？、删、查?、改 „ 边：增、删、查?、改 北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 class Graph{ //图的ADT public: int VerticesNum(); //返回图的顶点个数 int EdgesNum(); //返回图的边数 //返回与顶点oneVertex相关联的第一条边 Edge FirstEdge(int oneVertex); //返回与边PreEdge有相同关联顶点oneVertex的 //下一条边 Edge NextEdge(Edge preEdge);