图 – 章鱼哥学习小课堂

第七章、图

❗7.1、图的定义和基本术语

7.1.1、定义

1、图

❗1、完全图

2、邻接（）是无向图，<>是有向图、稠密图、稀疏图、网、关联（依附）

3、度

①有几个边就是几个度

②如图

4、有向树

①有且仅有1个顶点的入度（指向它的）

②其余顶点的入度均为1

③出度没限制

④就是有向树

5、路径相关概念

6、连通图（强连通图是有向图）

（1）任意两点都找到路径是连通图

7、权与网

8、子图

9、连通分量（强连通分量）

（1）连通子图，是子图，也两点任意访问

（2）极大连通：是指该顶点已经最大了，再加子图就不连通了

（3）无向图

（4）有向图

10、极小连通子图

（1）与极大连通子图对应

11、生成树

（1）包含无向图G所有定点的极小连通子图

7.2、案例引入

7.2.1、六度空间理论

7.3、图的类型定义

7.3.1、图的抽象数据类型定义

1、定义

2、操作

❗7.4、图的存储结构

1、介绍

❗7.4.1、数组（邻接矩阵）表示法

1、如果存在关系则用1表示，否则为0

2、无向图的邻接矩阵图

①有几个顶点，就有i*j的矩阵

②矩阵的对角线是0，因为都表示自己

3、有向图的邻接矩阵表示法

①有几个顶点，就有i*j的矩阵

②矩阵的对角线是0，因为都表示自己

③i行和j列的含义

④分析1：有向图的邻接矩阵可能不是对称的（除非是完全图）

⑤分析2：

⑥出度：该结点指向的方向（箭头出发的方向）

⑦入度：其他结点指向自己

4、网（即有权图）的邻接矩阵表示法

2、邻接矩阵的存储

1、两个数组分别存储顶点表和接邻矩阵

2、存储结构

3、思路

3、java实现代码

1、无向图邻接矩阵

import java.util.ArrayList;
import java.util.Arrays;

public class Graph {
    public static void main(String[] args) {
        int n = 5;//节点个数
        String vertextValue[] = {"A","B","C","D","E"};
        //创建对象
        Graph graph = new Graph(n);
        //循环添加顶点
        for(String value : vertextValue){
            graph.inserVetex(value);
        }

        //添加边
        graph.install(0,1,1);
        graph.install(0,2,1);
        graph.install(1,2,1);
        graph.install(1,3,1);
        graph.install(1,4,1);
        //显示邻接矩阵
        graph.showGraph();

    }
    private ArrayList<String> vertexList;//设置存储节点的集合
    private int [][] edges;//用来存储矩阵
    private int numOfEdges;//存储节点的边数

    //构造器
    public Graph(int n ){
        //初始化c存储矩阵
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);//设置n个节点集合
        numOfEdges = 0;
    }

    //显示图对应的矩阵
    public void showGraph(){
        for(int[] link :edges){
            System.out.println(Arrays.toString(link));
        }
    }

    //得到顶点的个数
    public int getNumOfVertex(){
        return vertexList.size();
    }

    //得到边的数目
    public int getNumOfEdges(){
        return numOfEdges;
    }

    //得到节点i(下标）对应的数据
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    //添加边
    public void install(int v1 ,int v2,int weight){//v1是第一个顶点，v2是第二个顶点
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }

    //添加顶点
    public void inserVetex(String vertex){
        vertexList.add(vertex);
    }
}