一、为什么要有图

图 

 图

二、图的常用概念

   图图 

 图 

 三、图的表示方法

图 

 1、邻接矩阵

图 

 2、邻接表

图 

 四、图的快速入门案例

图

 五、图的表示方式

图的结构表示方式有很多,当遇到其它表示方式时,可以把图转化为以下结构再进行后续操作

package Algorithms.Graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.ArrayList;

//图的结构
public class Graph {
    //点集
    public HashMap<Integer,Node> nodes; //Interger:点的编号  Node:实际点
    //边集
    public HashSet<Edge> edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

//点
class Node {
    public int value;              //点上的值
    public int in;                 //点的入度:有多少边可以指向这个点
    public int out;                //点的出度:有多少边可以指出这个点
    public ArrayList<Node> nexts;  //从当前这个点出发,由它发散出去的边的邻居有哪些点
    public ArrayList<Edge> edges;  //由当前点出发的边

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

//有向边 (两个有向边可以拼成一个无向边)
class Edge {
    public int weight;  //权值(距离)
    public Node from;   //从那个点出来
    public Node to;     //指向那个点

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

 学会创建接口把其它图的结构(下图)转化为自己所熟悉的结构(上面代码所示)

图 

 写一个转化的接口:

package Algorithms.Graph;

public class GraphGenerator {

    //接口(模板):把用户给的图结构转化为自己熟悉的图结构
    //matrix 所有的边   N*3的矩阵
    //[weight,from,to]
    public static Graph createGraph(Integer[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) { //matrix[0][0]  matrix[0][1]  matrix[0][2]
            Integer weight = matrix[i][0];
            Integer from = matrix[i][1];
            Integer to = matrix[i][2];
            if (!graph.nodes.containsKey(from)) {      //from节点(城市)不存在
                graph.nodes.put(from, new Node(from)); //在点集中新建这个from节点(编号,对应的城市)
            }
            if (!graph.nodes.containsKey(to)) {       //to节点(城市)不存在
                graph.nodes.put(to, new Node(to));    //在点集中新建这个to节点(编号,对应的城市)
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge newEdge = new Edge(weight, fromNode, toNode); //新建边
            fromNode.nexts.add(toNode); //添加from节点的邻居,toNode
            fromNode.out++; //出度++
            toNode.in++; //入度++
            fromNode.edges.add(newEdge); //添加属于fromNode的边
            graph.edges.add(newEdge); //把新建的边放入边集中
        }
        return graph;
    }

}

 

上一篇:【CCF CSP】【AC】201912-2:回收站选址(C++版)(只用到了结构体和数组)


下一篇:Leetcode112. 路径总和