图
连通图：
常用概念：
- 顶点：vetex
- 边：edge
- 路径
- 无向图
- 有向图
- 带权图
1. 图的表示方式
二维数组【邻接矩阵】
链表【邻接表】：数组 + 链表
2. 简易无向图实现
package graph;
public class Graph {
private ArrayList<String> vertexList = new ArrayList<>(); // 点
private int[][] edges; // 边
private int numOfEdges; // 边的数目
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.insertVertx("A");
graph.insertVertx("B");
graph.insertVertx("C");
graph.insertEdge("A", "B", 2);
graph.printArr();
System.out.println("顶点个数 " + graph.getNumOfVertex());
System.out.println("边的个数 " + graph.getNumOfEdges());
System.out.println("A和B间的 weight= " + graph.getWeight("A", "B"));
}
public Graph(int n){
edges = new int[n][n];
}
// 插入节点
public void insertVertx(String vertex){
vertexList.add(vertex);
}
// 添加边
public void insertEdge(String vertexA, String vertexB, int weight){
int i = vertexList.indexOf(vertexA);
int j = vertexList.indexOf(vertexB);
if (edges[i][j] == 0) {
edges[i][j] = weight;
edges[j][i] = weight;
numOfEdges++;
}
}
public int getNumOfVertex(){
return vertexList.size();
}
public int getNumOfEdges(){
return numOfEdges;
}
// 得到权值
public int getWeight(String vertexA, String vertexB){
int i = vertexList.indexOf(vertexA);
int j = vertexList.indexOf(vertexB);
return edges[i][j];
}
public void printArr(){
for (int i = 0; i < edges.length; i++) {
for (int j = 0; j < edges.length; j++) {
System.out.print(edges[i][j] + " ");
}
System.out.println();
}
}
}