签名能留链接的网站,网站建设运营服务商,江门网站开发,吉安企业做网站一、概念 和二叉树的区别#xff1a;图可能有环
常见概念
顶点#xff08;Vertex#xff09;#xff1a; 图中的节点或点。边#xff08;Edge#xff09;#xff1a; 顶点之间的连接线#xff0c;描述节点之间的关系。有向图#xff08;Directed Graph#xff09;图可能有环
常见概念
顶点Vertex 图中的节点或点。边Edge 顶点之间的连接线描述节点之间的关系。有向图Directed Graph 边具有方向性的图边有箭头表示方向。无向图Undirected Graph 边没有方向性的图。路径Path 顶点序列通过边连接的顶点序列。回路Cycle 闭合的路径起点和终点相同的路径。连通图Connected Graph 图中任意两个顶点之间都存在路径的图。强连通图Strongly Connected Graph 有向图中任意两个顶点之间都存在双向路径的图。连通分量Connected Component 无向图中的极大连通子图。树Tree 无环连通图任意两个节点都有唯一路径。森林Forest 多个不相交树的集合。度Degree 顶点的度是指与该顶点相关联的边的数量。权重Weight 边或者顶点上的数值表示边的代价或者顶点的属性。
邻接矩阵 ABCDA0正无穷58B正无穷09正无穷C5904D8正无穷40 邻接表法
NodeweightAC5AD8CB9CD4BC9DA8DC4 二、算法题
1、套路模板 /*** author jeb_lin* 22:27 2023/11/29*/
public class Node {public int value; // 可以改成 Stringpublic int in;// 入度public int out;// 出度public ArrayListNode nexts; // 多个后继节点public ArrayListEdge edges; // 多条边该节点指出去的public Node(int value){this.value value;this.in 0;this.out 0;this.nexts new ArrayList();this.edges new ArrayList();}public int getValue() {return value;}public void setValue(int value) {this.value value;}public int getIn() {return in;}public void setIn(int in) {this.in in;}public int getOut() {return out;}public void setOut(int out) {this.out out;}public ArrayListNode getNexts() {return nexts;}public void setNexts(ArrayListNode nexts) {this.nexts nexts;}public ArrayListEdge getEdges() {return edges;}public void setEdges(ArrayListEdge edges) {this.edges edges;}
} /*** author jeb_lin* 22:27 2023/11/29*/
public class Edge {public Node from;public Node to;public int weight;public Edge(Node from, Node to, int weight) {this.weight weight;this.from from;this.to to;}// 复写下面这俩是为了放入Set的时候能正确去重Overridepublic boolean equals(Object obj) {if (this obj) {return true;}if (obj null || !(obj instanceof Edge)) {return false;}Edge edge (Edge) obj;return this.weight edge.weight Objects.equals(edge.from, this.from) Objects.equals(edge.to, this.to);}Overridepublic int hashCode() {return this.weight * this.from.hashCode() * this.to.hashCode();}public Node getFrom() {return from;}public void setFrom(Node from) {this.from from;}public Node getTo() {return to;}public void setTo(Node to) {this.to to;}public int getWeight() {return weight;}public void setWeight(int weight) {this.weight weight;}
}/*** author jeb_lin* 22:26 2023/11/29*/
public class Graph {public HashMapInteger,Node nodes; // 该图上面的所有NodenodeVal - Nodepublic HashSetEdge edges; // 该图上面的所有边public Graph(){this.nodes new HashMap();this.edges new HashSet();}public HashMapInteger, Node getNodes() {return nodes;}public void setNodes(HashMapInteger, Node nodes) {this.nodes nodes;}public HashSetEdge getEdges() {return edges;}public void setEdges(HashSetEdge edges) {this.edges edges;}
}2、二维数组转化成图
012备注0015Node0-Node1 ,weight51123Node1-Node2 ,weight32027Node0-Node2 ,weight7 /*** 把二维数组转换成图* [* [0,1,5], // 表示 node0 - node1 ,weight 5* [1,2,3],* [0,2,7]* ]** param matrix* return*/public static Graph createGraph(int[][] matrix) {Graph graph new Graph();HashMapInteger, Node nodes new HashMap(); // 该图上面的所有NodenodeVal - NodeHashSetEdge edges new HashSet(); // 该图上面的所有边graph.setEdges(edges);graph.setNodes(nodes);for (int i 0; i matrix.length; i) {int[] row matrix[i];if (!nodes.containsKey(row[0])) {nodes.put(row[0], new Node(row[0]));}if (!nodes.containsKey(row[1])) {nodes.put(row[1], new Node(row[1]));}Node from nodes.get(row[0]);Node to nodes.get(row[1]);from.setOut(from.getOut() 1);to.setIn(to.getIn() 1);from.getNexts().add(to);Edge edgeTemp new Edge(from, to, row[2]);from.getEdges().add(edgeTemp);if(!edges.contains(edgeTemp)){edges.add(edgeTemp);}}return graph;}public static void main(String[] args) {int[][] arr {{0, 1, 5}, {1, 2, 3}, {0, 2, 7}};Graph graph createGraph(arr);System.out.println(ok);}
