图

实际开发中常用二维矩阵表示图, 矩阵中的每一行即为一条边, 格式如 [权重, 起始点, 结束点]

[
    [1, 1, 2],
    [4, 3, 2],
    [7, 3, 1]
]

以上矩阵所表示的结构如下:

Java

class GraphNode {
    public int value;   // 值
    public int in = 0;  // 入度
    public int out = 0; // 出度
    public ArrayList<GraphNode> nexts = new ArrayList<>();  // 当前点出发指向的所有相邻节点
    public ArrayList<Edge> edges = new ArrayList<>();       // 从当前点出发的所有边

    public GraphNode(int value) {
        this.value = value;
    }
}

class Edge {
    public int weight;
    public GraphNode from;
    public GraphNode to;

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

class Graph {
    public HashMap<Integer, GraphNode> nodes;   // 所有点集, key 为节点编号
    public HashSet<Edge> edges;                 // 所有边集

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

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

Python

class GraphNode:
    def __init__(self, value):
        self.value = value
        self.in_degree = 0
        self.out_degree = 0
        self.nexts = []
        self.edges = []


class Edge:
    def __init__(self, weight, from_node, to_node):
        self.weight = weight
        self.from_node = from_node
        self.to_node = to_node


class Graph:
    def __init__(self):
        self.nodes = dict()
        self.edges = set()


def create_graph(matrix):
    graph = Graph()
    for node in matrix:
        weight = node[0]
        from_val = node[1]
        to_val = node[2]
        
        if from_val not in graph.nodes.keys():
            graph.nodes[from_val] = GraphNode(from_val)
        if to_val not in graph.nodes.keys():
            graph.nodes[to_val] = GraphNode(to_val)
            
        from_node = graph.nodes.get(from_val)
        to_node = graph.nodes.get(to_val)
        new_edge = Edge(weight, from_node, to_node)
        
        from_node.nexts.append(to_node)
        from_node.edges.append(new_edge)
        from_node.out_degree += 1
        to_node.in_degree += 1
        graph.edges.add(new_edge)

    return graph