图（一）-------基础知识

悠悠 2022-05-24 00:10 235阅读 0赞

刚刚结束了二叉树的学习。最近一段时间在研究关于图的一些知识。并用java代码对这些一本基本操作进行了实现。

图和二叉树一样都是非线性的数据结构，但是我们内存空间的地址是连续的，所以对于非线性问题的分析我们需要将他们转化为线性问题进行分析。

![70][]

如图所示，其中所有的V1，V2....通常都是顶点。例如G1图中，V4指向V1表示从V4到V1的一条弧。称V4为弧尾（Tail），V1为弧头（Head）在G2图中V1和V4之间的连接成为一条边。这两个图中G1称为有序图，G2称为无序图。其中v1称为v4的邻接点

在一个无序图中，有n个顶点，边的最大数目是1/2n（n-1）。具有1/2n（n-1）条边的无向图称为完全图。

对于有向图，同样有n个顶点，那么它的弧的最大数目是n(n-1)。称具有n(n-1)条弧的有向图为完全有向图。

在有向图中，对于任意两个顶点之间都存在弧连接，将这个图称为强连通图。

介绍完图的一些基本知识，我们来深入了解一下图。我们知道，任意两个结点之间都是相连的，我们将这两个结点的弧（或者边）上的数值称为这两个顶点之间的权值。所谓图的存储结构，就是由顶点和顶点之间的权值构成的。

那么我们可以用一个二维数组来表示整个图。

下面我将用我的java代码来实现一个图

private int vertexSize;// 顶点数量
    	private int[][] matrix;// 邻接矩阵
    	private final int MAX_WEIGHT = 9999;// 表示两个顶点之间不存在指向关系时的常量值

根据这几个变量（常量）我来进行解释。vertexSize表示顶点的数量，matrix表示一个邻接矩阵。其中存储的是两个顶点之间的权值。

public void init() {
    		int[] a1 = { 0, MAX_WEIGHT, 9, 2, 4 };
    		int[] a2 = { MAX_WEIGHT, 0, 4, 5, MAX_WEIGHT };
    		int[] a3 = { 9, 4, 0, MAX_WEIGHT, 7 };
    		int[] a4 = { 2, 5, MAX_WEIGHT, 0, 4 };
    		int[] a5 = { 4, MAX_WEIGHT, 7, 4, 0 };
    		matrix[0] = a1;
    		matrix[1] = a2;
    		matrix[2] = a3;
    		matrix[3] = a4;
    		matrix[4] = a5;
    	}

这个init方法我创建了一个邻接矩阵，每一行都是每个顶点作为弧尾指向其他顶点的权值。如果为0说明和自己相连那么一定为0，如果为MAX\_WEIGHT。那就说明和该顶点并不相连。大家可以将这个图表示出来。每一列都是说明该顶点作为弧头有多少顶点指向它。

下面我来说一下关于图的基本的一些属性的查询。

在此之前我来解释两个概念，出度和入度。

什么是出度呢，我刚才说过，出度实际上就是一个顶点指向了多少个顶点，查询的方法就是从邻接矩阵的第i行中查找不为0和MAX\_WEIGHT的值即为i顶点的出度。

那么入度就和出度相反。有多少个顶点指向该顶点就叫做这个顶点的出度，查询的方法就是从邻接矩阵的第i列查找不为0和MAX\_WEIGHT的值即为i顶点的入度。

实现代码如下

/**
    	 * 获取某一个点的出度。 出度：一个顶点作为弧尾指向其他顶点的弧的数目 出度的求法，二维矩阵以行为主，求这一行中所有的不为0或-1的值的数目
    	 * 
    	 * @param index
    	 * @return
    	 */
    	public int getOutDegree(int index) {
    		int count = 0;
    		for (int i = 0; i < vertexSize; i++) {
    			if (matrix[index][i] != 0 && matrix[index][i] != MAX_WEIGHT) {
    				count++;
    			}
    		}
    		return count;
    	}
    
    	/**
    	 * 获取一个顶点的入度 入度：一个顶点作为弧头，指向该弧头的所有弧的数目叫做这个顶点的入度。 入度的求法：求index所在列的不为0或者-1的值的数目
    	 * 
    	 * @param index
    	 * @return
    	 */
    	public int getInDegree(int index) {
    		int count = 0;
    		for (int i = 0; i < vertexSize; i++) {
    			if (matrix[i][index] != 0 && matrix[i][index] != MAX_WEIGHT) {
    				count++;
    			}
    		}
    		return count;
    	}

同样我们可以查询两个顶点的权值，当然这个图我是以无向图为例的，如果是有向图也是类似的。首先我们要规定好弧尾和弧头，将这两个参数传入邻接矩阵，查找对应二维数组的值即可。

/**
    	 * 获取两个顶点之间的权值，注意要按照弧头(head)和弧尾(tail)的顺序输入
    	 * 
    	 * @param tail
    	 * @param head
    	 * @return
    	 */
    	public int getWeight(int tail, int head) {
    		return matrix[tail][head];
    	}

这些都是关于图的基本概念和一些简单的方法的实现，下一次我将会说关于图的深度优先遍历算法和图的广度优先遍历算法。

[70]: /images/20220524/e8981a05b9074403940c50bd2091e270.png