数据结构之图：简介

1. 概念

图是一种复杂的非线性结构。图G由两个集合V(顶点Vertex)和E(边Edge)组成，定义为G=(V，E)

2. 分类

2.1 按照边的类型分类

图的边有两种类型：

No.	边的类型	说明
1	无向边(Undirected Edge)	顶点`V1`到顶点`V2`的边没有方向。用无序偶对 $(V1,V2)$ 表示。
2	有向边/弧(Directed Edge)/(Arc)	顶点`V1`到顶点`V2`的边有方向。用有序偶对 $<V1,V2>$ 表示。

权(Weight)：与图的边或者弧关联的数值(权值可正可负可为零)

按照边的类型，图可以分为三类：

无向图(Undigraph)：任意两顶点之间的边都是无向边
- 无向图表示： $G=(V,E)$
- 顶点集合： $V(G)=\{V1,V2,V3,V4,V5\}$
- 边集： $E(G)=\{(V1,V2),(V1,V4),(V2,V3),(V2,V5),(V3,V4),(V3,V5),(V4,V5)\}$
有向图(Digraph)：任意两顶点之间的边都是有向边
- 无向图表示： $G=(V,E)$
- 顶点集合： $V(G)=\{V1,V2,V3\}$
- 边集： $E(G)=\{<V1,V2>,<V2,V3>,<V3,V1>,<V1,V3>\}$
混合图(Mixed Graph)：有向边与无向边同时存在的图。

2.2 按照边上是否带有数值

有权图/网(Network)：图的边或者弧有关联的数值
无权图：图的边或者弧有关联的数值

2.3 按照边数多少分类

稀疏图(Sparse Graph)
有很少条边或弧(边数 $E$ 远小于顶点数平方 $V^2$ )
稠密图(Dense Graph)
有很多条边或弧(边数 $E$ 接近顶点数平方 $V^2$ )

2.4 其他

图的种类

简单图(Simple Graph)：没有自环边没有平行边的图。
- 自环边：指向自己的边称为自环边。
- 平行边：两个节点之间的多条边成为平行边。
完全图(Complete Graph):每对顶点之间都恰连有一条边的图。
完全图通常使用 $K_n$ ，其中 $n$ 表示定点数，例如 $K_4$ 。
完全图属于简单图的特例。
多重图(Multigraph)：含有平行边不含有自环边的图。
伪图(Pseudograph)：含有平行边和自环边的图。
二分图/二部图/偶图(Bipartite graph): 顶点可以分成两个不相交的集使得在同一个集内的顶点不相邻（没有共同边）的图。

一个图所有的节点不一定全部相连。
图的连通性：一个图可以有多个群体，群体中的点是连同的，不同群体间的点不连通；

2.5 总结

在计算机中通常讨论的图是稀疏的简单图。所以一般只分析以下四种。

No.	分类	简写
1	无方向/无权重	U/U
2	无方向/有权重	U/W
3	有方向/无权重	D/U
4	有方向/有权重	D/W

四种基本图的分类演示visualgo

3. 表示法

3.1 对象顶点和边关系

图由顶点和边构成，这样就存在两种关系。

邻接关系(Adjacency)：顶点与顶点的关系
关联关系(Incidence)：顶点以及与它相关的边的关系

顶点的度(degree)：顶点相邻边数。

3.2 表示法

图的表示法有以下三种

邻接表(Adjacency List)
邻接矩阵(Adjacency Matrix)
关联矩阵(Incidence Matrix)

图的表示法

说明

无向图边数组是对称矩阵。
邻接矩阵和关联矩阵合适稠密图；邻接表合适稀疏图。实际中多数情况的图都是稀疏图。
邻接矩阵和关联矩阵使用数值1表示顶点存在边，数值0表示顶点不存在边；网(Network)使用权值表示存在边，使用∞表示不存在边。
简单图的邻接矩阵主对角线全是0

三种图表示法visualgo

3.3 存储方式

No.	类型	C++表示方式
1	邻接矩阵(Adjacency Matrix)	`顶点数据类型 [顶点数][顶点数]`
2	邻接表(Adjacency List)	`vector<顶点数据类型>[顶点数]`
3	关联矩阵(Incidence Matrix)	`顶点数据类型 [顶点数][边数]`

无向图邻接表

#include <bits/stdc++.h>
using namespace std;

int main(){
   int n = 0; // 顶点数
   int m = 0; // 边数
   scanf("%d%d",&n,&m);
   vector<int> vec[n+1]; // 邻接表，下标表示顶点
   for(int i=0;i<m;++i){
       int u = 0;
       int v = 0;
       scanf("%d%d",&u,&v);
       vec[u].push_back(v);
       vec[v].push_back(u);// 无向图两个顶点要各记录一次
   }
   return 0;
}

有向图邻接表

#include <bits/stdc++.h>
using namespace std;

int main(){
   int n = 0; // 顶点数
   int m = 0; // 边数
   scanf("%d%d",&n,&m);
   vector<int> vec[n+1]; // 邻接表，下标表示顶点
   for(int i=0;i<m;++i){
       int u = 0;
       int v = 0;
       scanf("%d%d",&u,&v);
       vec[u].push_back(v);
   }
   return 0;
}

一般情况通常使用邻接表存储图。*

3.4 通用接口

No.	操作	接口
1	获取边数	`int GetEdgeCount()`
2	获取顶点数	`int GetVertexCount()`
3	判断两点两点有边/相邻	`bool HashEdge(int v,int w)`
4	获取顶点`v`的度	`int GetDegree(int v)`
5	获取顶点`v`的邻接顶点	`vector<int> GetAdjVertex(int v)`

4. 图的遍历(Traversing Graph)

4.1 基本原理

深度优先遍历(DFS:Depth First Search)

广度优先遍历(BFS:Breadth First Search)

4.2 基本框架

遍历	技术
DFS	栈/递归(LIFO,先进先出)
BFS	队列(FIFO,先进先出)

DFS基本流程

流程说明
1. 标记当前访问的顶点。
2. 遍历当前的所有邻接顶点，如果未被访问，继续1。

基本框架
非递归方式

void DFS(int v,vector<int>* vec,int n){
  bool visited[n];           // 定义标记顶点是否已访问
  fill_n(visited,n,false);   // 初始化为未访问
  stack<int> s; // 使用栈
  s.push(v);
  while(!s.empty()){
      int now = s.top();
      visited[now] = true;// 出栈时记录已被访问
      s.pop();
      for(int i=0;i<vec[now].size();++i){
          int post = vec[now][i];
          if(!visited[post]){
              s.push(post);
          }
      }
  }
}

递归方式

...
bool visited[n];
fill_n(visited,n,false); // 初始化为未访问
...
int DFS(int v,vector<int>* vec){    
  visited[v] = true;       // 标记v已经访问
  for (int i = 0; i < vec[v].size(); i++) { // 遍历v的邻接点
    int post = vec[v][i];
    if (!visited[post]) {   // 判断邻接点是否访问
      DFS(post, vec);       // 访问邻接点
    }
  }
}

标记访问
经常使用布尔值数组表示是否被访问。

BFS基本流程

流程说明
1. 标记起始顶点已访问，并入队起始顶点
2. 队列判空，非空则出队。
3. 遍历出队顶点的邻接点，依次判断是否已被访问。如果未被访问，标记已访问，并且入队。

基本框架

void BFS(int v,vector<int>* vec,int n){    
  queue<int> q;              // 定义队列
  bool visited[n];           // 定义标记顶点是否已访问
  fill_n(visited,n,false);   // 初始化为未访问
  visited[v] = true;         // 标记v已经访问
  q.push(v);                 // 入队v
  while (!q.empty()) {       // 队列非空
    int now = q.front();     // 取出队首元素
    q.pop();                 // 队首元素出队
    for (int i = 0; i < vec[now].size(); i++) { // 遍历v的邻接点
      int post = vec[now][i];// 取出邻接点
      if (!visited[post]) {  // 判断邻接点是否访问
        visited[post] = true;// 标记邻接点已访问
        q.push(post);        // 邻接点入队
      }
    }
  }
}

说明
入队表示等待访问它的邻接点;
出队表示马上访问它的邻接点;
标记访问
经常使用布尔值数组表示是否被访问。
注意
有时直接使用数组下标作为顶点的标识，所以需要注意顶点是否从0开始。

应用

获取图DFS和BFS后的元素序列。把二维网状结构转变成一维线性结构

vector<int> bfs(vector<int>* vec, int v){
    vector<int> res;
    queue<int> q; // 使用队列
    res.push_back(v);
    q.push(v);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i=0;i<vec[now].size();++i){
            int post = vec[now][i];
            if(find(res.begin(),res.end(),post) == res.end()){
                res.push_back(post); // 入队时记录已被访问
                q.push(post);
            }
        }
    }
    return res;
}
vector<int> dfs(vector<int>* vec, int v){
    vector<int> res;
    stack<int> s; // 使用栈
    s.push(v);
    while(!s.empty()){
        int now = s.top();
        res.push_back(now);// 出栈时记录已被访问
        s.pop();
        for(int i=0;i<vec[now].size();++i){
            int post = vec[now][i];
            if(find(res.begin(),res.end(),post) == res.end()){
                s.push(post);
            }
        }
    }
    return res;
}

1971. 寻找图中是否存在路径

class Solution {
    vector<vector<int>> graph;
    set<int> visited;
public:
    // 递归DFS
    bool DFS(int source, int destination) {
        if(visited.count(source)) return false; // 访问过的节点
        visited.insert(source);
        if(source == destination) return true;
        bool res = false;
        for(auto m:graph[source]){
            res |= DFS(m,destination);
        } 
        return res;
    }
    // 迭代DFS
    bool DFS(int source, int destination) {
        stack<int> s;
        s.push(source);
        while(!s.empty()){
            int n = s.top();s.pop();

            if(visited.count(n)) continue; // 访问过的节点
            visited.insert(n);

            if(n == destination) return true;
            for(auto m:graph[n]) s.push(m);
        }
        return false;
    }
    //  迭代BFS
    bool BFS(int source, int destination) {
        queue<int> q;
        q.push(source);
        while(!q.empty()){
            int n = q.front();q.pop();

            if(visited.count(n)) continue; // 访问过的节点
            visited.insert(n);

            if(n == destination) return true;
            for(auto m:graph[n]) q.push(m);
        }
        return false;
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // 构造邻接表
        graph.resize(n);
        for(auto edge:edges){
            auto v = edge[0];
            auto u = edge[1];
            graph[v].push_back(u);
            graph[u].push_back(v);
        }
        return DFS(source,destination);
    } 
};

三十张图弄懂「图的两种遍历方式」