秒客网

图

1、概念

• 每个结点可以有零个或者多个相邻的结点

• 边

  • 两个结点之间的连接

• 顶点

  • 结点

• 路径

  • 一个顶点到另一个顶点，中间遍历的结点组成的路

• 无向图

  • 顶点和顶点之间的边没有方向

  • A - B 可行，B - A也可行

  

• 有向图

  • 顶点和顶点之间的边有方向

  • A - B 可行，B - A不可行

  

• 带权图（网）

  • 边上有权值

  

2、图的表示

2.1、二维数组：邻接矩阵

• 表示图形中顶点之间的相邻关系的矩阵

• 行：0，1，2，...，n 号顶点

• 列：0，1，2，...，n 号顶点

• 元素为0表示两个顶点不相邻，元素为1表示两个顶点相邻

• 缺点

  需要为每个顶点都分配n的存储空间，即使某些边不存在，会造成空间浪费

2.2、链表：邻接表

• 数组 + 链表

• 只关心存在的边

  

3、图的创建代码实现

• 思路

  • 存储顶点：ArrayList

  • 存储边：int

public class Chart {
​
    // 存储顶点
    private ArrayList<String> vertex;
    // 存储边
    private int[][] edge;
    // 边的个数
    private int edgesCount;
​
    // 构造一个含有n个顶点的图
    public Chart(int n){
​
        vertex = new ArrayList<String>(n);
        edge = new int[n][n];
        edgesCount = 0;
​
    }
​
    // 添加顶点
    public void insertVertex(String v){
        // 在链表中添加元素
        vertex.add(v);
    }
​
    // 添加边
    public void insertEdge(int v1, int v2, int weight){
​
        // 在邻接矩阵中设置两个顶点之间的权值
        edge[v1][v2] = weight;
        edge[v2][v1] = weight;
        // 边的总数加1
        edgesCount ++;
    }
​
    // 返回图中结点的总数
    public int vertexNums(){
        return vertex.size();
    }
​
    // 返回图中边的总数
    public int edgesBums(){
        return edgesCount;
    }
​
    // 返回两个顶点之间的权值
    public int getWeight(int v1,int v2){
        return edge[v1][v2];
    }
​
    // 返回顶点下标对应的元素
    public String getVertexValue(int i){
        return vertex.get(i);
    }
​
    // 返回图对应的邻接矩阵
    public void getMatrix(){
        for (int i = 0; i <edge.length ; i++) {
            for (int j = 0; j <edge[0].length ; j++) {
                System.out.print(edge[i][j] + " ");
            }
            System.out.println();
        }
    }
}