- 技术博客
- 用了都说好的Python、Java双实现的Graph图数据结构的定义
'''
一个好用的Graph的定义
权重，from Node到to Node
【
weight,from ,to
[12, 2, 4];
[4, 2, 7]
....
】
好的定义已经帮你解决了很多问题，比如这个图的Node出度入度直接就可以求
python代码的图定义是我直接从下面的Java代码翻译过来的
'''
class Graph:
def __init__(self
):
self
.nodes
={}
self
.edges
=set()
class Node:
def __init__(self
,valuse
):
self
.valuse
=valuse
self
.In
=0
self
.out
=0
self
.nexts
=[]
self
.edges
=[]
class Edge:
def __init__(self
,weight
,From
,to
):
self
.weight
=weight
self
.From
=From
self
.to
=to
def createGraph(matrix
):
graph
=Graph
()
for i
in range(len(matrix
)):
weight
=matrix
[i
][0]
From
=matrix
[i
][1]
to
=matrix
[i
][2]
if(From
not in graph
.nodes
):
graph
.nodes
.update
({From
:Node
(From
)})
if (to
not in graph
.nodes
):
graph
.nodes
.update
({to
:Node
(to
)})
fromNode
=graph
.nodes
.get
(From
)
toNode
=graph
.nodes
.get
(to
)
newEdge
=Edge
(weight
,fromNode
,toNode
)
fromNode
.nexts
.append
(toNode
)
fromNode
.out
+=1
fromNode
.In
+=1
fromNode
.edges
.append
(newEdge
)
graph
.edges
.add
(newEdge
)
return graph
if __name__
== '__main__':
matrix
=[[1,2,3],[4,5,6]]
graph
=createGraph
(matrix
)
print(graph
.nodes
.keys
())
'''
## Java注释 有类型 看着方便
public class Graph {
public HashMap<Integer,Node> nodes;
public HashSet<Edge> edges;
public Graph() {
nodes = new HashMap<>();
edges = new HashSet<>();
}
}
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 static Graph createGraph(Integer[][] matrix) {
Graph graph = new Graph();
for (int i = 0; i < matrix.length; i++) {
Integer weight = matrix[i][0];
Integer from = matrix[i][1];
Integer to = 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;
}
'''
