## 圖的表達方式及創建 ### 二維數組表示法  ~~~ int[][] data = { {1,2,3}, // 頂點1到頂點2有一條權值為3的邊 {2,3,4},// 頂點2到頂點3有一條權值為4的邊 {1,3,2}, {2,4,5}, {3,5,1} }; ~~~ ### 按數據創建無向圖 ~~~ Graph graph = Graph.createGraphUnDirect(data); ~~~ ~~~ /** * 從數組場景創建無向圖 * @param data eg,{{1,3,2},{2,3,3}} * 表示 從頂點1到頂點3有權值為2的邊；頂點3到頂點1權值為2的邊 * 從頂點2到頂點3有權值為3的邊；頂點3到頂點2權值為3的邊 * @return */ public static Graph createGraphUnDirect(int[][] data){ Graph graph = new Graph(); for(int i=0;i<data.length;i++){ String from = data[i][0] + ""; String to = data[i][1] + ""; Integer weight = data[i][2]; // 將from頂點和to頂點加入到圖里 if(!graph.vertexs.containsKey(from)){ graph.vertexs.put(from,new Vertex(from)); } if(!graph.vertexs.containsKey(to)){ graph.vertexs.put(to,new Vertex(to)); } // 從圖里獲取from和to頂點 Vertex fromVertex = graph.vertexs.get(from); Vertex toVertex = graph.vertexs.get(to); // 創建從from頂點到to頂點的邊 Edge edge = new Edge(weight,fromVertex,toVertex); // 創建反向的邊 Edge reverseEdge = new Edge(weight,toVertex,fromVertex); // from和to頂點的入度和出度都+1 fromVertex.out++; fromVertex.in++; toVertex.out++; toVertex.in++; // 將to頂點加入到from頂點里的點集nexts里 fromVertex.nexts.add(toVertex); // 將from頂點加入到to頂點里的點集nexts里 toVertex.nexts.add(fromVertex); // 將邊加入到from頂點的邊集里 fromVertex.edges.add(edge); // 將反向邊加入到to頂點的邊集里 toVertex.edges.add(reverseEdge); // 將邊加入到圖里 graph.edges.add(edge); // 將反向邊加入到圖里 graph.edges.add(reverseEdge); } return graph; } ~~~ ### 按數組創建有向圖 ~~~ Graph graph = Graph.createGraph(data); ~~~ ~~~ /** * 從數組場景創建有向圖 * @param data eg,{{1,3,2},{2,3,3}} * 表示 從頂點1到頂點3有權值為2的邊； * 從頂點2到頂點3有權值為3的邊 * @return */ public static Graph createGraph(int[][] data){ Graph graph = new Graph(); for(int i=0;i<data.length;i++){ String from = data[i][0] + ""; String to = data[i][1] + ""; Integer weight = data[i][2]; // 將from頂點和to頂點加入到圖里 if(!graph.vertexs.containsKey(from)){ graph.vertexs.put(from,new Vertex(from)); } if(!graph.vertexs.containsKey(to)){ graph.vertexs.put(to,new Vertex(to)); } // 從圖里獲取from和to頂點 Vertex fromVertex = graph.vertexs.get(from); Vertex toVertex = graph.vertexs.get(to); // 創建從from頂點到to頂點的邊 Edge edge = new Edge(weight,fromVertex,toVertex); // from頂點的出度+1，to頂點的入度+1 fromVertex.out++; toVertex.in++; // 將to頂點加入到from頂點里的nexts里 fromVertex.nexts.add(toVertex); // 將邊加入到from頂點的邊集里 fromVertex.edges.add(edge); // 將邊加入到圖里 graph.edges.add(edge); } return graph; } ~~~ ### 字符箭頭數組表示法  ~~~ String[] arrows = {">>v",">>v","^<<"}; ~~~ ~~~ /** * 從箭頭數組場景創建有向圖 * @param arrows eg, 自主編號 * { * ">>v", 1,2,3 * "v^<", 4,5,6 * "<><" 7,8,9 * } * 表示 從頂點1到頂點2有邊；頂點2到頂點3有邊；頂點3到頂點6有邊 * 頂點4到頂點7有邊；頂點5到頂點2有邊；頂點6到頂點5有邊 * 頂點8到頂點9有邊；頂點9到頂點8有邊 * @return */ public static Graph createGraphFromArrowString(String[] arrows){ Graph graph = new Graph(); int row = arrows.length; int col = arrows[0].length(); // 設置上下左右的坐標規則 Map<Character,int[]> ruleMap = new HashMap<>(); ruleMap.put('^',new int[]{-1,0}); ruleMap.put('v',new int[]{1,0}); ruleMap.put('<',new int[]{0,-1}); ruleMap.put('>',new int[]{0,1}); for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ String from = (i * col + j + 1) + ""; int[] rule = ruleMap.get(arrows[i].charAt(j)); int nextI = i + rule[0]; int nextJ = j + rule[1]; String to = (nextI * col + (nextJ + 1)) + ""; // 無權，默認為1 Integer weight = 1; // 判斷to點的坐標在合法范圍內 if(nextI >=0 && nextI < row && nextJ >=0 && nextJ < col){ // 將from頂點和to頂點加入到圖里 if(!graph.vertexs.containsKey(from)){ graph.vertexs.put(from,new Vertex(from)); } if(!graph.vertexs.containsKey(to)){ graph.vertexs.put(to,new Vertex(to)); } // 從圖里獲取from和to頂點 Vertex fromVertex = graph.vertexs.get(from); Vertex toVertex = graph.vertexs.get(to); // 創建從from頂點到to頂點的邊 Edge edge = new Edge(weight,fromVertex,toVertex); fromVertex.out++; toVertex.in++; // 將to頂點加入到from頂點里的點集nexts里 fromVertex.nexts.add(toVertex); // 將邊加入到from頂點的邊集里 fromVertex.edges.add(edge); // 將邊加入到圖里 graph.edges.add(edge); } } } return graph; } ~~~