概念

1，顶点
2，边
3，路径
4，无向图

请添加图片描述
无向图：顶点之间的连接没有方向，比如 A - B ，也可以是 B - A
路径：比如从D -> C 的路径有
1）：D -> B -> C
2）：D -> A -> B -> C

5，有向图

请添加图片描述

有向图：顶点之间的连接方向，
比如 A -> B ，只能是A -> B ，不能是B -> A .

6，带权图

请添加图片描述

这种边带也全值的图也叫网

图的表示方式

1，二维数组
2，链表表示（邻接表）

邻接矩阵是表示图形中的顶点之间的矩阵，对于N个顶点的图而言，矩阵的row和col 表示的是 1…n 个点

请添加图片描述

邻接表，邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在，会造成空间的一定损失，邻接表的实现，只关心存在的边，不关心不存在的边，因此，没有空间浪费，邻接表由数组+链表组成

在这里插入图片描述

图的快速入门案例

1）要求代码实现如下图结构

请添加图片描述
在这里插入图片描述 2）思路分析：

顶点存储用String ，使用ArrayList 保存顶点
保存矩阵用 int[][] edges
代码实现

代码

package com.huan.graph;

import java.util.ArrayList;
import java.util.Arrays;

public class Graph {

    private ArrayList<String> vertexList;//存储顶点集合
    private int[][] edges; // 存储图对应的邻接矩阵
    private int numOfEdges; //表示边的数目

    public static void main(String[] args) {
        //测试图是否创建ok
        int n = 5; //结点的个数
        String Vertexs[] = {"A","B","C","D","E"};
        //创建图对象
        Graph graph = new Graph( 5 );
        //循环的添加顶点s
        for (String vertex : Vertexs){
            graph.insertVertex( vertex );
        }

        //添加边
        // A - B , A - C , B-C , B-D , B-E
        graph.insertEdge( 0,1,1 );  //A - B
        graph.insertEdge( 0,2,1 );  //A - C
        graph.insertEdge( 1,2,1 );  //B - C
        graph.insertEdge( 1,3,1 );  //B - D
        graph.insertEdge( 1,4,1 );  //B - E
        graph.insertEdge( 1,0,1 );  //B - A

        //显示邻结矩阵
        graph.showGraph();

    }

    //构造器
    public Graph(int n) {
        //初始化矩阵
        edges = new int[n][n];
        //初始化顶点集合
        vertexList = new ArrayList<String>(n);
        //初始化边的数目
        numOfEdges = 0;
    }

    //图中常用的方法,
    //返回结点的个数
    public int getNumOfVertex(){
        return vertexList.size();
    }

    //得到边的数目
    public int getNumOfEdges(){
        return numOfEdges;
    }

    //返回结点i(下标)对应的数据 0 -> "A" , 1 -> "B" , 2 -> "C"
    public String getValueByIndex(int i){
        return vertexList.get( i );
    }

    //返回v1 v2 的权值
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }

    //显示图对应的矩阵
    public void showGraph(){
        for (int[] link : edges){
            System.err.println( Arrays.toString( link ) );
        }
    }

    //插入结点
    public void insertVertex(String vertex){
        vertexList.add( vertex );
    }

    //添加边
    /**
     * @param v1 表示点的下标即使第几个顶点 “A” - "B" , "A" -> 0  "B" -> 1
     * @param v2 表示第二个顶点对应的下标
     * @param weight 全值 , 表示矩阵里面的值，你想用什么值来表示 AB之间的关系 , 证明他们是关联的。
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}