数据结构系列六之图

一、图结构简介

    图是现实生活中很常见的一种形状，例如不同城市及城市之间的路径，我们可以用无向图模拟城市与路径，城市为图的顶点，城市之间的路径是图的边。图分为无向图、有向图，无向图由顶点和边构成，有向图由顶点和弧构成，有向图有出度和入度区分。图的实现方式比较简单，可以用数据结构邻接矩阵和邻接表实现。

二、图结构分析

1、邻接矩阵

A、B、C、D四个顶点，边集合{{A,B},{A,C},{A,D},{B,D},{C,D}}，有向图如下：

结构分析： 用数组存放图顶点；用二维数组存放图的边。二维数组值是0表示没有这条边，1表示有这条边，

在有向图中某个顶点的行有多少1表示该顶点的出度；矩阵中某个顶点的列有多少个1表示该顶点的入度。

2、邻接表

有向图用邻接矩阵，如下图：

结构分析：用数组存放自己封装顶点的结构，每个顶点的链表就是该顶点的边

在有向图中，某个顶点有多少个链表节点，就表示该节点的出度是多少

邻接矩阵相比于邻接表，占用空间少

三、图结构实现

1、邻接矩阵结构实现

二维数组表示图结构

package com.sf.bdp.chart;

/**
 * @Author:swcks
 * @Description:
 * @Date：create in 2018/6/24/024 13:45
 */
public class ArrayMatrix {
    private char[] ele;//存储图顶点
    private int[][] matrix;//存储图边
    private int size;

    public ArrayMatrix() {
    }
    //图构造
    public ArrayMatrix(char[] ele, char[][] matrix) {
        size = ele.length;
        this.ele = ele;
        this.matrix = new int[size][size];

        for(char[] temp:matrix){
            int firstPos = findIndex(temp[0]);
            int secondPos = findIndex(temp[1]);
            this.matrix[firstPos][secondPos] = 1;
//            this.matrix[secondPos][firstPos] = 1; //注释该句表示有向图
        }
    }

    private int findIndex(char c) {
        for (int i = 0; i < size; i++) {
            if(ele[i] == c){
                return i;
            }
        }
        return -1;
    }

    public void showMatrix(){
        for(int[] temp:matrix){
            for(int i=0;i<size;i++){
                System.out.print(temp[i]+" ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        char[] ele = {'A','B','C','D'};
        char[][] side = {
                {'A','B'},{'A','C'},{'A','D'},{'B','D'},{'C','D'}
        };
        ArrayMatrix arrayMatrix = new ArrayMatrix(ele,side);
        arrayMatrix.showMatrix();
    }
}

2、邻接表结构实现

邻接表使用线性数组和线性链表组合结构实现

package com.sf.bdp.chart;

/**
 * @Author:swcks
 * @Description:
 * @Date：create in 2018/6/24/024 14:17
 */
public class LinkTable {
    private int size;
    private char[] ch;
    private Ele[] ele;


    public LinkTable(char[] ele,char[][] matrix) {
        size = ele.length;
        this.ch = ele;
        this.ele = new Ele[size];
        for (int i = 0; i < size; i++) {
            this.ele[i] = new Ele(ele[i]);
        }
        for(char[] temp:matrix){
            int firstPos = findIndex(temp[0]);
            this.ele[firstPos].add(temp[1]);
//            int secondPos = findIndex(temp[1]);
//            this.ele[secondPos].add(temp[0]); //注释该部分表示有向图
        }
    }

    private int findIndex(char c) {
        for (int i = 0; i < size; i++) {
            if(ch[i] == c){
                return i;
            }
        }
        return -1;
    }

    public void showTable(){
        for (int i = 0; i < size; i++) {
            System.out.print(ele[i].data+" ");
            Ele temp = ele[i].next;
            while (temp != null) {
                System.out.print(temp.data+" ");
                temp = temp.next;
            }
            System.out.println();
        }
    }
    //自定义结构，包含元素和指向下一个Ele对象的指针
    private class Ele{
        private char data;
        private Ele next;

        public Ele(char data) {
            this.data = data;
            this.next = null;
        }

        public void add(char data){
            Ele current = this;
            while(current.next != null){
                current = current.next;
            }
            current.next = new Ele(data);
        }
    }

    public static void main(String[] args) {
        char[] ele = {'A','B','C','D'};
        char[][] side = {
                {'A','B'},{'A','C'},{'A','D'},{'B','D'},{'C','D'}
        };
        LinkTable linkTable = new LinkTable(ele,side);
        linkTable.showTable();
    }
}