为什么要有图
当我们需要表示多对多的关系时,就需要用到图了。
图的基本介绍
图是一种数据结构,其中节点可以具有零个或多个相邻的元素。两个结点之间的连接称为边,结点也可以称为顶点。
如图:
图常用的概念
-
顶点(vertex)
-
边(edge)
-
路径
-
无向图(下图)
-
有向图
-
带权图
图的表示方式
二维数组表示
也叫 邻接矩阵
链表
也叫 邻接表
入门案例
思路分析
- 存储顶点,使用ArrayList
- 保存矩阵,使用int[][] adges
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
| package com.algorithm.graph;
import java.util.ArrayList; import java.util.Arrays;
public class Graph {
private ArrayList<String> vertexList;
private int[][] edges;
private int numOfEdges;
public static void main(String[] args) { int n = 5; String[] vertexs = {"A","B","C","D","E"}; Graph graph = new Graph(n); for (String vertex : vertexs) { graph.insertVertex(vertex); } graph.insertEdge(0,1,1); graph.insertEdge(0,2,1); graph.insertEdge(1,2,1); graph.insertEdge(1,3,1); graph.insertEdge(1,4,1);
graph.showGraph();
}
public Graph(int n){ vertexList = new ArrayList<>(n); edges = new int[n][n]; }
public int getNumOfVertex(){ return vertexList.size(); }
public int getNumOfEdges(){ return numOfEdges; }
public String getVertexByIndex(int index){ return vertexList.get(index); }
public void showGraph(){ for (int[] edge : edges) { System.out.println(Arrays.toString(edge)); } }
public int getWeight(int v1,int v2){ return edges[v1][v2]; }
public void insertVertex(String vertex){ vertexList.add(vertex); }
public void insertEdge(int v1,int v2,int weight){ edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } }
|
输出:
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
如果在设置边的时候,设置如下
1 2 3 4 5 6 7 8
|
graph.insertEdge(0,1,23); graph.insertEdge(0,2,12); graph.insertEdge(1,2,34); graph.insertEdge(1,3,56); graph.insertEdge(1,4,41);
|
边的权值设置为实际长度,输出的结果为:
[0, 23, 12, 0, 0]
[23, 0, 34, 56, 41]
[12, 34, 0, 0, 0]
[0, 56, 0, 0, 0]
[0, 41, 0, 0, 0]