图

start:

图的存储

邻接矩阵

一般适合于顶点数目不超过1k 的题目

邻接表

顶点数目大于 1k 的题目

实现

vector实现

开一个 vector数组 Adj[N]其中N为顶点个数。

• 如果邻接表只存储每条边的终点编号，而不存储权重，则vector中的元素类型可以直接定义为int。

• 如果需要存储边的权重，则把元素类型改为结构体Node。

  结构体的初始化可以定义构造函数。

  struct Node
  {
      int v, w;//v 为节点，w 为权重。
      Node(int _v, int _w) : v(_v), w(_w);
      //写出构造函数可以赋值。
  };
  //eg
  Adj[i].push_back(Node(3,4));图的遍历

遍历的伪代码

深度优先搜索

DFS(u)
{
    vis[u] = true;// u 被访问。
    for(/*从顶点u出发能够到达的所有顶点vi*/)
    {
        if(vis[vi] = false)//如果这个节点没有被访问
        {
            DFS[vi]；//访问 vi 能够到达的节点
        }
    }
}
DFSTrave(G)
{
    for(/* G 中所有顶点*/) //枚举
    {
        if(vis[u] == false)
        {
            DFS(u);//访问 u 能够到达的节点
        }
    }
        
}

广度优先搜索

#include <queue>
···
BFS(u)
{
    queue q;
    vis[u] = true;
    //定义并让u入队
    
    while(q.size() ！= 0)
    {
        int top = q.front();//读入，并取出队列 q 的队首元素u
        q.pop();
        
        for(/* 从 u 出发遍历能到达的节点 vi */)
        {
            if(vis[vi] = false)//若未曾入队，则入队
            {
                vis[vi] = true;
                q.push(vi);
            }
        }
    }
    
}
BFSTrave(G)
{
    for(/* G 的所有顶点 u*/)
    {
        if(vis[u] == false)
        {
            BFS(u);// 遍历 u 所在的连通块
        }
    }
}

遍历的实现

DFS 实现

• 邻接矩阵

#include <string.h>
int n, G[maxn][maxn];// n 为节点数，maxn 最大定点数
bool vis[maxn];

void DFS(int u, int depth)
{
    vis[u] = true; // 设置 u 已经被访问
    
    // 对节点 u 特殊执行阶段
    for(int i = 0;i < n; i++)
    {
        if(vis[i] ==false && G[u][v] != INF) // 枚举 i 可以到达且未被访问的所有顶点。
        {
            DFS(v, depth+1);// 访问 i 深度 +1。
        }
    }
    
}
void DFSTrave()
{
    for(int u = 0; u < n; u++)
    {
        if(vis[u] == false)
        {
            DFS(u,1);// 初始为第 1 层
        }
    }
}
int main()
{
    ···
    memset(vis, 0, sizeof(vis));
    ···
}

• 邻接表

#include <vector>
#include <string.h>//memset 所在的库函数

vector<int> Adj[maxn];
int n;//顶点数
bool vis[maxn];

void DFS(int u, int depth)
{
    vis[u] = true;
    
    /*在这里对 u 操作*/
    for(int i = 0; i<Adj.size(); i++)
    {
        int v = Adj[u][i];
        if(vis[v] == false)
        {
            DFS(v, depth + 1);
        }
    }// end for i
}

void DFSTrave()
{
    for(int u = 0; u < n; u++)
    {
        if(vis[u] == false)
        {
            DFS(u, 1);
        }
    }
}

BFS 实现

• 邻接矩阵

#include <queue>
int n, G[maxn][maxn]; // n 为顶点数
bool inq[maxn] = {false};

void BFS(int u)
{
    queue<int> q;
    q.push(u);
    while(q.size != 0)
    {
        int top = q.front();
        q.pop();
        for(int i = 0; i < n; i++)
        {
            if(inq[i] == false&&G[u][v] != INF)
            {
                q.push(v);
                inq[v] = true;
                /*
                	进行特殊操作
                */
            }
        }
    } // end while
}

void BFSTrave()
{
    for(int u = 0; u < n; u++) // 遍历
    {
        if(inq[u] == false) // 未入队且可达
        {
            BFS(u);
        }
    }
}

-邻接表版本

#include <vector>
#include <queue>

vector<int> Adj[maxn];
int n;
bool inq[maxn] = {false};

void BFS(int u)
{
    queue<int> q;
    q.push(u);
    inq[u] = true;
    while(!q.empty())
    {
        int top = q.front();
        q.pop();
        for(int i = 0; i<Adj[u].size; i++)
        {
            int v = Adj[u][i];
            if(inq[v] == false)
            {
                q.push(v);
                inq[v] = true;
            }
        }
    }//end while
}

void BFSTrave()
{
    for(int u = 0; u < n; u++)
    {
        if(inq[u] == false)
        {
            BFS(u);
        }
    }
}

注：当题目要求输出节点的层号时，只需将vector<>中存储的元素换成结构体即可，结构体包含节点编号和层号。遍历时更新层号信息，子节点时父节点的层号+1结构体如下：

struct node
{
    int v;
    int layer;
};

最短路径

dijkstra 算法

练习题：PAT A1003，A1030，A1018，A1072，A1087。