我家自动化

这个屌丝很懒，什么也没留下！

热门标签

图的遍历

作者：我家自动化 | 2024-08-21 07:31:09

踩

图的遍历

介绍

是从图的某一顶点出发，按照某种搜索方式对图中所有顶点访问一次且仅一次。图的遍历可以解决很多搜索问题，在实际中应用非常广泛。图的遍历根据搜索方式的不同，分为广度优先搜索和深度优先搜索。

一.深度优先遍历

1.1介绍

深度优先搜索（Depth First Search, DFS）是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直走下去，无法行进时，回退到刚刚访问的节点，似“不撞南墙不回头，不到黄河不死心”。深度优先遍历是按照深度优先搜索的方式对图进行遍历。
深度优先遍历秘籍：后被访问的顶点，其邻接点先被访问。
根据深度优先遍历秘籍，后来先服务，可以借助于栈实现。递归本身就是使用栈实现的，因此使用递归方法更方便。

举例

在这里插入图片描述

代码实现1—深度优先遍历邻接矩阵

//深度优先遍历  邻接矩阵
#include <iostream>
using namespace std;

#define MaxVnum 100  //顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;  //顶点的数据类型，根据需要定义
typedef int EdgeType;  //边上权值的数据类型，若不带权值的图，则为0或1
typedef struct {
    VexType Vex[MaxVnum];
    EdgeType Edge[MaxVnum][MaxVnum];
    int vexnum, edgenum; //顶点数，边数
}AMGragh;

int locatevex(AMGragh G, VexType x)
{
    for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标
        if (x == G.Vex[i])
            return i;
    return -1;//没找到
}

void CreateAMGraph(AMGragh& G)//创建无向图的邻接矩阵
{
    int i, j;
    VexType u, v;
    cout << "请输入顶点数：" << endl;
    cin >> G.vexnum;
    cout << "请输入边数:" << endl;
    cin >> G.edgenum;
    cout << "请输入顶点信息:" << endl;
    for (int i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组
        cin >> G.Vex[i];
    for (int i = 0; i < G.vexnum; i++)//初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大
        for (int j = 0; j < G.vexnum; j++)
            G.Edge[i][j] = 0;
    cout << "请输入每条边依附的两个顶点：" << endl;
    while (G.edgenum--)
    {
        cin >> u >> v;
        i = locatevex(G, u);//查找顶点u的存储下标
        j = locatevex(G, v);//查找顶点v的存储下标
        if (i != -1 && j != -1)
            G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1，若有向图G.Edge[i][j]=1
        else
        {
            cout << "输入顶点信息错！请重新输入！" << endl;
            G.edgenum++;//本次输入不算
        }
    }
}

void print(AMGragh G)//输出邻接矩阵
{
    cout << "图的邻接矩阵为：" << endl;
    for (int i = 0; i < G.vexnum; i++)
    {
        for (int j = 0; j < G.vexnum; j++)
            cout << G.Edge[i][j] << "\t";
        cout << endl;
    }
}

void DFS_AM(AMGragh G, int v)//基于邻接矩阵的深度优先遍历
{
    int w;
    cout << G.Vex[v] << "\t";
    visited[v] = true;
    for (w = 0; w < G.vexnum; w++)//依次检查v的所有邻接点
    {
        if (G.Edge[v][w] && !visited[w])//v,w邻接且w未被访问
        {
            DFS_AM(G, w);//从w顶点开始递归深度优先遍历
        }
    }
}

//如果不是一个连通图,还需要进行验证.
void DFS_AM(AMGragh G)
{
    for (int i = 0; i < G.vexnum; i++)//检查未被访问的顶点
    {
        if (!visited[i])
        {
            DFS_AM(G, i);
        }
    }
}

int main()
{
    int v;
    VexType c;
    AMGragh G;
    CreateAMGraph(G);
    print(G);
    cout << "请输入遍历连通图的起始点: ";
    cin >> c;
    v = locatevex(G, c);//查找顶点u的存储下标
    if (v != -1)
    {
        cout << "深度优先搜索遍历连通图结果: " << endl;
        DFS_AM(G);
    }
    else {
        cout << "输入顶点信息错误!请重新输入!" << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

运行结果1

如图: 在这里插入图片描述

在这里插入图片描述

代码实现2—深度优先遍历邻接表

//深度优先遍历  邻接表
#include <iostream>
using namespace std;

const int MaxVnum = 100;//顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;//顶点的数据类型为字符型

typedef struct AdjNode { //定义邻接点类型
    int v; //邻接点下标
    struct AdjNode* next; //指向下一个邻接点
}AdjNode;

typedef struct VexNode { //定义顶点类型
    VexType data; // VexType为顶点的数据类型，根据需要定义
    AdjNode* first; //指向第一个邻接点
}VexNode;

typedef struct {//定义邻接表类型
    VexNode  Vex[MaxVnum];
    int vexnum, edgenum; //顶点数，边数
}ALGragh;

int locatevex(ALGragh G, VexType x)
{
    for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标
        if (x == G.Vex[i].data)
            return i;
    return -1;//没找到
}

void insertedge(ALGragh& G, int i, int j)//插入一条边
{
    AdjNode* s;
    s = new AdjNode;
    s->v = j;
    s->next = G.Vex[i].first;
    G.Vex[i].first = s;
}

void printg(ALGragh G)//输出邻接表
{
    cout << "----------邻接表如下：----------" << endl;
    for (int i = 0; i < G.vexnum; i++)
    {
        AdjNode* t = G.Vex[i].first;
        cout << G.Vex[i].data << ": ";
        while (t != NULL)
        {
            cout << "---->";
            cout << "[" << G.Vex[t->v].data << "]";
            t = t->next;
        }
        cout << endl;
    }
}
void CreateALGraph(ALGragh& G)//创建无向图邻接表
{
    int i, j;
    VexType u, v;
    cout << "请输入顶点数和边数:" << endl;
    cin >> G.vexnum >> G.edgenum;
    cout << "请输入顶点信息:" << endl;
    for (i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组
        cin >> G.Vex[i].data;
    for (i = 0; i < G.vexnum; i++)
        G.Vex[i].first = NULL;
    cout << "请依次输入每条边的两个顶点u,v" << endl;
    while (G.edgenum--)
    {
        cin >> u >> v;
        i = locatevex(G, u);//查找顶点u的存储下标
        j = locatevex(G, v);//查找顶点v的存储下标
        if (i != -1 && j != -1)
        {
            insertedge(G, i, j);
            //insertedge(G, j, i);//无向图多插入一条边
        }
        else
        {
            cout << "输入顶点信息错！请重新输入！" << endl;
            G.edgenum++;//本次输入不算
        }
    }
}

void DFS_AL(ALGragh G, int v)//基于邻接表的深度优先遍历
{
    int w;
    AdjNode* p;//辅助指针
    cout << G.Vex[v].data << "\t";
    visited[v] = true;
    p = G.Vex[v].first;//获取该顶点的第一个邻接点
    while (p)//依次检查v的所有邻接点
    {
        w = p->v;//w为v的邻接点.
        if (!visited[w])//w未被访问,则从w出发,递归深度优先遍历
        {
            DFS_AL(G, w);
        }
        p = p->next;
    }
}

void DFS_AL(ALGragh G) //非连通图,基于邻接表的深度优先遍历
{
    for(int i = 0; i < G.vexnum; i++)//检查未被访问的点.
        if (!visited[i])
        {
            DFS_AL(G, i);
        }
}

int main()
{
    ALGragh G;
    int v;
    VexType c;
    CreateALGraph(G);//创建有向图邻接表
    printg(G);//输出
    cout << "请输入遍历连通图的起始点: ";
    cin >> c;
    v = locatevex(G, c);
    if (v != -1)
    {
        cout << "深度优先搜索遍历连通图结果: " << endl;
        DFS_AL(G, v);
        DFS_AL(G);
    }
    else
    {
        cout << "输入顶点信息错误!请重新输入!" << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

运行结果2

如图:
在这里插入图片描述

在这里插入图片描述

算法分析

基于邻接矩阵的DFS算法
查找每个顶点的邻接点需要O(n)时间，一共n个顶点，总的时间复杂度为O(n^2)，使用了一个递归工作栈，空间复杂度为O(n)。
基于邻接表的DFS算法
查找顶点vi的邻接点需要O(d(vi))时间，d(vi)为vi的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为O(e)，加上初始化时间O(n)，总的时间复杂度为O(n+e)，(由于n和e大小未知,所以时间复杂度两者都涉及)使用了一个递归工作栈，空间复杂度为O(n)。

二.广度优先遍历

2.1介绍

广度优先搜索（Breadth First Search, BFS），又称宽度优先搜索，是最常见的图搜索方法之一。广度优先搜索是从某个顶点（源点）出发，一次性访问所有未被访问的邻接点，再依次从这些访问过的邻接点出发……似水中涟漪，一层层地传播开来.

举例

在这里插入图片描述

广度优先遍历秘籍：先被访问的顶点，其邻接点先被访问。
根据广度优先遍历秘籍，先来先服务，可以借助于队列实现。每个节点访问一次且只访问一次，因此可以设置一个辅助数组visited[i]=false，表示第i个顶点未访问；visited[i]=true，表示第i个顶点已访问。

代码实现1—广度优先遍历邻接矩阵

#include <iostream>
#include <queue>//引入队列头文件
using namespace std;

#define MaxVnum 100  //顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;  //顶点的数据类型，根据需要定义
typedef int EdgeType;  //边上权值的数据类型，若不带权值的图，则为0或1
typedef struct {
    VexType Vex[MaxVnum];
    EdgeType Edge[MaxVnum][MaxVnum];
    int vexnum, edgenum; //顶点数，边数
}AMGragh;

int locatevex(AMGragh G, VexType x)
{
    for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标
        if (x == G.Vex[i])
            return i;
    return -1;//没找到
}

void CreateAMGraph(AMGragh& G)//创建有向图的邻接矩阵
{
    int i, j;
    VexType u, v;
    cout << "请输入顶点数：" << endl;
    cin >> G.vexnum;
    cout << "请输入边数:" << endl;
    cin >> G.edgenum;
    cout << "请输入顶点信息:" << endl;
    for (int i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组
        cin >> G.Vex[i];
    for (int i = 0; i < G.vexnum; i++)//初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大
        for (int j = 0; j < G.vexnum; j++)
            G.Edge[i][j] = 0;
    cout << "请输入每条边依附的两个顶点：" << endl;
    while (G.edgenum--)
    {
        cin >> u >> v;
        i = locatevex(G, u);//查找顶点u的存储下标
        j = locatevex(G, v);//查找顶点v的存储下标
        if (i != -1 && j != -1)
            G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1，若无向图G.Edge[i][j]=G.Edge[j][i]=1
        else
        {
            cout << "输入顶点信息错！请重新输入！" << endl;
            G.edgenum++;//本次输入不算
        }
    }
}

void print(AMGragh G)//输出邻接矩阵
{
    cout << "图的邻接矩阵为：" << endl;
    for (int i = 0; i < G.vexnum; i++)
    {
        for (int j = 0; j < G.vexnum; j++)
            cout << G.Edge[i][j] << "\t";
        cout << endl;
    }
}

void BFS_AM(AMGragh G, int v)
{
    int u, w;
    queue<int> Q;//创建一个队列,里面存放节点的下标
    cout << G.Vex[v] << "\t";
    visited[v] = true;
    Q.push(v);//源点v入队
    while (!Q.empty())
    {
        u = Q.front();//取对头
        Q.pop();
        for (w = 0; w < G.vexnum; w++)//一次检查u的所有邻接点
        {
            if (G.Edge[u][w] && !visited[w])//是邻接点但没有访问则进行访问
            {
                cout << G.Vex[w] << "\t";
                visited[w] = true;
                Q.push(w);
            }
        }
    }
}

void BFS_AM(AMGragh G){
	for(int i = 0; i < G.vexnum; i++){
		if(!visited[i]){
			BFS_AM(G,i); 
		}
	}
}

int main()
{
    int v;
    VexType c;
    AMGragh G;
    CreateAMGraph(G);
    print(G);
    cout << "请输入遍历连通图的起始点: ";
    cin >> c;
    v = locatevex(G, c);//查找顶点u的存储下标
    if (v != -1)
    {
        cout << "广度优先搜索遍历连通图结果: " << endl;
        BFS_AM(G, v);
        BFS_AM(G);
    }
    else {
        cout << "输入顶点信息错! 请重新输入!" << endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

运行结果1

如图:
在这里插入图片描述

在这里插入图片描述

代码实现2—广度优先遍历邻接表

#include <iostream>
#include <queue>//引入队列头文件
using namespace std;

const int MaxVnum = 100;//顶点数最大值
bool visited[MaxVnum];  //访问标志数组，其初值为"false"
typedef char VexType;//顶点的数据类型为字符型

typedef struct AdjNode { //定义邻接点类型
    int v; //邻接点下标
    struct AdjNode* next; //指向下一个邻接点
}AdjNode;

typedef struct VexNode { //定义顶点类型
    VexType data; // VexType为顶点的数据类型，根据需要定义
    AdjNode* first; //指向第一个邻接点
}VexNode;

typedef struct {//定义邻接表类型
    VexNode  Vex[MaxVnum];
    int vexnum, edgenum; //顶点数，边数
}ALGragh;

int locatevex(ALGragh G, VexType x)
{
    for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标
        if (x == G.Vex[i].data)
            return i;
    return -1;//没找到
}

void insertedge(ALGragh& G, int i, int j)//插入一条边
{
    AdjNode* s;
    s = new AdjNode;
    s->v = j;
    s->next = G.Vex[i].first;
    G.Vex[i].first = s;
}

void printg(ALGragh G)//输出邻接表
{
    cout << "----------邻接表如下：----------" << endl;
    for (int i = 0; i < G.vexnum; i++)
    {
        AdjNode* t = G.Vex[i].first;
        cout << G.Vex[i].data << ": ";
        while (t != NULL)
        {
            cout << "---->";
            cout << "[" << G.Vex[t->v].data << "]";
            t = t->next;
        }
        cout << endl;
    }
}

void CreateALGraph(ALGragh& G)//创建有向图邻接表
{
    int i, j;
    VexType u, v;
    cout << "请输入顶点数和边数:" << endl;
    cin >> G.vexnum >> G.edgenum;
    cout << "请输入顶点信息:" << endl;
    for (i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组
        cin >> G.Vex[i].data;
    for (i = 0; i < G.vexnum; i++)
        G.Vex[i].first = NULL;
    cout << "请依次输入每条边的两个顶点u,v" << endl;
    while (G.edgenum--)
    {
        cin >> u >> v;
        i = locatevex(G, u);//查找顶点u的存储下标
        j = locatevex(G, v);//查找顶点v的存储下标
        if (i != -1 && j != -1)
            insertedge(G, i, j);
        else
        {
            cout << "输入顶点信息错！请重新输入！" << endl;
            G.edgenum++;//本次输入不算
        }
    }
}

void BFS_AL(ALGragh G, int v)//基于邻接表的广度优先遍历
{
    int u, w;
    AdjNode* p;
    queue<int> Q;
    cout << G.Vex[v].data << "\t";
    visited[v] = true;
    Q.push(v);
    while (!Q.empty())
    {
        u = Q.front();//取对头元素
        Q.pop();
        p = G.Vex[u].first;
        while (p)
        {
            w = p->v;
            if (!visited[w])//w未被访问
            {
                cout << G.Vex[w].data << "\t";
                visited[w] = true;
                Q.push(w);
            }
            p = p->next;
        }
    }
}

void BFS_AL(ALGragh G)//非连通图,基于邻接表的广度优先遍历
{
    for (int i = 0; i < G.vexnum; i++)//查漏点.
    {
        if (!visited[i])//未被访问则进行访问
        {
            BFS_AL(G, i);
        }
    }
}

int main()
{
    ALGragh G;
    int v;
    VexType c;
    CreateALGraph(G);//创建有向邻接表
    printg(G);//输出
    cout << "请输入遍历连通图的起始点: ";
    cin >> c;
    v = locatevex(G, c);//查找顶点u的存储下标
    if (v != -1)
    {
        cout << "广度优先搜索遍历连通图结构: " << endl;
        BFS_AL(G, v);
        BFS_AL(G);
    }
    else
    {
        cout << "输入顶点错!请重新输入!" << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

运行结果2

如图:
在这里插入图片描述

算法分析

基于邻接矩阵的BFS算法
查找每个顶点的邻接点需要O(n)时间，一共n个顶点，总的时间复杂度为O(n^2)，使用了一个辅助队列，最坏的情况下每个顶点入队一次(访问完就入队)，空间复杂度为O(n)。
基于邻接表的BFS算法
查找顶点vi的邻接点需要O(d(vi))时间，d(vi)为vi的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为O(e)，加上初始化时间O(n)，总的时间复杂度为O(n+e)，使用了一个辅助队列，最坏的情况下每个顶点入队一次，空间复杂度为O(n)。

总结

容易发现,广度优先和深度优先的算法效率基本相同,在实际应用中要根据需要合理选择.
需要注意的是，一个图的邻接矩阵是唯一的，因此基于邻接矩阵的BFS或DFS遍历序列也是唯一的。而图的邻接表不是唯一的，边的输入顺序不同，正序或逆序建表都会影响邻接表的邻接点顺序，因此基于邻接表的BFS或DFS遍历序列不是唯一的。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/1010802

图的遍历

图的遍历

介绍

一.深度优先遍历

1.1介绍

举例

代码实现1—深度优先遍历邻接矩阵

运行结果1

代码实现2—深度优先遍历 邻接表

运行结果2

算法分析

二.广度优先遍历

2.1介绍

举例

代码实现1—广度优先遍历邻接矩阵

运行结果1

代码实现2—广度优先遍历邻接表

运行结果2

算法分析

总结

代码实现2—深度优先遍历邻接表