数据结构之图：简介

1. 概念

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

2. 分类

图的种类

2.1 按照边的类型分类

图的边有两种类型：

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

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

1. 无向图(Undigraph)：任意两顶点之间的边都是无向边

   • 无向图表示：
   • 顶点集合：
   • 边集：

2. 有向图(Digraph)：任意两顶点之间的边都是有向边

   • 无向图表示：
   • 顶点集合：
   • 边集：

3. 混合图(Mixed Graph)：有向边与无向边同时存在的图。

2.2 按照边数多少分类

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

2.3 按照边上是否带有数值

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

3. 表示法

3.1 对象顶点和边关系

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

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

3.2 表示法

图的表示法有以下三种

1. 邻接表(Adjacency List)
2. 邻接矩阵(Adjacency Matrix)
3. 关联矩阵(Incidence Matrix)

图的表示法

说明

1. 无向图边数组是对称矩阵。
2. 邻接矩阵和关联矩阵合适稠密图；邻接表合适稀疏图。
3. 邻接矩阵和关联矩阵使用数值1表示顶点存在边，数值0表示顶点不存在边；网(Network)使用权值表示存在边，使用∞表示不存在边。

3.3 存储方式

No.	类型	C++表示方式
1	邻接表(Adjacency List)	vector<顶点数据类型>[顶点数]
2	邻接矩阵(Adjacency Matrix)	顶点数据类型 [顶点数][顶点数]
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;
}

4. 图的遍历(Traversing Graph)

4.1 基本原理

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

2. 广度优先遍历(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;
}