数据结构与算法----图。学习_最大连通生成子图

图,基础知识

图(Graph)是由一个顶点集 V 和一个边集 E构成的数据结构。 G = (V , E)
V：图G中顶点（或结点，即数据元素）的有穷非空集合：V={v1 , v2,…, vn}
E：图G中顶点之间边（即关系）的有穷集合：
E={<vi , vj > ︱vi , vj ∈V，vi ≠vj ，i=1,2,…,n，j=1,2,…,n}

图，术语、定义、解释

数据结构：图，涉及的专业术语】顶点，有向图，无向图，完全图(边数和顶点数关系)，有向完全图(边数和顶点数关系)，度，入度和出度，权，网络，连通图，连通分量，极大连通子图，强连通图，强连通分量，极大强连通子图，路径，路径长度，简单路径，简单回路，回路，子图，生成子图，有向树，生成树，稠密图，稀疏图

图是由一组顶点和一组能够将两个顶点相连的边组成的。

相邻：当两个顶点通过一条边相连时,我们称这两个顶点是相邻的。

度数：某个顶点的度数即为依附于它的边的总数。

“路径”：路径：从顶点u 到顶点v 的路径是指一个顶点序列(u=v1, v2, …, vn=v)，其中<vi , vi+1> ∈ E, 1≤i<n 。在图中，路径是由边顺序连接的一系列顶点。

“路径长度”，定义/解释：路径上边的数目。

“简单路径”：定义/解释：序列中顶点不重复出现的路径。简单路径是一条没有重复顶点的路径。

环是一条至少含有一条边且起点和终点相同的路径。

简单环是一条（除了起点和终点必须相同之外）不含有重复顶点和边的环。

自环：即一条连接一个顶点和其自身的边;

平行边：连接同一对顶点的两条边称为平行边。

路径或者环的长度为其中所包含的边数。

简单图：没有平行边或自环的图称为简单图。

"简单回路"定义/解释：序列中第一个顶点和最后一个顶点相同的简单路径。

“回路”，定义/解释：序列中第一个顶点与最后一个顶点重合的路径。

“双连通图”，定义/解释：图中任意两点之间有两条不同的路径相通

“关节点”：定义/解释:删掉该结点及其相关联的边，图不再是连通图

“桥”:定义/解释:删掉该边后，图不再是连通图

连通：当两个顶点之间存在一条连接双方的路径时，我们称一个顶点和另一个顶点是连通的。

连通图（强连通图）：在无（有）向图G=(V,{E})中，若对任何两个顶点v,u都存在从v到u的路径，则称G是连通图（强连通图）。定义2：在无（有）向图中，任何两个顶点v,u之间都存在路径。如果从任意一个顶点都存在一条路径到达另一个任意顶点，我们称这幅图是连通图。

子图是由一幅图的所有边的一个子集（以及它们所依附的所有顶点）组成的图。许多计算问题都需要识别各种类型的子图，特别是由能够顺序连接一系列顶点的边所组成的子图。

一幅非连通的图由若千连通的部分组成，它们都是其极大连通子图。

连通分量：无向图G的极大连通子图。

（不懂YW）极大连通子图：该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。

强连通分量：有向图G的极大强连通子图。

极大强连通子图：该子图是G的强连通子图，将G的任何不在该子图中的顶点加入，子图不再强连通。

顶点的度：与该顶点相关联的边的数目，记为TD(v)。在有向图中，顶点的度等于该顶点的入度和出度之和。
顶点v的入度：是以v为终点的有向边的条数，ID(v);
顶点v的出度：是以v为起点的有向边的条数，OD(v).

权：图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。

树是一幅无环连通图。

互不相连的树组成的集合称为森林。

连通图的生成树是它的一幅子图，它含有图中的所有顶点且是一棵树。

图的生成树森林是它的所有连通子图的生成树的集合。

带权子图】

生成子图】

有向树】

生成树】

当且仅当一幅含有V个结点的图G满足下列5个条件之一时，它就是一棵树】:1.G有V-1条边且不含有环。2.G有V-1条边且是连通的。3.G是连通的，但删除任意一条边都会使它不再连通。4.G是无环图，但添加任意一条边都会产生一条环。5.G中的任意一对顶点之间仅存在一条简单路径。

当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并称该连接依附于这两个顶点。

某个顶点的度数即为依附于它的边的总数。

二分图】
二分图是一种能够将所有结点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分。

有向图

有向图，概述】
图中的每条边都有方向的图。
边的两个顶点有次序关系，有向边<u , v>称为从顶点u到顶点v的一条弧，u称为弧尾（或始点），v称为弧头（或终点）；有向图中弧<u , v>和弧<v, u>表示不同的二条边。

无向图

无向图，概述】
图中的每条边没有方向的图。
边的两个顶点没有次序关系，无向图用边(u , v)表示对称弧<u , v>和<v, u>；
在无向图中弧<u , v>和弧<v , u>表示相同的边(u , v)。

加权图

有向加权图

完全图

完全图：任意两个点都有一条边相连。
无向完全图：假设含有n个节点，则含有 e=n(n-1)/2 条边的无向图。
有向完全图：假设含有n个节点，则含有 e=n(n-1) 条弧的有向图。

什么样的图是树

图的存储结构

"图"中需要保存:顶点的数据 &顶点间的关系

图的存储结构】二维数组。多重链表(多重链表类型：邻接表，邻接多重表，十字链表)。

图的存储结构：邻接矩阵

邻接矩阵(数组+二维数组)

邻接矩阵(数组+二维数组)存储结构概述】建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间的关系）。邻接矩阵可用来表示:无向/有向图，有向/无向网。邻接矩阵多用于稠密图的存储

邻接矩阵存储结构的优点和缺点】

图的存储结构：邻接表

邻接表多用于稀疏图的存储

有向图的一种存储结构：十字链表

无向图的一种存储结构：邻接多重表

图的操作

图的操作，知识点概述】

图的处理算法的设计模式】我们会考虑大量关于图处理的算法，所以设计的首要目标是将图的表示和实现分离开来，为此，我们会为每个任务创建一个相应的类，用例可以创建相应的对象来完成任务，类的构造函数一般会在预处理中构造各种数据结构，以有效地响应用例的请求，典型的用例程序会构造一幅图，将图传递给实现了某个算法的类(作为构造函数的参数),然后调用用例的方法来获取图的各种性质。

图的基本操作，陈列】结构的建立和销毁；对顶点的访问操作；插入或删除顶点；插入和删除弧；对邻接点的操作；遍历

图相关的算法

图相关的算法：图的遍历。计算图中任意点之间的最短距离。二分图的配对问题。

图的应用】最小生成树；最短路径；拓扑排序；关键路径

图的遍历

图的遍历，概述】从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。
为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此我们为图设置一个访问标志数组visited［n］vi未被访问: visited[i]值为false ； vi被访问过: visited[i]为true

按图的类型，图的遍历分为：有向图的遍历和无向图的遍历。
图的遍历，根据搜索路径方向不同，分为：深度优先搜索和广度优先搜索。

计算图的遍历的时间复杂度

求出图的最大生成子树/最大连通分量】

实现一个图的遍历的步骤:首先决定存储结构(推荐邻接表)，（首先要创建图），再遍历】

图的遍历，应用】

深度优先遍历搜索DFS

深度优先遍历，DFS思想】
(depth-first search)在访问其中一个顶点时:将它标记为已访问，递归地访问它的所有没有被标记过的邻居顶点：它使用一个 boolean数组来记录和起点连通的所有顶点，递归方法会标记给定的顶点并调用自己来访问该顶点的相邻顶点列表中所有没有被标记过的顶点，如果图是连通的，每个邻接链表中的元素都会被检查到。

《算法导论》
深度优先搜索所使用的策略就像其名字所隐含的:只要可能，就在图中尽量“深入”。深度优先搜索总是对最近才发现的结点v的出发边进行探索，直到该结点的所有出发边都被发现为止。一旦结点v的所有出发边都被发现，搜索则“回溯”到v的前驱结点(v是经过该结点才被发现的)，来搜索该前驱结点的出发边。该过程一直持续到从源结点可以达到的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源结点，并重复同样的搜索过程。该算法重复整个过程，直到图中的所有结点都被发现为止。

深度优先遍历只会访问和起点连通的顶点。
mine：深度优先遍历，可以用在图，也可以用于树，用于图的时候，为了重复访问之前访问过的点，于是借助了一个数组保存访问信息

DFS适用对象—有向图、无向图

DFS算法流程图，算法伪代码(递归思想)；

有向图(采用邻接表存储结构)；

无向图(采用邻接矩阵or邻接表存储结构)；

稠密图适于在邻接矩阵上进行深度遍历；

稀疏图适于在邻接表上进行深度遍历。

DFS可以用来解决的问题】
路径检测问题：“两个给定的顶点是否连通?”等价于“两个给定的顶点之间是否存在一条路径?”，

单点路径：给定一幅图和一个起点s,回答“从s到给定目的顶点v是否存在一条路径?如果有，找出这条路径。”等类似问题。

深度优先遍历

/*

《极客时间》
*

/变量 found，它的作用是，当我们已经找到终止顶点 t 之后，我们就不再递归地继续查找了。



boolean found = false; // 全局变量或者类成员变量
 
public void dfs(int s, int t) {
  found = false;
  boolean[] visited = new boolean[v];
  int[] prev = new int[v];
  for (int i = 0; i < v; ++i) {
    prev[i] = -1;
  }
  recurDfs(s, t, visited, prev);
  print(prev, s, t);
}
 
private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
  if (found == true) return;
  visited[w] = true;
  if (w == t) {
    found = true;
    return;
  }
  for (int i = 0; i < adj[w].size(); ++i) {
    int q = adj[w].get(i);
    if (!visited[q]) {
      prev[q] = w;
      recurDfs(q, t, visited, prev);
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

广度优先遍历搜索BFS

https://leetcode-cn.com/u/nettee/

BFS是使用队列，要会BFS遍历图的算法

广度优先遍历

//广度优先遍历



/*

《极客时间》
其中 s 表示起始顶点，t 表示终止顶点。我们搜索一条从 s 到 t 的路径。实际上，这样求得的路径就是从 s 到 t 的最短路径。

visited是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q] 会被设置为 true。

queue是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，也就是说，我们只有把第 k 层的顶点都访问完成之后，才能访问第 k+1 层的顶点。当我们访问到第 k 层的顶点的时候，我们需要把第 k 层的顶点记录下来，稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以，我们用这个队列来实现记录的功能。

prev用来记录搜索路径。当我们从顶点 s 开始，广度优先搜索到顶点 t 后，prev 数组中存储的就是搜索的路径。不过，这个路径是反向存储的。prev[w] 存储的是，顶点 w 是从哪个前驱顶点遍历过来的。比如，我们通过顶点 2 的邻接表访问到顶点 3，那 prev[3] 就等于 2。为了正向打印出路径，我们需要递归地来打印，你可以看下 print() 函数的实现方式。
*/

public void bfs(int s, int t) {
  if (s == t) return;
  boolean[] visited = new boolean[v];
  visited[s]=true;
  Queue<Integer> queue = new LinkedList<>();
  queue.add(s);
  int[] prev = new int[v];
  for (int i = 0; i < v; ++i) {
    prev[i] = -1;
  }
  while (queue.size() != 0) {
    int w = queue.poll();
   for (int i = 0; i < adj[w].size(); ++i) {
      int q = adj[w].get(i);
      if (!visited[q]) {
        prev[q] = w;
        if (q == t) {
          print(prev, s, t);
          return;
        }
        visited[q] = true;
        queue.add(q);
      }
    }
  }
}
 
private void print(int[] prev, int s, int t) { // 递归打印 s->t 的路径
  if (prev[t] != -1 && t != s) {
    print(prev, s, prev[t]);
  }
  System.out.print(t + " ");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

资料摘抄

《极客时间》数据结构与算法之美
深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构的。这是因为，图这种数据结构的表达能力很强，大部分涉及搜索的场景都可以抽象成“图”。

深度优先搜索算法和广度优先搜索算法，既可以用在无向图，也可以用在有向图上。

广度优先搜索和深度优先搜索是图上的两种最常用、最基本的搜索算法
简单粗暴，没有什么优化，所以，也被叫作暴力搜索算法；这两种搜索算法仅适用于状态空间不大，也就是说图不大的搜索。

深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。在执行效率方面，深度优先和广度优先搜索的时间复杂度都是 O(E)，空间复杂度是 O(V)。

单源最短路径

杂

有向无回路图单源最短路径】

Bellman-Ford算法】

Dijkstra算法】