寫在前面

我們知道，圖的表示法有很多，但是用多種方法來實現我們的算法，那就變的困難了，所以我們遇到圖的時候就要想到轉化為一般表示法，如果題目給的是別的表示方法，那么我們就進行轉換，將題目給的圖轉化為我們的一般圖表示法。

---

圖的一般表示法

// 點結構的描述 public class Node {public int value;//表示值public int in;//入度:有多少個邊指向此處public int out;//出度:有多少指出去的邊public ArrayList<Node> nexts;//直接鄰居,指向下一個的點集合public ArrayList<Edge> edges;//邊，從我出發的邊的集合//out=next.size()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 {public HashMap<Integer, Node> nodes;//k表示編號id，Node就是實際的點public HashSet<Edge> edges;public Graph() {nodes = new HashMap<>();edges = new HashSet<>();} }

轉化

例一

題目所給的圖的結構是這樣描述的

• 用二維數組來表示圖，共三個列，第一列表示邊權，第二列表示入點id，第三列表示出點id。
• [ 邊權 ,from ，to ] 三個都是int型的

// matrix 所有的邊 // N*3 的矩陣 // [weight, from節點上面的值，to節點上面的值] // // [ 5 , 0 , 7] // [ 3 , 0, 1] // public static Graph createGraph(int[][] matrix) {Graph graph = new Graph();for (int i = 0; i < matrix.length; i++) {// 拿到每一條邊， matrix[i] int weight = matrix[i][0];int from = matrix[i][1];int 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的直接鄰居fromNode.nexts.add(toNode);fromNode.out++;//fromNode的出度++toNode.in++; //toNode的入度++fromNode.edges.add(newEdge);//以fromNode開始的邊//給圖加邊graph.edges.add(newEdge);}return graph; }

鄰接矩陣轉換法

總結

以上是生活随笔為你收集整理的【图】图的一般表示法以及其他表示法转化为一般表示法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。