4.1 图的基本概念与实现

图的定义

🎨 Graph= (V，E)

🎨 V={x|x是一个结点，表示一个数据元素}、

图中的数据元素x也称为顶点（vertex)

V是顶点的有穷非空集合

🎨 E={<x，y>|x，y都属于V，并且x连接到y}

E是两个顶点之间的关系的集合

如果<x, y>属于E，那么表示x到y的一条弧(arc)，且x称为尾(tail)，y称为头(head),具有这种性质的图称为有向图(digraph)

如果<x,y>属于E，必有<y,x>也属于E，则以无序对(x, y)代替这两个有序对，表示x和y之间的一条边(edge)，此时的图称为无向图(undigraph)

术语

完全图

用|V|表示G中顶点的个数，用|E|表示G中弧或者边的个数

当不考虑顶点到其自身的弧或者边时，那么|V|和|E|乏间有如下关系:

1️⃣ 如果G是无向图，|E|的取值范围是0到|V|(|V|-1)/2

当|E|为最大值时，该无向图称为完全图(completedgraph)

2️⃣ 如果G是有向图，|E|的取值范围是0到|V|(|V|-1)

当|E|为最大值时，该有向图称为有向完全图

3️⃣ 如果G中有少量的边或弧(如|E|<|V| log|V|)时，称该G为稀疏图(sparse graph),反之称为稠密图（dense graph）

当G中的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权(weight),这种带权的图通常称为网(network)

顶点相关概念

对于无向图G，如果边(v,u)属于E，则称顶点v和u互为邻接点(adjacent),并且称边(v,u)与顶点和u相关联(incident)

顶点v的度(degree)是和v相关联的边的个数

对于有向图G，如果弧<v,u>属于E，则称顶点v邻接到(to)顶点u，顶点u邻接自(from)顶点v，并且称弧<v,u>与顶点v、u相关联

以顶点v为头的弧的数目称为v的入度(indegree)

以顶点v为尾的弧的数目称为v的出度(outdegree)

顶点v的度=顶点v的入度+顶点v的出度

子图

假设有两个图G=(V,E)和G’=(V’ ,E’),如果V’是V的子集，且E’是E的子集,称G’是G的子图

路径相关概念

在G=(V，E)中，当从v到u存在如下的边或弧时,我们称这是v到u的一条路径，该路径的长度则为这些边或弧的个数

1️⃣ 当G是无向图时，边是: $(v,v_1),(v_1,v_2),...,(v_n,u)$

2️⃣ 当G是有向图时，弧是: $<v,v_1>,<v_1,v_2>,...,<v_n,u>$

当在一条路径中出现的顶点不重复出现时则称该路径为简单路径(simple path)

图的连通

在一个图G中，如果从顶点v到顶点u有路径，则称v和u是连通的(connected)

如果G是无向图。那么当G中的任意两个顶点vi和vj，都有vi和vj是连通的，则称G是连通图(connected graph)

当无向图G不是一个连通图时，那么该无向图的极大连通子图则称为连通分量(connected component)

如果G是有向图，对于每一对顶点vi和vj，都有从vi到vj和vj到vi的路径，则称该G是强连通图

如果G不是强连通图，但是将G中的弧想象为边时能成为一个连通图时，我们称这个有向图G为弱连通(weakly connected)

有向图中的极大强连通子图称为有向图的强连通分量

如果图G中不存在环，那么称G为无环图(acycle)

一个无环图如果既是无向图也是连通图，则该图称为自由树(free tree)

一个无环图如果是有向图，则简称为DAG(directed acyclic graph)

图的实现方式

图有两种常见的表示方法

1️⃣ 相邻矩阵

是由|V|* |V|个元素组成的矩阵

矩阵中某个坐标对所对应的元素值表示该坐标对所对应的顶点之间的关系

2️⃣ 邻接表

是一个以链表为元素的数组

数组有|V|个元素，每个元素表示一个顶点第i个元素存储的链表中的内容为第i个顶点连接到的所有顶点信息

相邻矩阵

如果一个图有|V|个顶点，那么就定义一个具有|V|* |V|的矩阵M，M中的每个元素的取值如下（无权）

$M_{ij}=1 $ <i,j>是一条弧

$M_{ij}=0 $ <i,j>不是一条弧

有权的时候

$M_{ij}=Weight_{ij} $ <i,j>是一条弧

$M_{ij}=\infty $ <i,j>不是一条弧

时间复杂性分析

判断一个边是否存在：O(1)

寻找某个顶点所能到达的相邻顶点：O(|V|)

寻找所有的边：O(|V|^2)

增加或者删除一条边：O(1)

适用于稠密图

代码实现

public class GraphM {
    //用相邻矩阵实现无向图
    private ArrayList<String> V;//顶点
    private int E;//边数
    private int[][] matrix;//相邻矩阵

    /**
     * 初始化无向图
     * @param n 结点数
     */
    public GraphM(int n) {
        matrix = new int[n][n];
        V = new ArrayList<String>(n);
    }

    /**
     * 添加结点
     * @param vertex 结点值
     */
    public void insertVertex(String vertex){
        V.add(vertex);
    }

    /**
     * 插入边
     * @param v1 起点下标
     * @param v2 终点下标
     * @param weight 权值，这里0表示不相邻，1表示相邻
     */
    public void insertEdge(int v1,int v2,int weight) {
        matrix[v1][v2] = weight;
        matrix[v2][v1] = weight;
        E++;//边数+1
    }

    /**
     * 获得v1->v2的权值
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1,int v2){
        return matrix[v1][v2];
    }

    /**
     * 获得边的数量
     * @return
     */
    public int getEdgeNum(){
        return E;
    }

    /**
     * 获得结点数
     * @return
     */
    public int getVertexNum(){
        return V.size();
    }

    //打印邻接矩阵
    public void print() {
        for (int[] edge : matrix) {
            System.out.println(Arrays.toString(edge));
        }
    }

    public static void main(String[] args) {
        //定义图的所有顶点
        String[] vertexs = {"1","2","3","4"};
        //创建图
        GraphM graph = new GraphM(vertexs.length);
        //添加顶点到图中
        for (String vertex : vertexs) {
            graph.insertVertex(vertex);
        }
        //添加边到图中
        graph.insertEdge(0,1,1);
        graph.insertEdge(0,2,1);
        graph.insertEdge(0,3,1);
        graph.insertEdge(2,3,1);
        graph.print();

    }
}

[0, 1, 1, 1]
[1, 0, 0, 0]
[1, 0, 0, 1]
[1, 0, 1, 0]

邻接表

是一个以链表为元素的数组

时间复杂性分析

判断一个边是否存在：O(|V|)

寻找某个顶点所能到达的相邻顶点：O(|V|)

寻找所有的边：O(|E|)

增加或者删除一条边：O(|V|)

适用于稀疏图

代码实现

public class GraphList {
    //使用邻接表实现无向图
    private int V;//顶点数
    private int E;//边数
    private ArrayList<Integer> [] adjacencyList;//邻接表

    //对图进行初始化
    public GraphList(int v) {
        this.V = v;
        this.E = 0;
        this.adjacencyList = new ArrayList[v];
        for (int i = 0; i <v ; i++) {
            adjacencyList[i] = new ArrayList<>(v);
        }
    }

    //获取顶点数
    public int getV() {
        return V;
    }

    //获取边数
    public int getE() {
        return E;
    }

    /**
     * 插入边
     * @param v1 起点
     * @param v2 终点
     */
    public void insertEdge(int v1,int v2){
        adjacencyList[v1].add(v2);
        adjacencyList[v2].add(v1);
        E++;
    }

    public ArrayList<Integer> getAdjacentVertexs(int v){
        return adjacencyList[v];
    }

    public void print(){
        for (int i = 0; i < V; i++) {
            System.out.println("vertex:"+i+" : "+getAdjacentVertexs(i));
        }
    }

    public static void main(String[] args) {
        GraphList graphList = new GraphList(5);
        graphList.insertEdge(0,1);
        graphList.insertEdge(0,2);
        graphList.insertEdge(1,2);
        graphList.insertEdge(3,4);
        graphList.print();
    }
}

vertex:0 : [1, 2]
vertex:1 : [0, 2]
vertex:2 : [0, 1]
vertex:3 : [4]
vertex:4 : [3]