起步

大纲

图的表示
图的遍历

• 深度优先（连通性，路径，二分图检测，环的检测，floodfill）
• 广度优先（无权图的最短路径）

欧拉路径
哈密尔顿路径
状态压缩

论有什么用？

培养思维，可以遇到新的问题的时候可以借助前人的方式，去创新性的解决新的问题。

图Graph

是由顶点的有穷非空集合和顶点之间的边的集合组成。表示方法为G(V,E)

• 线性表中的数据元素称为元素，树中的数据元素称为结点，图中的数据元素称为顶点
• 图的结构中不允许没有顶点

概念

图的定义

分类

• 有向图
• 无向图

G(V,E) 表示为V={A,B,C,D} E={(A,B),(B,C), (C,D), (D,A), (A,C)}

1. 图结构中，不允许没有顶点
2. 图中，数据元素称为顶点
3. 图结构中，两个顶点之间的关系用边来表示

有向图 从顶点V1到V2的边有方向，则称为这条边为有向边，也称为弧。由顶点和弧构成。弧有弧尾和弧头之分

表示方式

<V1, V2> => <弧尾, 弧头>

无向图 如果任意两点之间都存在边，则称该图为无向完全图。 由顶点和边构成

表示方式

(V1,V2)

• 含有n个顶点的无向图有n(n-1)/2条边

子图 Subgraph

图的顶点与边的关系

路径长度

树中根结点到任意结点的路径是唯一的。但是图中顶点与顶点之间的路径不是唯一的

路径长度是路径上的边或弧的数目

环

第一个顶点到最后一个顶点相同的路径称为回路或环。

权

边|弧附带的数值。可以表示为一个顶点到另一个顶点的距离。

路径

从顶点i出发经过一系列的边能够到达j的路径

连通，连通图，连通分量

图中顶点存在路径，两个顶点存在路径说明是连通

若任意两顶点都是连通的，则称为连通图。

图的存储

图的存储结构

图的机构比较复杂，任意两个顶点之间都可能会存在关系。

临接矩阵

用两个数组来表示图。一个一维数组存储顶点信息，一个二维数组存储图中边或弧的信息。

空间复杂度0(n^2)

代码

// 请输入两个数， 一个表示V 一个E。V表示有多少个节点，E表示有多少边。
/*
以上面的例子
5 6
0 1
0 2
1 3
1 4
2 3
3 4
*/
import java.io.File;
import java.util.Arrays;
import java.util.Scanner;
public class AdjMatrix {
    private int V; //节点
    private int E; //边
    private int[][] adj; //临街矩阵
    public AdjMatrix(String fileName){
        File file = new File(fileName); // 从文件读入
        try(Scanner scanner = new Scanner(file)){
            V = scanner.nextInt();
            E = scanner.nextInt();
            System.out.println("结点："+V+"\t"+"边数："+E);
            adj = new int[V][V];
            for(int i=0; i<E; i++){// 遍历
                int a= scanner.nextInt();
                int b = scanner.nextInt();
                adj[a][b] = 1;
                adj[b][a] = 1;
            }
        }catch (Exception e){
            e.printStackTrace();
        }
    }
    @Override
    public String toString() {
       for(int i=0; i<V; i++){
           System.out.println(Arrays.toString(adj[i]));
       }
       return "";
    }
    public static void main(String[] args) {
        AdjMatrix adjMatrix = new AdjMatrix("data.txt");
        System.out.println(adjMatrix);
    }
}
结点：5    边数：6
[0, 1, 1, 0, 0]
[1, 0, 0, 1, 1]
[1, 0, 0, 1, 0]
[0, 1, 1, 0, 1]
[0, 1, 0, 1, 0]

临接链表

数组与链表相结合，孩子表示法，将顶点集合存入数组，并对结点的孩子链式存储。

代码

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class AdjList {
    private int V;
    private int E;
    private LinkedList<Integer>[] adj;
    public AdjList(String fileName){
        File file = new File(fileName);
        try(Scanner scanner = new Scanner(file)){
            V =scanner.nextInt(); // 读取结点
            E = scanner.nextInt();// 读取边
            // 初始化
            adj = new LinkedList[V];
            for(int i=0; i<V; i++){
                adj[i] = new LinkedList<Integer>();
            }
            for(int i=0; i<E; i++){
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                adj[a].add(b);
                adj[b].add(a);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
    @Override
    public String toString() {
        for(int i=0; i<V;i++){
            System.out.println(adj[i]);
        }
        return "";
    }
    public static void main(String[] args) {
        AdjList adjList = new AdjList("data.txt");
        System.out.println(adjList);
    }
}
[1, 2]
[0, 3, 4]
[0, 3]
[1, 2, 4]
[1, 3]

十字链表

十字链表将临接表与逆临接表结合

定义结构

顶点结构

• firstin 表示入边表头指针，指向该顶点的入边表中的第一个结点。
• firstout 表示出边表头指针，指向该顶点的出边表中的第一个结点。

边结构

• tailvex是弧起点在顶点表的下标
• headvex是指弧终点在顶点表的下标
• headlink指入边标指针域
• taillink指边表的指针与，指向起点相同的下一条边

图的遍历

从图的某一个顶点触发访图中其余顶点，且使每一个顶点仅被访问一次。

• 深度优先遍历Depth_First_Search
• 广度优先遍历Breadth_First_Search

DFS

BFS

最小生成树

Prim