.路径长度非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指路径 上各边的权值之和。 简单路径若路径上各顶点y1,y2,,ym均 不互相重复，则称这样的路径为简单路径。 回路 若路径上第一个顶点y,与最后一个 顶点ym重合，则称这样的路径为回路或环。 3 3 3 6
• 路径长度 非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指路径 上各边的权值之和。 • 简单路径 若路径上各顶点 v1 , v2 , ..., vm 均 不互相重复, 则称这样的路径为简单路径。 • 回路 若路径上第一个顶点 v1 与最后一个 顶点vm 重合, 则称这样的路径为回路或环。 6 0 1 2 3 0 1 2 3 0 1 2 3
连通图与连通分量？ 在无向图中，若从顶点到顶 点y2有路径，则称顶点与2是连通的。如果图中 任意一对顶点都是连通的，则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 强连通图与强连通分量 在有向图中，若对于每 一对顶点y和y,都存在一条从到y和从y到y的 路径，则称此图是强连通图。非强连通图的极大 强连通子图叫做强连通分量。 生成树(spanning tree) 一个无向连通图的生成树 是其极小连通子图，在个顶点的情形下，有 n-1条边。若是有向图，则可能得到它的由若干 有向树组成的生成森林
• 连通图与连通分量 在无向图中, 若从顶点v1到顶 点v2有路径, 则称顶点v1与v2是连通的。如果图中 任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 • 强连通图与强连通分量 在有向图中, 若对于每 一对顶点vi和vj , 都存在一条从vi到vj和从vj到vi的 路径, 则称此图是强连通图。非强连通图的极大 强连通子图叫做强连通分量。 • 生成树(spanning tree) 一个无向连通图的生成树 是其极小连通子图，在 n 个顶点的情形下，有 n-1 条边。若是有向图，则可能得到它的由若干 有向树组成的生成森林。 7
图的抽象数据类型 class Graph /对象：由一个非空顶点集合和一个边集合构成 /每条边由一个顶点对来表示。 public; GraphO); /建立一个空的图 void insert Vertex (const T&vertex); /插入一个顶点vertex,该顶点暂时没有入边 void insertEdge (int vl,int v2,int weight); /在图中插入一条边(V1,V2,w) yoid remove Vertex (int v); /在图中删除顶点V和所有关联到它的边 8
图的抽象数据类型 class Graph { //对象: 由一个非空顶点集合和一个边集合构成 //每条边由一个顶点对来表示。 public: Graph(); //建立一个空的图 void insertVertex (const T& vertex); //插入一个顶点vertex, 该顶点暂时没有入边 void insertEdge (int v1, int v2, int weight); //在图中插入一条边(v1, v2, w) void removeVertex (int v); //在图中删除顶点v和所有关联到它的边 8
void removeEdge (int v1,int v2); /在图中删去边(V1,V2) bool IsEmptyO; /若图中没有顶点，则返回tru,否则返回 false T getWeight (int v1,int v2); /函数返回边(V1,V2)的权值 int getFirstNeighbor (int v); /给出顶点V第一个邻接顶点的位置 int getNextNeighbor (int v,int w); /给出顶点V的某邻接顶点W的下一个邻 接顶点
void removeEdge (int v1, int v2); //在图中删去边(v1,v2) bool IsEmpty(); //若图中没有顶点, 则返回true, 否则返回 false T getWeight (int v1, int v2); //函数返回边(v1,v2) 的权值 int getFirstNeighbor (int v); //给出顶点v 第一个邻接顶点的位置 int getNextNeighbor (int v, int w); //给出顶点v 的某邻接顶点 w 的下一个邻 接顶点 }; 9
图的存储表示 图的模板基类 在模板类定义中的数据类 型参数表<class T,class E>中，T是顶点数 据的类型，E是边上所附数据的类型。 这个模板基类是按照最复杂的情况（即带 权无向图)来定义的，如果需要使用非带 权图，可将数据类型参数表<class T,class E>改为<class T>。 如果使用的是有向图，也可以对程序做相 应的改动。 10
图的存储表示 • 图的模板基类 在模板类定义中的数据类 型参数表 <class T, class E> 中，T是顶点数 据的类型，E是边上所附数据的类型。 • 这个模板基类是按照最复杂的情况（即带 权无向图）来定义的，如果需要使用非带 权图，可将数据类型参数表 <class T, class E> 改为 <class T>。 • 如果使用的是有向图，也可以对程序做相 应的改动。 10