图的基本结构

概念：

（1）图是由顶点集合以及顶点间的关系集合组成的一种数据结构。

Graph = (V,E) V是顶点的有穷非空集合；E是顶点之间关系的有穷集合，也叫边集合。

（2）有向图：顶点对<x,y>是有序的；无向图：顶点对<x,y>是无序的。

（3）无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi,Vj)来表示。

（4）完全无向图：若有n个顶点的无向图有n(n-1)/2 条边, 则此图为完全无向图。

完全有向图：有n个顶点的有向图有n(n-1)条边, 则此图为完全有向图。

（5）树中根节点到任意节点的路径是唯一的，但是图中顶点与顶点之间的路径却不是唯一的。

路径的长度是路径上的边或弧的数目。

（6）如果对于图中任意两个顶点都是连通的，则成G是连通图。

（7）图按照边或弧的多少分稀疏图和稠密图。 如果任意两个顶点之间都存在边叫完全图，有向的叫有向图。

若无重复的边或顶点到自身的边则叫简单图。

（8）图中顶点之间有邻接点。无向图顶点的边数叫做度。有向图顶点分为入度和出度。

（9）图上的边和弧上带权则称为网。

（10）有向的连通图称为强连通图。

结构实现代码：

点：

public 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<>();
    }
}

---

边：

public 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;
    }

---

图：

public class Graph {
        //存储点集，Integer标识用
    public HashMap<Integer,Node> nodes;
    public HashSet<Edge> edges;

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

---

建立图：

思路：

建立一个图，题目通常会给你一个二维数组，例如如下这种，第一个元素表示from，第二个表示to，第三个元素表示权重

[1，2，50]
[2，3，100]
[4，3，40]

给定这个二维数组后，让你建立图
循环数组的第一维，如果图中没有from to 等就加入，然后加入边，入度出度等信息，就可以建立出一个图

代码：

public static Graph createGraph(Integer[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            Integer from = matrix[i][0];
            Integer to = matrix[i][1];
            Integer weight = matrix[i][2];
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to); 
            Edge newEdge = new Edge(weight, fromNode, toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }