【数据结构与算法学习】图的快速入门案例

一、图的定义及其相关概念的介绍

定义：图是由顶点的有穷非空集合和顶点之间边的集合组成，表示为G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

无向图：顶点与顶点之间的连接没有方向，比如v1-v2，既可以是v1->v2，也可以是v2->v1。（上图即为） 有向图：顶点与顶点之间的连接是有方向的，比如v1->v2，就明确指定顶点间的方向是从v1指向v2的。（带箭头） 带权图：顶点与顶点的连接的边上带上一个权值的无向图。

二、图的表示方式

图的表示方式有两种：邻接矩阵、邻接表 邻接矩阵：用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。 （点点之间如果存在连接则为1，否则为0）

三、快速入门案例（简单代码实现）

案例说明：在这个案例中，从视觉上的无向图用简单代码的方式呈现出图的邻接矩阵。通过输入图的结点数和结点名称，以及结点间的连接情况，来得到一个图的邻接矩阵。

package com.datou.graph;

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

/**
 * @author datou
 * @data 2020/8/11 - 18:01
 * @target 图的表示
 * 要求：输入结点及结点数，各个边的连接情况，输出邻接矩阵
 */
public class Graph {
          
   
    //声明图的结点，用动态数组表示
    private ArrayList<String> nodeList;
    //声明邻接矩阵
    private int[][] arr;

    //输入结点数，初始化参数
    public Graph(int n){
          
   
        nodeList = new ArrayList<String>(n);
        arr = new int[n][n];
    }

    /**
     * 插入结点
     * @param nodeValue
     */
    public void insertNode(String nodeValue){
          
   
        nodeList.add(nodeValue);
    }

    /**
     * 无向图添加边，连接则为1，否则则为0
     * @param v1 结点1
     * @param v2 结点2
     * @param weight 权值
     */
    public void insertArr(int v1, int v2, int weight){
          
   
        arr[v1][v2] = weight;
        arr[v2][v1] = weight;
    }

    /**
     * 显示图
     */
    public void showGraph(){
          
   
        for (int[] link : arr){
          
   
            System.out.println(Arrays.toString(link));
        }
    }

    public static void main(String[] args) {
          
   
        int n = 5;
        Graph graph = new Graph(n);
        String[] nodeList = {
          
   "A","B","C","D","E"};
        //循环插入结点值
        for (String nodeValue : nodeList){
          
   
            graph.insertNode(nodeValue);
        }
        //A-B A-C B-C B-D B-E
        graph.insertArr(0,1,1);
        graph.insertArr(0,2,1);
        graph.insertArr(1,2,1);
        graph.insertArr(1,3,1);
        graph.insertArr(1,4,1);

        graph.showGraph();

    }
}
/**结果：
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
**/

教程视频： 😄希望以上的分享对你有所帮助！若有错误，请小伙伴们指出！