【数据结构】图论入门

引入

数据的逻辑结构：

• 聚集：数据元素间除“同属于一个聚集”外，无其他关系
  
• 线性结构：一个对一个，例如：线性表、栈、队列
  
• 树形结构：一个对多个，例如：树
  
• 图形结构：多个对多个，例如：图
  

图的基本概念及术语

   图：G = ( V, E )
  V：顶点（数据元素）的有穷非空聚集
  E：边的有穷聚集
  图的类型界说

无向图：每条边都是无方向的

有向图：每条弧都是有方向的

完全图：任意两个点都有一条边相连

• 无向完全图：n个结点就有n * (n - 1) / 2 条边
  
• 有向完全图：n个结点就有n * (n - 1) 条边
  

稀疏图：有很少的边或者弧的图（通常 m 远小于nlog(n)）
稠密图：有较多的边或者弧的图（通常 m 大于nlog(n)）
连通图：在无（有）向图G = (V,{E})中，若对任意两个顶点v、u，都存在v到u的路径，则称G是连通图（强连通图）
图的基本术语

• 网：边或者弧带权（有值）的图
  
• 毗邻：有边 / 弧相连的两个顶点之间的关系
  
  
  
  • 存在（Vi，Vj），则称 Vi 和 Vj 互为毗邻点（无向图）
    
  • 存在 <Vi，Vj>，则称 Vi 毗邻到Vj，Vj 毗邻于 Vi（有向图）
    
  
  
• 关联（依附）：边 / 弧与顶点之间的关系
  存在（Vi，Vj）/ <Vi，Vj>，则称该边/弧关联与Vi和Vj
  
• 顶点的度：与该顶点相干联的边的数目，记为TD(V)
  在有向图当中，顶点的度即是该顶点的入度与出度之和
  顶点V的入度是以V为终点的有向边的条数
  以上图为例：
  ​ 对于上面的有向图来说，每个结点的度都为2
  ​ 对于上面的无向图来说，每个结点的度都为3，但是不同结点的入度、出度不一样（V3入度为1，出度为2）
  
• 路径：毗连的边构成的顶点序列
  
• 路径长度：路径上边/弧的数目/权值之和
  
• 回路（环）：第一个顶点和末了一个顶点相同的路径
  
• 简单路径：除路径起点和终点可以相同之外，其余顶点均不相同的路径
  
• 简单回路（简单环）：除路径起点和终点相同之外，其余顶点均不相同的路径
  
• 子图：设有两个图G = (V,{E})，G1 = (V1,{E1})，若V1属于V并且E1属于E，则称G1是G的子图
  
• 连通分量（强连通分量）：无（有）向图的极大连通子图称为G的连通分量（强连通分量）
  
  
  
  • 极大连通子图：该子图是G连通子图，将G的任何不在该子图的顶点参加，此图不再一连
    
  • 极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，此子图不再一连
    
  
  

图的存储结构

数组（毗邻矩阵）表现法

概述

建立一个顶点表（记录各个顶点信息）和一个毗邻矩阵（表现各个顶点之间的关系）

• 设图A = (V,E)有n个顶点，则顶点表Vext[n]表现为
     i01…n-1VextV1V2…Vn
  
• 图的毗邻矩阵是一个二维数组A.arcs[n][n],界说为：
  当存在<i,j>或者( i,j )属于图中的边或者弧，我们就将A.arcs[j]赋值为1，否则为0
  

举例

无向图

详细形况根据顶点的值去建立顶点表
毗邻矩阵：
V1V2V3V4V5V101010V210101V301011V410100V501100 特点：

• 无向图的毗邻矩阵是对称的
  
• 顶点i的度 = 第i行（列）中1的个数
  
• 完全图的毗邻矩阵中，对角元素为0，其余为1
  

代码演示见下面遍历部分
有向图

毗邻矩阵：
v1v2v3v4v10110v20000v30001v41000 特点：

• 有向图的毗邻矩阵可能是不对称的
  
• 顶点的出度 = 第i行元素之和
  顶点的入度 = 第i列元素之和
  顶点的度 = 出度 + 入度
  

   网的毗邻矩阵就是将1用权值替换
  代码演示见下面遍历部分
优缺点

优点：

• 直观，简单，好明白
  
• 方便检查任意一对顶点间是否存在边
  
• 方便找任意顶点的所有毗邻点
  
• 方便盘算出任意顶点的度
  

缺点：

• 倒霉于增加和删除顶点
  
• 浪费空间：存稀疏图，有大量无效元素
  
• 浪费时间：统计稀疏图中共有多少条边
  

毗邻表

顶点：按编号顺序将顶点数据存储在一维数组中
关联同一顶点的边（以顶点为尾的弧）：用线性链表存储
举例

仍以上图为例
无向图：

特点：

• 毗邻表不唯一
  
• 若无向图中有n个顶点e条边，则其毗邻表需n个头结点和2e个表结点，适宜存储稀疏图
  
• 无向图中顶点vi的度为第i个单链表中的结点数
  

代码演示见下面遍历部分
有向图：

特点：

• 顶点vi的出度为第i个单链表中的结点个数
  
• 顶点vi的入度为整个单链表中毗邻点域值是i-1的结点个数
  

代码演示见下面遍历部分
   毗邻矩阵与毗邻表的关系:
  1.接洽：毗邻表中每个链表对应于毗邻矩阵中的每一行，链表中结点个数即是一行中非零元素的个数
  2.区别：
  a.对于任意确定的无向图，毗邻矩阵是唯一的(行列号与顶点编号同等)，但毗邻表不唯一（毗连次序与顶点编号无关）
b.毗邻矩阵的空间复杂度为O(n^2)，而毗连表的空间复杂度为O(n+e)
  图的遍历

界说：从已给的连通图中某一顶点出发，沿着一些边访问图中所有的顶点，且每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算
实质：找每个顶点的毗邻点的过程
问题：由图的特点，图中可能出现回路，且图的任一顶点都可能与其他结点相遇，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点，怎么避免重复访问？
解决思路：设置辅助数组a[n]，用来标志每个被访问过的顶点，初始状态都为0，当顶点i被访问，改a为1，防止被多次访问
深度优先搜索（DFS）

方法：

• 在访问图中某一起始顶点v后，由v出发，访问它的任一毗邻顶点w1
  
• 再由w1出发访问与w1毗邻，但还未被访问过的顶点w2
  
• 然后再从w2出发进行雷同的访问…
  
• 如此进行下去，直至到达所有的毗邻顶点都被访问过的顶点u为止
  
• 接着退回一步退到前一次刚访问过的顶点，看是否还有其他没有被访问的毗邻顶点
  
• 如果有则访问此顶点，之后再从此顶点出发，进行与之前雷同的访问
  
• 如果没有就再退回一步进行搜索，重复上述过程，直到连通图中所有顶点都被访问过为止
  

留意：

• 稠密图适于在毗邻矩阵上进行深度遍历
  
• 稀疏图适于在毗连表上进行深度遍历
  

对于毗邻矩阵的代码演示：

1. public class GraphAdjacencyMatrix {
2.     private int V; // 顶点的数量
3.     private int[][] matrix; // 邻接矩阵
4.     private boolean[] visited;
5.     // 构造函数
6.     public GraphAdjacencyMatrix(int v) {
7.         V = v;
8.         matrix = new int[v][v];
9.         visited = new boolean[v];
10.         for (int i = 0; i < v; i++) {
11.             visited[i] = false;
12.         }
13.     }
15.     // 添加边
16.     public void addEdge(int v, int w, int weight) {
17.         matrix[v][w] = weight; // 因为是无向图，所以需要添加两个方向的边
18.         matrix[w][v] = weight;
19.     }
21.     //深度优先遍历
22.     private void DFS(int v) {
23.         visited[v] = true;
24.         System.out.print(v + " ");
26.         for (int i = 0; i < V; i++) {
27.             if (matrix[v][i] == 1 && !visited[i]) {
28.                 DFS(i);
29.             }
30.         }
31.     }
33.     // 遍历所有顶点（如果顶点未访问，则进行DFS）
34.     public void DFSTraversal() {
35.         for (int i = 0; i < V; i++) {
36.             if (!visited[i]) {
37.                 DFS(i); // 从顶点i开始DFS
38.             }
39.         }
40.     }
42.     // 打印图
43.     public void printGraph() {
44.         for (int i = 0; i < V; i++) {
45.             for (int j = 0; j < V; j++) {
46.                 if (matrix[i][j] == 0) {
47.                     System.out.print("0 ");
48.                 } else {
49.                     System.out.print(matrix[i][j] + " ");
50.                 }
51.             }
52.             System.out.println();
53.         }
54.     }
55. }

复制代码

1. public class linjiejuzhen {
2.     public static void main(String[] args) {
3.         GraphAdjacencyMatrix graph = new GraphAdjacencyMatrix(4);
5.         graph.addEdge(0, 1, 10); // 添加边 0-1 权重为 10
6.         graph.addEdge(0, 2, 6);
7.         graph.addEdge(1, 2, 4);
8.         graph.addEdge(2, 3, 1);
10.         System.out.println("Adjacency Matrix:");
11.         graph.printGraph();
12.         System.out.println("Depth First Traversal starting from vertex 0: ");
13.         graph.DFSTraversal(); //0 1 2 3
14.     }
15. }

复制代码

1. Adjacency Matrix:
2. 0 10 6 0
3. 10 0 4 0
4. 6 4 0 1
5. 0 0 1 0
6. Depth First Traversal starting from vertex 0:
7. 0 1 2 3

复制代码

对于毗邻表代码演示：

1. import java.util.Iterator;
2. import java.util.LinkedList;
4. public class DirectedGraphAdjacencyList {
5.     private int V; // 顶点的数量
6.     private LinkedList<Integer> adj[];
7.     private boolean visited[]; // 邻接表
9.     // 构造函数
10.     public DirectedGraphAdjacencyList(int v) {
11.         V = v;
12.         adj = new LinkedList[v];
13.         visited = new boolean[v];
14.         for (int i = 0; i < v; i++) {
15.             adj[i] = new LinkedList<>();
16.             visited[i] = false;
17.         }
18.     }
20.     // 添加边
21.     public void addEdge(int v, int w) {
22.         adj[v].add(w); // 添加从顶点v到顶点w的有向边
23.     }
25.     // 打印图
26.     public void printGraph() {
27.         for (int i = 0; i < V; i++) {
28.             System.out.print("Vertex " + i + ":");
29.             Iterator<Integer> it = adj[i].iterator();
30.             while (it.hasNext()) {
31.                 System.out.print(" -> " + it.next());
32.             }
33.             System.out.println();
34.         }
35.     }
37.     private void DFS(int v) {
38.         visited[v] = true;
39.         System.out.print(v + " ");
41.         Iterator<Integer> i = adj[v].listIterator();
42.         while (i.hasNext()) {
43.             int n = i.next();
44.             if (!visited[n]) {
45.                 DFS(n); // 递归访问未访问的邻接顶点
46.             }
47.         }
48.     }
50.     // 遍历所有顶点执行DFS
51.     public void DFSTraversal() {
52.         for (int i = 0; i < V; i++) {
53.             if (!visited[i]) {
54.                 DFS(i); // 从顶点i开始DFS
55.             }
56.         }
57.     }
58. }

复制代码

1. public class DirectedGraphAdjacency {
2.     public static void main(String[] args) {
3.         DirectedGraphAdjacencyList graph = new DirectedGraphAdjacencyList(6);
5.         // 添加有向边
6.         graph.addEdge(5, 0);
7.         graph.addEdge(5, 3);
8.         graph.addEdge(4, 0);
9.         graph.addEdge(4, 1);
10.         graph.addEdge(2, 3);
11.         graph.addEdge(3, 1);
12.         graph.addEdge(1, 3);
14.         System.out.println("Adjacency List Representation of Directed Graph:");
15.         graph.printGraph();
16.         System.out.println("Depth First Traversal starting from vertex 0: ");
17.         graph.DFSTraversal(); //0 1 3 2 4 5
18.     }
19. }

复制代码

1. Adjacency List Representation of Directed Graph:
2. Vertex 0:
3. Vertex 1: -> 3
4. Vertex 2: -> 3
5. Vertex 3: -> 1
6. Vertex 4: -> 0 -> 1
7. Vertex 5: -> 0 -> 3
8. Depth First Traversal starting from vertex 0:
9. 0 1 3 2 4 5

复制代码

广度优先搜索（BFS）

方法：
从图的某一结点出发，首先依次访问该结点的所有毗邻结点 Vi1、Vi2……Vin，再按这些顶点被访问的先后次序依次访问与他们相毗邻的所有未被访问的顶点。重复此过程，直至所有顶点均被访问为止
对于毗邻矩阵的代码演示

1. import java.util.LinkedList;
2. import java.util.Queue;
4. public class DirectedGraphAdjacencyMatrix {
5.     private int V; // 顶点的数量
6.     private int[][] matrix; // 邻接矩阵
7.     private boolean[] visited;
9.     // 构造函数
10.     public DirectedGraphAdjacencyMatrix(int v) {
11.         V = v;
12.         matrix = new int[v][v];
13.         visited = new boolean[v];
14.         // 初始化矩阵，所有元素都设置为0，表示没有边
15.         for (int i = 0; i < v; i++) {
16.             for (int j = 0; j < v; j++) {
17.                 matrix[i][j] = 0;
18.             }
19.             visited[i] = false;
20.         }
21.     }
23.     // 添加边
24.     public void addEdge(int v, int w, int weight) {
25.         matrix[v][w] = weight; // 只在矩阵的对应位置添加边的权重
26.     }
28.     // 打印图
29.     public void printGraph() {
30.         for (int i = 0; i < V; i++) {
31.             for (int j = 0; j < V; j++) {
32.                 if (matrix[i][j] == 0) {
33.                     System.out.print(" 0 ");
34.                 } else {
35.                     System.out.print(" " + matrix[i][j] + " ");
36.                 }
37.             }
38.             System.out.println();
39.         }
40.     }
41.     //广度优先搜索
42.     public void BFS(int start) {
43.         Queue<Integer> queue = new LinkedList<>();
44.         visited[start] = true; // 标记起始顶点为已访问
45.         queue.add(start); // 将起始顶点添加到队列中
47.         while (!queue.isEmpty()) {
48.             int v = queue.poll(); // 从队列中取出一个顶点
49.             System.out.print(v + " ");
51.             for (int i = 0; i < V; i++) {
52.                 if (matrix[v][i] != 0 && !visited[i]) {
53.                     visited[i] = true; // 标记邻接顶点为已访问
54.                     queue.add(i); // 将邻接顶点添加到队列中
55.                 }
56.             }
57.         }
58.     }
59. }

复制代码

1. public class linjiejuzhenYou {
2.     public static void main(String[] args) {
3.         DirectedGraphAdjacencyMatrix graph = new DirectedGraphAdjacencyMatrix(4);
5.         graph.addEdge(0, 1, 10); // 添加有向边 0->1 权重为 10
6.         graph.addEdge(0, 2, 6);
7.         graph.addEdge(1, 2, 4);
8.         graph.addEdge(1, 3, 1);
9.         graph.addEdge(2, 3, 7);
11.         System.out.println("Directed Adjacency Matrix:");
12.         graph.printGraph();
13.         System.out.println("Breadth First Traversal starting from vertex 0: ");
14.         graph.BFS(0); //0 1 2 3
15.     }
16. }

复制代码

1. Directed Adjacency Matrix:
2. 0  10  6  0
3. 0  0  4  1
4. 0  0  0  7
5. 0  0  0  0
6. Breadth First Traversal starting from vertex 0:
7. 0 1 2 3

复制代码

对于毗邻表的代码演示

1. import java.util.Iterator;
2. import java.util.LinkedList;
3. import java.util.Queue;
5. public class UndirectedGraphAdjacencyList {
6.     private int V; // 顶点的数量
7.     private LinkedList<Integer> adj[]; // 邻接表
8.     private boolean[] visited;
10.     // 构造函数
11.     public UndirectedGraphAdjacencyList(int v) {
12.         V = v;
13.         visited = new boolean[V];
14.         adj = new LinkedList[v];
15.         for (int i = 0; i < v; i++) {
16.             adj[i] = new LinkedList<>();
17.             visited[i] = false;
18.         }
19.     }
21.     // 添加边
22.     public void addEdge(int v, int w) {
23.         adj[v].add(w); // 添加从v到w的边
24.         adj[w].add(v); // 因为是无向图，所以需要添加从w到v的边
25.     }
27.     // 打印图
28.     public void printGraph() {
29.         for (int i = 0; i < V; i++) {
30.             System.out.print("Vertex " + i + ":");
31.             Iterator<Integer> it = adj[i].iterator();
32.             while (it.hasNext()) {
33.                 System.out.print(" -> " + it.next());
34.             }
35.             System.out.println();
36.         }
37.     }
39.     public void BFS(int start) {
40.         Queue<Integer> queue = new LinkedList<>();
41.         visited[start] = true; // 标记起始顶点为已访问
42.         queue.add(start); // 将起始顶点添加到队列中
44.         while (!queue.isEmpty()) {
45.             int v = queue.poll(); // 从队列中取出一个顶点
46.             System.out.print(v + " ");
48.             Iterator<Integer> i = adj[v].listIterator();
49.             while (i.hasNext()) {
50.                 int n = i.next();
51.                 if (!visited[n]) {
52.                     visited[n] = true; // 标记邻接顶点为已访问
53.                     queue.add(n); // 将邻接顶点添加到队列中
54.                 }
55.             }
56.         }
57.     }
58. }

复制代码

1. public class UndirectedGraphAdjacency {
2.     public static void main(String[] args) {
3.         UndirectedGraphAdjacencyList graph = new UndirectedGraphAdjacencyList(4);
5.         graph.addEdge(0, 1); // 添加边 0-1
6.         graph.addEdge(0, 2);
7.         graph.addEdge(1, 2);
8.         graph.addEdge(2, 3);
10.         System.out.println("Adjacency List Representation of Undirected Graph:");
11.         graph.printGraph();
12.         System.out.println("Breadth First Traversal starting from vertex 0: ");
13.         graph.BFS(0); //0 1 2 3
14.     }
15. }

复制代码

1. Adjacency List Representation of Undirected Graph:
2. Vertex 0: -> 1 -> 2
3. Vertex 1: -> 0 -> 2
4. Vertex 2: -> 0 -> 1 -> 3
5. Vertex 3: -> 2
6. Breadth First Traversal starting from vertex 0:
7. 0 1 2 3

复制代码

二者搜索的算法分析

时间复杂度：
毗邻矩阵：
对于毗邻矩阵表现的图，时间复杂度重要受两个因素影响：

• 矩阵大小：毗邻矩阵的大小为