Java数据结构之图

谁借莪１个温暖的怀抱￠ 2022-02-01 11:11 270阅读 0赞

# 基本概念 #

图是一种数据元素间具有“多对多”关系的非线性数据结构，由顶点集V和边集E组成，记作G=(V,E)。

1.  无向边 e=(u,v)：表示顶点u到顶点v的一条无向边，简称边，其中(u,v)=(v,u)。
2.  有向边 e=<u,v>：表示顶点u到顶点v的一条有向边，也叫弧，其中u叫始点或弧尾，v叫终点或弧头，<u,v>!=<v,u>。
3.  零图：指E为空集的图，即图中只有顶点，没有边。
4.  无向图：全部由无向边构成的图。
5.  有向图：全部由有向边构成的图。
6.  完全图：边数达到最大值的图，即在顶点为n的无向图中，边数为n(n-1)/2；在顶点为n的有向图中，边数为n(n-1)。
7.  稠密图：边数较少的图，如e<nlog2n，反之则为稀疏图。
8.  子图：设有两个图G=(V,E)和G’=( V ',E’)，如有 V '是V的子集，E’是E的子集，则成G’是G的子图。
9.  生成子图：设有两个图G=(V,E)和G’=( V ',E’)，如有 V '=V，则成G’为G的生成子图。
10. 邻接点：在一个图中，若存在边 (u,v)（或弧<u,v>），则称边（或弧）为顶点u，v关联的边（或弧），顶点u，v为邻接点。
11. 顶点的度：指与顶点关联的边数，记作D(u)。指向顶点边数的个数，称为入度，记作ID(u)；从顶点指出边的个数，称作出度，记作OD(u)。全部顶点的度之和为边数的两倍。
12. 路径：从顶点u到顶点v所经过的顶点序列，没有顶点重复出现的路径叫做初等路径。
13. 回路：第一个和最后一个顶点相同的路径称作回路或环。除了第一个顶点和最后一个顶点外，其他顶点都不重复的回路叫初等回路。
14. 连通图：在无向图中，若顶点v和顶点u之间有路径，则成u和v是连通的。任意两个顶点都连通的图称为连通图。
15. 连通分量：无向图中的极大连通子图。
16. 强连通图：有向图中任意两个分量均连通的图称为强连通图。
17. 强连通分量：有向图中的极大连通子图。
18. 生成树：包含图中全部n个顶点和n-1条边的生成子图。
19. 网：边上带有权值的图。

# 图的抽象数据类 #

package cho6;
    
    public interface IGraph {
    	public void createGraph();// 创建图
    
    	public int getVNum();// 返回图中顶点数
    
    	public int getENum();// 返回图中边数
    
    	public Object getVex(int i);// 返回位置i的顶点数
    
    	public int locateVex(Object x);// 返回值为x的顶点位置
    
    	public int firstAdj(int i) throws Exception;// 返回结点的第一个邻接点
    
    	public int nextAdj(int i, int j);// 返回相对于j的下一个邻接点
    }