考研数据结构 07 图

发布于 2021-11-12  59 次阅读


一、图的基本概念

1.1 图的定义

  图G由顶点集V和边集E组成,记为G = (V, E),其中V(G)表示图G中顶点的有限非空集;E(G)表示图G中顶点之间的关系(边集合)。若V={v1, v2...vn},则用|V|表示图G中顶点的个数,E={(u, v)| u∈V, v ∈ V},用|E|表示图G中的边数。

1.1.1 有向图

  不多解释,有方向指向的图。

1.1.2 无向图

  同上。

1.1.3 简单图、多重图

  如果一个图满足:

  1. 不存在重复的边;
  2. 不存在顶点到自身的边。

那么该图就称为简单图。若图G中两个顶点之间的边数大于1条,又允许顶点通过一条边和自身相连,则图G称为多重图。

1.1.4 完全图

  对于无向图,任意两个顶点之间都存在边。对于有向图,表述则是:总能从一个顶点到达另一个顶点。

1.1.5 子图

  有两个图G = (V, E)和G1 = (V1, E1),若V1是V的子集,且E1是E的子集,则称图G1是图G的子图。

1.1.6 通道、连通图和连通分量

  在无向图中,若顶点v到顶点w有路径存在,则称v和w是连通的。若图G中任意两个顶点都是连通的,则称图G为连通图,否则称为非连通图。无向图中的极大连通子图,称为连通分量。

1.1.7 强连通图、强连通分量

  在有向图中,若一对顶点w和v,若可从w到v、可从v到w。那么w和v之间是强连通的。其余概念与上述连通图相同。

1.1.8 生成树、生成森林

  对于一个连通图G,若其一个子图G1是一颗包含G所有顶点的树,则该子图称为G的生成树。生成树是包含图G所有顶点的极小连通子图。

1.1.9 顶点的度、入度和出度

  在无向图中,顶点v的度是指依附于顶点v的边的条数。
  在有向图中,出度是从v出发的边数,入度是到达v的边数。

1.1.10 边、权和网

  在图中,每条边上都可以标上某种数值,该数值被称为边的权值。这种边上带权值的图称为带权图,也称为网。

1.1.11 稀疏图、稠密图

  边很少的图叫稀疏图,边很多的图叫稠密图。一般当图G满足|E|<|V|log|V|,可以将图G是为稀疏图。

1.1.12 路径、路径长度和回路

  顶点vp到顶点vq之间的一条路径是指顶点序列vp...vi...vq。路径上的数目称为路径长度。第一个顶点和最后一个顶点相同的路径,称为回路或环。

1.1.13 简单路径、简单回路

  顶点不重复,即简单。

1.1.14 距离

  从顶点u出发到顶点v的最短路径若存在,则此路径的长度称为从u到v的距离。若不存在路径,则距离为无穷。

1.1.15 有向树

  一个顶点入度为0,其余顶点的入度均为1的有向图,称为有向树。

二、图的存储及基本操作

2.1 邻接矩阵法

  用一个一维数组存放图中的顶点信息,用一个二维数组存放图中的的信息。存储顶之间邻接关系的二维数组称为邻接矩阵。

struct MGraph
{
    int vertex[num];
    int graph[num][num];
    int vexnum, arcnum;
    // 当前节点的顶点数 和 弧数
};

  在上述图中,我们可以通过graph[1][3] = 1表示从vertex[1]可以到达vertex[3](下标);同样,使用[2][1] = 0表示不可到达。这里需要区分有向图和无向图,无向图是对称的,有向图则不是。

2.2 邻接表法

  为了解决邻接矩阵利用率低的问题,这里使用邻接表来完成。

// 邻接节点
struct ArcNode
{
    int adjvex; // 邻接节点编号
    ArcNode* next;  // 指向下一个节点
}

// 邻接表
struct AdjList
{
    std::list<ArcNode*> ArcList;    // 顶点列表
    int vexnum, arcnum;
    // 当前节点的顶点数 和 弧数
}

  为了更好地理解邻接表与邻接矩阵之间的转化,我们给出如下例题:
Description
  给一个带权有向图的邻接矩阵表示,将之转换为邻接表的表示,并输出对应的邻接表
Input
  第一行:两个整数m(图的节点数),n(图的边数)(0 < n,m < 100,)。余下n行:n*n矩阵,代表矩阵表示下的图(其中以非零表示有链接,数字间以空格隔开)
Output
  输出有m行,对应m个节点的邻接表示下的节点连接情况
Sample Input
6 10
0 5 0 7 0 0
0 0 4 0 0 0
8 0 0 0 0 0
0 0 5 0 0 6
0 0 5 0 0 0
3 0 0 0 1 0
Sample Output
0:1 3
1:2
2:0
3:2 5
4:2
5:0 4

2.3 十字链表与邻接多重表

p 208; 后面要考再补充。

三、图的遍历

3.1 广度优先搜索 BFS

题目描述
  图的广度优先搜索类似于树的按层次遍历,即从某个结点开始,先访问该结点,然后访问该结点的所有邻接点,再依次访问各邻接点的邻接点。如此进行下去,直到所有的结点都访问为止。在该题中,假定所有的结点以“A”--“Z”中的若干字符表示,且要求结点的访问顺序根据录入的顺序进行访问。如果结点录入的顺序为HUEAK,要求从H开始进行广度优先搜索,则可能的搜索结果为:H->E->A->U->K.
输入
  第一行为一个整数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,否则为相应的边的长度。最后一行为一个字符,表示要求进行广度优先搜索的起始顶点。
输出
  用一行输出广度优先搜索结果,起始点为给定的顶点。
样例输入
5
HUEAK
0 0 2 3 0
0 0 0 7 4
2 0 0 0 0
3 7 0 0 1
0 4 0 1 0
H
样例输出
HEAUK

#include <iostream>
#include <vector>
#include <string>
#include <deque>

// 节点元素
struct Node
{
    int id;         // 节点序号
    bool flag;      // 是否访问过
    char ele;       // 存储的元素
    std::vector<int>list;   // 当前节点的路径, 0表示不可到达[i]节点, n表示可到达[i]节点

    // 构造函数
    Node():
        flag{ true }, ele{ '\0' }
    { }
};

/*
    BFS搜索函数

    返回值:BFS遍历的结果
    参数1:顶点数组
    参数2:搜索起点
*/
std::string BFS(std::vector<Node> Vertex, 
                Node Begin);

int main()
{
/* ========== Section I : 数据准备 ========== */
    // 图的大小
    int size{ 0 };
    // 顶点元素
    std::string Vertex_ele;
    // 顶点
    std::vector<Node> Vertex;

    // 录入大小和顶点
    std::cin >> size >> Vertex_ele;
    // 顶点大小改变
    Vertex.resize(size);

    // 读入数据
    for (int i = 0; i < size; ++i)
    {
        // ele赋值
        Vertex[i].ele = Vertex_ele.at(i);
        Vertex[i].id = i;

        // list赋值
        for (int j = 0; j < size; ++j)
        {
            int input{ 0 };
            std::cin >> input;
            Vertex[i].list.push_back(input);
        }
    }

    // 开始搜索的元素,即搜索起点
    char BeginCh;
    std::cin >> BeginCh;

/* ========== Section II : BFS ========== */
    // 定位搜索起点
    for (int i = 0; i < size; ++i)
    {
        if(Vertex[i].ele == BeginCh)
        {
            std::cout << BFS(Vertex, Vertex[i]);
            break;
        }
    }

    return 0;
}

std::string BFS(std::vector<Node> Vertex, Node Begin)
{
    // BFS遍历队列
    std::deque<Node> Trans;

    Trans.push_back(Begin);

    // 返回值
    std::string re;

    // 开始遍历
    while(!Trans.empty())
    {
        // 队首
        Node head = Trans.front();
        Trans.pop_front();

        // 访问元素 这里需要判断是否可以访问
        if (Vertex[head.id].flag == true)
        {
            re.push_back(head.ele);
        }
        else
        {
            continue;
        }
        // 队首节点flag置0
        Vertex[head.id].flag = false;

        // 查找head可到达的节点
        for (int i = 0; i < Vertex.size(); ++i)
        {
            if (head.list[i] != 0               // 可到达
                && Vertex[i].flag == true)      // 未访问
            {
                Trans.push_back(Vertex[i]);
            }
        }
    }

    return re;
}

3.1.1 BFS性能分析

空间复杂度

  O(vertex),需要至多size == vertex的队列。

时间复杂度

  O(vertex),最坏情况下每个点都要入队一次。

3.1.2 BFS最短路径

  利用广度优先搜索总是按距离遍历的特性,我们可以利用它来求最短路径。下面我们计算从vBegin到vEnd的距离,即我们只需要在while循环里面加入一个distence++即可。但是需要注意的是,我们这里遍历,不再是每次取出头结点遍历,而是取出队列里面所有节点(即一层)循环一次,即我们使用层次遍历计算距离。

int BFS(std::vector<Node> Vertex, Node Begin)
{
    // BFS遍历队列
    std::deque<Node> Trans;

    Trans.push_back(Begin);

    // 返回值
    std::string re;

    int distance = 0;

    // 开始遍历 - 每次循环遍历一层
    while(!Trans.empty())
    {   
        // 取出队列所有元素
        std::list<Node> nodes = all nodes in deque(Trans);

        // 判断节点是否可以遍历
        for (auto node : nodes)
        {
            // 判断是否可以遍历
            if (node.flag == true)
            {
                // node flag置0,并随后访问
                node.flag = false;
            }
            else if (node.flag == false)
            {
                // node 移除出list
                nodes.remove(node);
            }
        }

        // 访问所有节点
        for (auto node : nodes)
        {
            // 访问,并将其可到达的节点压入队列

            if (node.list[i] != 0               // 可到达
                && Vertex[i].flag == true)      // 未访问
            {
                Trans.push_back(Vertex[i]);
            }
        }

        // 每一层的距离
        distance++;
    }

    return distance;
}

3.2 深度优先搜索 DFS

题目描述
  图的深度优先搜索类似于树的先根遍历,即从某个结点开始,先访问该结点,然后深度访问该结点的第一棵子树,依次为第二顶子树。如此进行下去,直到所有的结点都访问为止。在该题中,假定所有的结点以“A”至“Z”中的若干字符表示,且要求结点的访问顺序根据录入的顺序进行访问。如果结点录入的顺序为HUEAK,从H开始进行深度优先搜索,则可能的搜索结果为:H->A->K->U>E.
输入
  第一行为一个整数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,否则为相应的边的长度。最后一行为一个字符,表示要求进行深度优先搜索的起始顶点。
输出
  用一行输出深度优先搜索结果,起始点为给定的顶点。
样例输入
5
HUEAK
0 0 2 3 0
0 0 0 7 4
2 0 0 0 0
3 7 0 0 1
0 4 0 1 0
H
样例输出
HEAUK

#include <iostream>
#include <vector>
#include <string>
#include <deque>

// 节点元素
struct Node
{
    int id;         // 节点序号
    bool flag;      // 是否访问过
    char ele;       // 存储的元素
    std::vector<int>list;   // 当前节点的路径, 0表示不可到达[i]节点, n表示可到达[i]节点

    // 构造函数
    Node():
        flag{ true }, ele{ '\0' }
    { }
};

std::string ans;    // 遍历结果

/*
    DFS搜索函数

    返回值:void
    参数1:顶点数组
    参数2:当前节点
*/
void DFS(std::vector<Node>& Vertex, Node& node);

int main()
{
/* ========== Section I : 数据准备 ========== */
    // 图的大小
    int size{ 0 };
    // 顶点元素
    std::string Vertex_ele;
    // 顶点
    std::vector<Node> Vertex;

    // 录入大小和顶点
    std::cin >> size >> Vertex_ele;
    // 顶点大小改变
    Vertex.resize(size);

    // 读入数据
    for (int i = 0; i < size; ++i)
    {
        // ele赋值
        Vertex[i].ele = Vertex_ele.at(i);
        Vertex[i].id = i;

        // list赋值
        for (int j = 0; j < size; ++j)
        {
            int input{ 0 };
            std::cin >> input;
            Vertex[i].list.push_back(input);
        }
    }

    // 开始搜索的元素,即搜索起点
    char BeginCh;
    std::cin >> BeginCh;

/* ========== Section II : BFS ========== */
    // 定位搜索起点
    for (int i = 0; i < size; ++i)
    {
        if(Vertex[i].ele == BeginCh)
        {
            DFS(Vertex, Vertex[i]);
            break;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

void DFS(std::vector<Node>& Vertex, Node& node)
{
    // false 则返回
    if (!node.flag) return;

    // 访问元素
    ans.push_back(node.ele);

    // 标记flag为flase
    node.flag = false;

    // 遍历可到达的点
    for (int i = 0; i < Vertex.size(); i++)
    {
        if (node.list[i] != 0)
        {
            DFS(Vertex, Vertex[i]);
        }
    }
}

3.2.1 DFS性能分析

空间复杂度

  O(vertex),需要借助栈实现提柜。

时间复杂度

  以邻接矩阵表示时,查找每个顶点所需的时间为O(vertex),总时间复杂度为O(vertex2);以邻接表储存时,查找所有顶点所需时间为O(Edge),总时间为O(Edge2)。

四、图的应用

4.1 最小生成树

4.1.1 Prim算法

void Prim(G, T)
{
    /*
        T : 树
        U : 用于统计顶点是否全部加入树中
    */
    T = nullptr;        // 初始化树,使其为空
    U = { w };          // 将任意一点w,添加入树

    while (U.size() != G.size())  
    {
        step 1: 寻找当前T集合与G图之间权值最小的两个点,即Tn和Gn。
        step 2: 边Tn-Gn 加入 T中。
        step 3: 顶点Gn 加入 U中。
    }
}

4.1.2 Kruskal算法

void Kruskal(V, T)
{
    /*
        E : 边集合,用于存放所有的边以及其长度
    */
    T = V;          // 初始化树,仅含顶点
    CC = n;         // 联通分量 = 顶点数
    while (CC > 1)
    {
        step 1: 从E中选出最短的边v-u。
        step 2: 如果 u和v属于T中不同的联通分量,则此边加入T树、联通分量数CC--。
    }
}

4.1.3 比较

图1

  在Prim算法中,时间复杂度为O(V2);在Kruskal算法中,时间复杂度为O(E*logE)。