数据结构笔记(六): 图的存储与遍历

发布于 / 程序猿 / 0 条评论

分别使用邻接矩阵与邻接表存储图来实现图的深度优先遍历和广度优先遍历若文中存在错误,敬请指出,感谢阅读。

这次先上代码后讲基础知识,给定一个无向无权图(不一定联通),输出图的深度优先遍历和广度优先遍历

演示

个人感觉有向图的遍历更好理解,所以演示就以有向联通图为例吧。

  • 基本图

  • 深度遍历(从0开始)


  • 广度遍历(从0开始)


代码

邻接矩阵存储

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int G[maxn][maxn]; // 邻接矩阵
bool vis1[maxn]; // dfs标记数组
bool vis2[maxn]; // bfs标记数组
int n, m; // 点数与边数

void init() // 初始化
{
    memset(G, 0, sizeof(G)); // 为0表示无边相连
    memset(vis1, 0, sizeof(vis1)); // 为0表示未被访问
    memset(vis2, 0, sizeof(vis2));
}

void dfs(int u) // 深度优先遍历
{
    cout << u << " ";
    vis1[u] = true;
    for (int i = 1; i <= n; ++i)
    {
        if (!vis1[i] && G[u][i]) // 没有被访问过且有边
            dfs(i);
    }
}

void bfs(int u) // 广度优先遍历
{
    int now = u;
    vis2[now] = true;
    queue<int>Q;
    Q.push(now);
    while (!Q.empty())
    {
        now = Q.front();
        Q.pop();
        cout << now << " ";
        for (int i = 1; i <= n; ++i)
        {
            if (!vis2[i] && G[now][i]) // 没有被访问过且有边
            {
                Q.push(i);
                vis2[i] = true;
            }
        }
    }
}

int main()
{
    while (cin >> n >> m)
    {
        init();
        int x, y;
        for (int i = 1; i <= m; ++i)
        {
            cin >> x >> y;
            G[x][y] = G[y][x] = 1; // 无向边
        }
        cout << "深度优先遍历:" << endl;
        for (int i = 1; i <= n; ++i)
        {
            if (!vis1[i])
                dfs(i);
        }
        cout << endl;
        cout << "广度优先遍历:" << endl;
        for (int i = 1; i <= n; ++i)
        {
            if (!vis2[i])
                bfs(i);
        }
        cout << endl;
    }
    return 0;
}

/*
9 7
1 2
1 4
2 6
2 5
4 7
3 8
3 9
深度优先遍历:
1 2 5 6 4 7 3 8 9
广度优先遍历:
1 2 4 5 6 7 3 8 9
*/

邻接表存储(链表)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 1010;
bool vis1[maxn]; // dfs标记数组
bool vis2[maxn]; // bfs标记数组
int n, m; // 点数与边数

struct Edge
{
    int to;
    Edge * next;
    Edge(int a = 0, Edge * b = NULL):to(a), next(b){} // 默认构造函数
};

Edge * Vertex[maxn] = {NULL}; // 初始化为空

void addedge(int x, int y) // “连边”
{
    Edge * pt = new Edge(y, Vertex[x]); // 总是从第一个插入
    Vertex[x] = pt;
}

void init() // 初始化
{
    memset(vis1, 0, sizeof(vis1)); // 为0表示未被访问
    memset(vis2, 0, sizeof(vis2));
}

void dfs(int u) // 深度优先遍历
{
    cout << u << " ";
    vis1[u] = true;
    for (Edge * pt = Vertex[u]; pt; pt = pt->next)
    {
        if (!vis1[pt->to])
            dfs(pt->to);
    }
}

void bfs(int u) // 广度优先遍历
{
    int now = u;
    vis2[now] = true;
    queue<int> Q;
    Q.push(now);
    while (!Q.empty())
    {
        now = Q.front();
        Q.pop();
        cout << now << " ";
        for (Edge * pt = Vertex[now]; pt; pt = pt->next)
        {
            if (!vis2[pt->to])
            {
                Q.push(pt->to);
                vis2[pt->to] = true;
            }
        }
    }
}

int main()
{
    while (cin >> n >> m)
    {
        init();
        int a, b;
        for (int i = 1; i <= m; ++i)
        {
            cin >> a >> b;
            addedge(a, b); // 无向边
            addedge(b, a);
        }
        cout << "深度优先遍历:" << endl;
        for (int i = 1; i <= n; ++i)
        {
            if (!vis1[i])
                dfs(i);
        }
        cout << endl;
        cout << "广度优先遍历:" << endl;
        for (int i = 1; i <= n; ++i)
        {
            if (!vis2[i])
                bfs(i);
        }
        cout << endl;
    }
    return 0;
}

/*
9 7
1 2
1 4
2 6
2 5
4 7
3 8
3 9
深度优先遍历:
1 4 7 2 5 6 3 9 8
广度优先遍历:
1 4 2 7 5 6 3 9 8
*/

邻接表存储(顺序表)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 1010;
bool vis1[maxn]; // dfs标记数组
bool vis2[maxn]; // bfs标记数组
int n, m; // 点数与边数

vector <int> G[maxn];

void init() // 初始化
{
    memset(vis1, 0, sizeof(vis1)); // 为0表示未被访问
    memset(vis2, 0, sizeof(vis2));
}

void dfs(int u) // 深度优先遍历
{
    cout << u << " ";
    vis1[u] = true;
    for (int i = 0; i < G[u].size(); ++i)
    {
        if (!vis1[G[u][i]])
            dfs(G[u][i]);
    }
}

void bfs(int u) // 广度优先遍历
{
    int now = u;
    vis2[now] = true;
    queue<int> Q;
    Q.push(now);
    while (!Q.empty())
    {
        now = Q.front();
        Q.pop();
        cout << now << " ";
        for (int i = 0; i < G[now].size(); ++i)
        {
            if (!vis2[G[now][i]])
            {
                Q.push(G[now][i]);
                vis2[G[now][i]] = true;
            }
        }
    }
}

int main()
{
    while (cin >> n >> m)
    {
        init();
        int x, y;
        for (int i = 1; i <= m; ++i)
        {
            cin >> x >> y;
            G[x].push_back(y);
            G[y].push_back(x);
        }

        // 按照大小顺序依次输出
        //for(int i=1;i<=n;++i)
        //    sort(G[i].begin(),G[i].end());

        cout << "深度优先遍历:" << endl;
        for (int i = 1; i <= n; ++i)
        {
            if (!vis1[i])
                dfs(i);
        }
        cout << endl;
        cout << "广度优先遍历:" << endl;
        for (int i = 1; i <= n; ++i)
        {
            if (!vis2[i])
                bfs(i);
        }
        cout << endl;
    }
    return 0;
}

/*
9 7
1 2
1 4
2 6
2 5
4 7
3 8
3 9
深度优先遍历:
1 2 6 5 4 7 3 8 9
广度优先遍历:
1 2 4 6 5 7 3 8 9
*/

基础知识

图的存储表示方法有很多种,常用的有 2 种:邻接矩阵(adjacency matrix)、邻接表(adjacencylist)。

邻接矩阵

在邻接矩阵存储方法中,除了一个记录各个顶点信息的顶点数组外,还有一个表示各个顶点之间关系的矩阵,称为邻接矩阵(adjacency matrix)。设 G(V, E)是一个具有 n 个顶点的图,则图的邻接矩阵是一个 n×n 的二维数组,在本书中用 Edge[n][n]表示,它的定义为:

例如,下面的图 1.15 给出了图 1.1(a)中的无向图 G1(V, E)及其邻接矩阵表示。在图 1.15 中,为了表示顶点信息,特意将顶点的标号用字母 A、B、C、D、E 和 F 表示,各顶点的信息存储在顶点数组中,如图(b)所示,注意在 C/C++语言中,数组元素下标是从 0 开始计起的。G1的邻接矩阵如图(c)所示,从该图可以看出,无向图的邻接矩阵是沿主对角线对称的。

又如,下面的图 1.16 给出了图 1.1(b)中的有向图 G2(V, E)及其邻接矩阵表示。同样,为了表示顶点信息,在图 1.16 中特意将顶点的标号用字母 A、B、C、D、E、F 和 G 表示,各顶点的信息存储在顶点数组中,如图(b)所示。G2的邻接矩阵如图(c)所示,从该图可以看出,有向图的邻接矩阵不一定是沿主对角线对称的。

注意:如果图中存在自身环(self loop,连接某个顶点自身的边)和重边(multiple edge 多条边的起点一样,终点也一样,也称为平行边,parallel edge)的情形,则无法用邻接矩阵存储。

从图的邻接矩阵可以获得什么信息?对无向图的邻接矩阵来说,如果 Edge[i][j] = 1,则表示顶点 i 和顶点 j 之间有一条边。而对有向图的邻接矩阵来说,如果 Edge[i][j] = 1,则表示存在从顶点 i 到顶点 j 有一条有向边,i 是起点,j 是终点。

邻接表

尽管 ACM/ICPC 中绝大多数图论题目在求解时可以采用邻接矩阵存储图,但由于邻接矩阵无法存储带自身环(或重边)的图,所以有时不得不采用邻接表来存储图。另外,当图的边数(相对于邻接矩阵中的元素个数,即 n×n)较少时,使用邻接矩阵存储会浪费较多的存储空间,而用邻接表存储可以节省存储空间。

所谓邻接表(adjacency list),就是把从同一个顶点发出的边链接在同一个称为边链表的单链表中。边链表的每个结点代表一条边,称为边结点。每个边结点有 2 个域:该边终点的序号,以及指向下一个边结点的指针。在邻接表中,还需要一个用于存储顶点信息的顶点数组

例如,图 1.19(a)所示的有向图对应的邻接表如图(b)所示。在顶点数组中,每个元素有两个成员:一个成员用来存储顶点信息;另一个成员为该顶点的边链表的表头指针,指向该顶点的边链表。如果没有从某个顶点发出的边,则该顶点没有边链表,因此表头指针为空,如图1.19(b)中的顶点 G。在该图中,如果指针为空,则用符号“∧”表示。

在邻接表每个顶点的边链表中,各边结点所表示的边都是从该顶点发出的边,因此这种邻接表也称为出边表。采用邻接表存储图时,求顶点的出度很方便,只需要统计每个顶点的边链表中边结点的个数即可,但在求顶点的入度时就比较麻烦。

在图 1.19(b)中,顶点 B 的边链表有 3 个边结点,分别表示边<B, F><B, E><B, C>,因此顶点 B 的出度为 3;顶点 C 的边链表中只有 1 个边结点,表示边<C, E>,因此顶点 C 的出度为 1。

如果需要统计各顶点的入度,可以采用逆邻接表存储表示图。所谓逆邻接表,也称为入边表,就是把进入同一个顶点的边链接在同一个边链表中。

例如,图 1.20(a)所示的有向图对应的逆邻接表如图(b)所示。在图 1.20(b)中,顶点 B 的边链表有 2 个边结点,分别表示边<E, B><A, B>,因此顶点 B 的入度为 2;顶点 C 的边链表中也有 2个边结点,分别表示边<D, C><B, C>,因此顶点 C 的入度也为 2。

因为无向图中的边没有方向性,所以无向图的邻接表没有入边表和出边表之分。在无向图的邻接表中,与顶点 v 相关联的边都链接到该顶点的边链表中。无向图的每条边在邻接表里出现 2次。例如,图1.21(a)所示的无向图对应的邻接表如图(b)所示。

在图 1.21(b)中,顶点 B 的边链表中有 5 个边结点,分别表示边(B, F)、(B, E)、(B, D)、(B, C)和(B, A),因此顶点 B 的度为 5;顶点 C 的边链表中有 4 个边结点,分别表示边(C, E)、(C, D)、(C,B)和(C, A),因此顶点 C 的度为 4。边(B, C)分别出现在顶点 B 和顶点 C 的边链表中。

说明:如果用邻接表存储有向网或无向网,则在边结点中还应增加一个成员,用于存储边的权值。

基础知识讲的挺详细的,来自于《图论算法理论、实现及应用》一书。

最后,致敬迅哥


The end.
2017-11-11 星期六

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(六): 图的存储与遍历
Not Comment Found