一丶图的相关概念

图是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为G<V,E>,其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

1丶顶点

顶点：线性表中我们把数据元素叫做元素，树中将数据元素称为结点，在图中数据元素称之为顶点。

线性表中相邻的的元素具有线性关系，可以没有元素，称为空表。树中相邻两层的结点具有层次关系，可以没有结点，称为空树。在图中，任意两个顶点之间都有可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

2丶无向图

2-1丶无向边

无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边。

2-2丶无向图

如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。

无向图

2-3丶完全无向图

在无向图中，如果任意两个顶点都存在边，则称该图为完全无向图。

完全无向图

3丶有向图

3-1丶有向边

有向边：若顶点Vi到Vj之间的边有方向，则称这条边为有向边，也称为弧。Vi称为弧尾，Vj为弧头。

3-2丶有向图

如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。

有向图

3-3丶完全有向图

在有向图中，如果任意两个顶点都存在方向相反的两条有向边，则称该图为完全有向图。

完全有向图

二丶图的基础知识

1丶图的权

有些图的边或弧具有与它相关的的数字，这种与图相关的边或者弧相关的数叫做权。

图片.png

2丶连通图

在无向图G中，如果从顶点V1到V2有路径，则称V1和V2是连通的。如果对于图中任意两个顶点V1,V1和V2都是连通的，则称G是连通图。

图片.png

3丶度

无向图顶点的边数叫做度。
有向图顶点的边数叫做出度和入度。

4丶图的存储结构

也正是由于图的结构比较复杂，任意两个顶点之间都有可能存在联系，因此无法以数据元素在内存的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。

图片.png

5丶邻接矩阵

考虑到图是有顶点和边(或弧)两部分组成，合在一起比较困难，那就很自然的考虑到分两个结构来分别存储。顶点不分大小，主次，所以用一个一维数组来存储是很不错的选择。而边(或弧)由于是顶点和顶点之间的关系，一维数组搞不定，那就考虑用一个二维数组来存储。于是就可以采用邻接矩阵的方案。

图的邻接矩阵存储方式是用两个数组来表示图，一个一维数组来存储图中顶点信息，一个二维数组(称为邻接矩阵)来表示图中边(或弧)的信息。如下图所示

图片.png 图片.png 图片.png

6丶邻接表

我们可以将顶点存入数组，并对顶点的孩子进行链式存储，这种数组和链表相结合的存储方式称之为邻接表。

无向图的邻接表

图片.png

有向图的邻接表

图片.png

带权邻接表

图片.png

三丶图的遍历

图的遍历是和树的遍历类似，我们希望从图中某一个顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程叫做图的遍历。

深度优先遍历(Depth_First_Search)，也称深度优先搜索，简称DFS。

从图中某个顶点V出发，访问此顶点，然后从V的未被访问的邻接点出发深度优先图，直至图中所有和V有路径相通的顶点都被访问到。

图片.png

package com.cehae.graphMatrix;
/**
 * 深度优先搜索
 * @author Cehae
 */
public class GraphDFS {
    
    public void DFSraverse(graph gh){
        
        //初始化visited数组，用  false 以表示该顶点是否已经访问过
        boolean[] visited = new boolean[gh.numVexs];
        for(int i = 0; i < gh.numVexs; i++){
            visited[i] = false;
        }
        System.out.println();
        for(int i = 0; i < gh.numVexs; i++){
            if(!visited[i])
                DFS(gh,i,visited);
        }
    }
 
    private void DFS(graph gh, int k,boolean[] vi) {
        // TODO Auto-generated method stub
    
        vi[k] = true;
        System.out.println("正访问的结点是 ： " + gh.vexs[k]);
        
        for(int i = 0; i < gh.numVexs; i++){
            if(gh.arc[k][i] == 1 && !vi[i])
                DFS(gh,i,vi);
        }
    }   
}

广度优先遍历(Breadth First Search)，也称深度优先搜索，简称BFS。

广度优先遍历是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。

package com.cehae.graphMatrix;
 
import java.util.LinkedList;
import java.util.Queue;
 
/**
 * 广度优先搜索
 * @author Cehae
 */
public class GraphBFS {
    
    public void BFSraverse(graph gh){
        
        Queue<Integer> que =  new LinkedList<Integer>();
        boolean[] visited = new boolean[gh.numVexs];
        for(int i = 0; i < gh.numVexs; i++)
            visited[i] = false;
        
        for(int i = 0; i < gh.numVexs; i++){
            
            if(!visited[i]){
                
                visited[i] = true;
                System.out.println("正在访问的节点是 ：" + gh.vexs[i]);
                que.add(i);
                
                while(!que.isEmpty()){
                    que.remove();
                    
                    for(int j = 0; j <gh.numVexs; j++){
                        
                        if(gh.arc[i][j] == 1 && !visited[j]){
                            visited[j] = true;
                            System.out.println("正在访问的节点是 ：" + gh.vexs[j]);
                            que.add(j);
                        }
                    }
                }
            }
        }   
    }
}

最小生成树

一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。我们把构造连通网的最小代价生成树。称为最小生成树。寻找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法。

普里姆算法

package com.cehae.graphMatrix;

import java.util.LinkedList;

/**
 * 求最小生成树 Prim 普里姆算法 
 * @author Cehae
 */
public class GraphPrim {

    private int VertexSize;// 顶点数量

    private int[] vertexs;// 顶点数组

    private int[][] matrix;

    private boolean[] isVisited;

    private static final int MAX_WEIGHT = 1000;

    public GraphPrim(int vertexsize) {
        this.VertexSize = vertexsize;

        this.vertexs = new int[vertexsize];
        for (int i = 0; i < vertexsize; i++) {
            this.vertexs[i] = i;
        }

        this.matrix = new int[vertexsize][vertexsize];

        this.isVisited = new boolean[vertexsize];
    }

    public int[] getVertexs() {
        return vertexs;
    }

    public void setVertexs(int[] vertexs) {
        this.vertexs = vertexs;
    }

    public static void main(String[] args) {

        GraphPrim graph = new GraphPrim(9);

        int[] b1 = new int[] { 0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
        int[] b2 = new int[] { 10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12 };
        int[] b3 = new int[] { MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8 };
        int[] b4 = new int[] { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, MAX_WEIGHT, 16, 21 };
        int[] b5 = new int[] { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT };
        int[] b6 = new int[] { 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT };
        int[] b7 = new int[] { MAX_WEIGHT, 16, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT };
        int[] b8 = new int[] { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT };
        int[] b9 = new int[] { MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0 };

        int[][] bs = { b1, b2, b3, b4, b5, b6, b7, b8, b9 };

        for (int i = 0; i < bs.length; i++) {
            graph.matrix[i] = bs[i];
        }

        graph.prim();
    }


    // 详细解释和调试
    // prim 普里姆算法
    public void prim() {

        int[] lowcost = new int[VertexSize]; // 最小权值顶点权值的数组，为0表示已经获取最小权值
        int[] adjvex = new int[VertexSize]; // 最小权值顶点的数组

        // 最小权值的和
        int sum = 0;

        // 先将第一行的数据（除去第一个）存放到权值数组中
        for (int i = 1; i < VertexSize; i++) {
            lowcost[i] = matrix[0][i];
        }

        for (int i = 1; i < VertexSize; i++) {

            System.out.println("第" + i + "轮合并前");
            System.out.println("最小顶点数组：");
            for (int j : adjvex) {
                System.out.println(j);
            }
            System.out.println("最小权值数组：");
            for (int j : lowcost) {
                System.out.println(j);
            }

            int min = MAX_WEIGHT;// 最小权值
            int minId = 0;// 最小权值下标

            // 求出本行数组最小的权值和下标
            for (int j = 1; j < VertexSize; j++) {
                if (lowcost[j] < min && lowcost[j] > 0) {
                    min = lowcost[j];
                    minId = j;
                }
            }

            // 已经找到本行最小的权值和下标
            System.out.println("顶点：" + minId + " 权值：" + min);
            lowcost[minId] = 0;// 将最小权值下标里的权值设置为0，相当于一个标记，为0 代表已经找到最小权值

            // 然后遍历 最小下标所在行对应的数组1 和 最小权值数组2，两个数组进行比较，
            // 将对应位置最小的权值放入数组2，同时将最小权值下标放入最小权值数组
            int[] minIdArr = matrix[minId];

            System.out.println("找到要合并的数组:");
            for (int j : minIdArr) {
                System.out.println(j);
            }

            for (int j = 1; j < VertexSize; j++) {
                if (lowcost[j] != 0 && minIdArr[j] < lowcost[j]) {
                    lowcost[j] = minIdArr[j];
                    adjvex[j] = minId;
                }
            }
            sum += min;// 累加权值

            System.out.println("第" + i + "合并后");
            System.out.println("最小顶点数组：");
            for (int j : adjvex) {
                System.out.println(j);
            }
            System.out.println("最小权值数组：");
            for (int j : lowcost) {
                System.out.println(j);
            }

            System.out.println();
            System.out.println();
            System.out.println();
        }

        System.out.println("最小生成树权值和为:" + sum);

        System.out.println("最后合并后");
        System.out.println("最小顶点数组：");
        for (int j : adjvex) {
            System.out.println(j);
        }
        System.out.println("最小权值数组：");
        for (int j : lowcost) {
            System.out.println(j);
        }
    }
}

克鲁斯卡尔算法

package com.cehae.graphMatrix;

/**
 * 求最小生成树 Kruskal 克鲁斯卡尔算法 
 * @author Cehae
 */
public class GraphKruskal {

    class Edge {// 边对象

        private int begin;// 开始
        private int end;// 结束
        private int weight;// 权值

        public Edge(int begin, int end, int weight) {
            super();
            this.begin = begin;
            this.end = end;
            this.weight = weight;
        }

        public int getBegin() {
            return begin;
        }

        public void setBegin(int begin) {
            this.begin = begin;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }

    private Edge[] edges;// 边的数组
    private int edgeSize;// 边的数量

    public GraphKruskal(int edgeSize) {
        super();
        this.edgeSize = edgeSize;
        this.edges = new Edge[edgeSize];
    }

    public void createEdgeArray() {

        // 起顶点，终顶点，权值
        edges[0] = new Edge(4, 7, 7);
        edges[1] = new Edge(2, 8, 8);

        edges[2] = new Edge(0, 1, 10);
        edges[3] = new Edge(0, 5, 11);

        edges[4] = new Edge(1, 8, 12);
        edges[5] = new Edge(3, 7, 16);

        edges[6] = new Edge(1, 6, 16);
        edges[7] = new Edge(5, 6, 17);

        edges[8] = new Edge(1, 2, 18);
        edges[9] = new Edge(6, 7, 19);

        edges[10] = new Edge(3, 4, 20);
        edges[11] = new Edge(3, 8, 21);

        edges[12] = new Edge(2, 3, 22);
        edges[13] = new Edge(3, 6, 24);

        edges[14] = new Edge(4, 5, 26);
    }

    public static void main(String[] args) {

        GraphKruskal g = new GraphKruskal(15);

        g.createEdgeArray();

        g.miniSpanTreeKruskal();
    }

    public void miniSpanTreeKruskal() {

        int m, n, sum = 0;

        // 这个数组很关键，是克鲁斯卡尔算法的关键所在，次数组中 a[4]=7,代表一条起点为4终点为7的边
        // 神奇数组下标为起点，值为终点
        int[] parent = new int[edgeSize];
        for (int i = 0; i < edgeSize; i++) {
            parent[i] = 0;
        }

        for (int i = 0; i < edgeSize; i++) {
            n = find(parent, edges[i].begin);
            m = find(parent, edges[i].end);

            if (n != m) {
                parent[n] = m;
                System.out.println("起始顶点：" + edges[i].begin + "---结束顶点" + edges[i].end + "--权值：" + edges[i].weight);
                sum += edges[i].weight;
            }
        }

        System.out.println("最小权值为：" + sum);
    }

    /**
     *
     * 对神奇数组进行查询获取非回环的值
     * 
     * parent 神奇数组
     * 
     * f 为顶点
     * 
     * 核心方法
     * 
     * @auther Cehae
     */
    private int find(int[] parent, int f) {
        while (parent[f] > 0) {
            f = parent[f];// 为什么会跳出循环，注意改变了下标
        }
        return f;
    }
}