【数据结构】图的基本操作（含全部代码）_数据结构图的基本操作代码

图的存储结构主要有邻接矩阵，邻接表，十字链表等。笔者在这里主要介绍邻接矩阵和邻接表两种存储结构。并将分别采用两种存储方法去实现无向图的基本操作，包括加点，删点，加边，删边、深度优先遍历以及广度优先遍历。（文末附完整代码）

邻接矩阵部分

主要包含如下函数
void visit()
该函数意在将标注数组初始化为false；（标志数组在dfs和bfs均有用到)
void insert_node(char c) 加点函数
void delete_node(char c) 删点函数
insert_edge(char u, char v) 加边函数
delete_edge(char u, char v) 删边函数
bfs(int v) 广度优先遍历
dfs(int u) 深度优先遍历
每个函数的具体算法思想均在代码种给出注释
以下为邻接矩阵的完整代码

#include <iostream>
#include <algorithm>
#include <string.h> 
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <cstdio>
const int N = 100;

using namespace std;

int V, E;
class matrix
{
private:
    int no, ed;
    char node[N];
    int edge[N][N];
    bool vis[N];

public:
    matrix()
    {
        memset(edge, 0,sizeof(edge));
        for (int i = 0; i < N; ++i)
            node[i] = '#', vis[i] = false;
        no = ed = 0;
    }
    void visit()
    {
        for (int i = 0; i < N; ++i)
            vis[i] = false;
    }
    void insert_node(char c) //扩容
    /**
     * @description: 由于采用的是顺序表结构存储
     * 只需在设置一个记录结点个数的变量，每次新
     * 加入一个结点就顺序接在数组尾巴，然后记录
     * 结点个数的变量自增 1
     * @param {*char c}
     */
    {
        node[no++] = c;
    }
    void delete_node(char c)
    /**
     * @description: 顺序遍历存储结点的数组。直至找到该节点
     * 然后将该节点后面的数据全部往前移一个位置。同时记录边问题
     * 的数组也应将包含该节点边关系的对应数据行和列采取将后面的
     * 数据往前移动位置，以覆盖边数组种被删除结点的信息
     * @param {*char c}
     */
    {
        int i;
        for (i = 0; i < no; ++i)
            if (node[i] == c)
                break;
        for (int j = i; j < no - 1; ++j)
            node[j] = node[j + 1];
        for (int k = 0; k < no; ++k)
            for (int j = i; j < no - 1; ++j)
                edge[k][j] = edge[k][j + 1];
        for (int k = 0; k < no - 1; ++k)
            for (int j = i; j < no - 1; ++j)
                edge[j][k] = edge[j + 1][k];
        no--;
    }
    void insert_edge(char u, char v)
    /**
     * @description: 通过设置两个变量x，y，顺序变量结点数组
     * 在找到相应结点后存储它的位置下标，然后在边数组中将其
     * 连接起来
     * @param {*char u, char v}
     */
    {
        int x = -1, y = -1; //不存在的情况
        for (int i = 0; i < no; ++i)
            if (node[i] == u)
                x = i;
            else if (node[i] == v)
                y = i;
        edge[x][y] = edge[y][x] = 1;
        ed++;
    }
    void delete_edge(char u, char v)
    /**
     * @description: 同加边操作，首先应找出两个结点对应的
     * 下标，然后在边数组中删除相应的边
     * @param {*char u, char v}
     */
    {
        int x = -1, y = -1; //不存在的情况
        for (int i = 0; i < no; ++i)
            if (node[i] == u)
                x = i;
            else if (node[i] == v)
                y = i;
        edge[x][y] = edge[y][x] = 0;
        ed--;
    }
    void bfs(int v)
    /**
     * @description: 广度优先遍历，借助队列来实现
     * 首先将开始结点V输出，同时将下标存入队列中，然后
     * 在队列不为空的情况下逐一出队队首元素，判断是否存在
     * 以该元素为起点的边，同时边的终点未被访问，若满足该
     * 两项条件则可以输出数据，并标记该节点已输出，然后将
     * 该结点入队，如此往复直至队列为空。
     * @param {*int v}
     */
    {
        queue<int> q;
        q.push(v);
        cout << node[v] << " ";
        vis[v] = true;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < no; ++i)
            {
                if (edge[u][i] == 1 && !vis[i])
                {
                    cout << node[i] << " ";
                    vis[i] = true;
                    q.push(i);
                }
            }
        }
    }
    void dfs(int u)
    /**
     * @description: 深度优先遍历。采用递归形式实现
     * 首先输出开始结点对应数据，然后顺序遍历以开始结点
     * 为起点的边，且边的终点尚未被访问过，则往下搜索，如此
     * 往复，直至输出全部结点
     * @param {*int u}
     */
    {
        cout << node[u] << " ";
        vis[u] = true;
        for (int i = 0; i < no; ++i)
            if (edge[u][i] == 1 && !vis[i])
                dfs(i);
    }
    void display_node()
    /**
     * @description: 通过顺序遍历结点数组，以输出结点来进行展示
     */
    {
        for (int i = 0; i < no; ++i)
            cout << node[i] << " ";
        cout << endl;
    }
    void display_edge()
    /**
     * @description: 顺序遍历边数组，输出边信息来进行展示
     */
    {
        for (int i = 0; i < no; cout << endl, ++i)
            for (int j = 0; j < no; ++j)
                cout << edge[i][j] << " ";
    }
};
void Matrix()
{
    cout << "邻接矩阵：\n";
    matrix G;
    cout << "请输入点数，边数：\n";
    cin >> V >> E;
    cout << "请输入点\n";
    char cc, u, v;
    for (int i = 0; i < V; ++i)
    {
        cin >> cc;
        G.insert_node(cc);
    }
    cout << "请输入边\n";
    for (int i = 0; i < E; ++i)
    {
        cin >> u >> v;
        G.insert_edge(u, v);
    }
    G.display_node();
    G.display_edge();
    cout << "请输出宽搜结果\n";
    G.bfs(0);
    G.visit();
    cout << endl;
    cout << "请输出深搜结果\n";
    G.dfs(0);
    G.visit();
    cout << endl;
    cout << "请输入要删除的点的数及点\n";
    cin >> V;
    for (int i = 0; i < V; ++i)
    {
        cin >> cc;
        G.delete_node(cc);
    }
    cout << "请输入要删除的边的数及边\n";
    cin >> E;
    for (int i = 0; i < E; ++i)
    {
        cin >> u >> v;
        G.delete_edge(u, v);
    }
    G.display_node();
    G.display_edge();
}
int main()
{
    int _ = 1;
    //sf(_);
    while (_--)
    {
        Matrix();
    }

    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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223

邻接表部分

主要实现思想同邻接矩阵，这里就不再赘述，直接放代码，代码中包含了详细注释

#include <iostream>
#include <algorithm>
#include <string.h> 
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <cstdio>
const int N = 100;

using namespace std;

int V, E;
typedef struct arcnode
{
    struct arcnode *next;
    int vex;
    arcnode(const int &d) : vex(d), next(NULL) {}
} arcnode;
typedef struct node
{
    char ve;
    arcnode *fir = new arcnode(0);
} arclist[N];
class arc
{
private:
    arclist ar;
    int no, ed;
    bool vis[N];

public:
    arc()
    {
        no = ed = 0;
        for (int i = 0; i < 100; ++i)
            ar[i].ve = '#';
    }
    void visit()
    {
        for (int i = 0; i < 100; ++i)
            vis[i] = false;
    }
    void insert_node(char c)
    /**
     * @description: 由于采用的是顺序表结构存储
     * 只需在设置一个记录结点个数的变量，每次新
     * 加入一个结点就顺序接在数组尾巴，然后记录
     * 结点个数的变量自增 1
     * @param {*char c}
     */
    {
        ar[no++].ve = c;
    }
    void delete_node(char c)
    /**
     * @description: 首先在结点数组中找到要删除结点的下标，然后
     * 将该结点后面的数据均往前移动一个位置以覆盖数据，从而达到删除
     * 该结点目的。同时在邻接表中也要删除对应的边关系，首先将该节点
     * 的边关系的存储链表删除，然后遍历其他每一个结点的存储边关系的
     * 存储链表，找到其中包含该节点的下标的结点，将其删去，同时对大于
     * 该节点的其他数据，若存储下标大于它，则应自减 1
     * @param {*char c}
     */
    {
        int i;
        for (i = 0; i < no; ++i)
            if (ar[i].ve == c)
                break;
        for (int j = i; j < no - 1; ++j)
            ar[j] = ar[j + 1];
        no--;
        for (int k = 0; k < no; ++k)
        {
            arcnode *T = ar[k].fir;
            while (T->next)
            {
                if (T->next->vex == i)
                {
                    if (T->next->next)
                        T->next = T->next->next;
                    else
                        T->next = NULL;
                    break;
                }
                else if (T->next->vex > i)
                {
                    T->next->vex--;
                    T = T->next;
                }
                else
                    T = T->next;
            }
        }
    }
    void insert_edge(char u, char v)
    /**
     * @description: 首先应找到边对应两个结点的存储下标。然后分别
     * 在以u为起点的存储边关系的链表中连接v；然后在以v为起点的存储
     * 边关系的链表中连接u
     * @param {*char u, char v}
     */
    {
        int x = -1, y = -1;
        for (int i = 0; i < no; ++i)
            if (ar[i].ve == u)
                x = i;
            else if (ar[i].ve == v)
                y = i;
        arcnode *p = new arcnode(0);
        p->vex = y;
        arcnode *q = ar[x].fir;
        while (q->next)
            q = q->next;
        p->next = q->next;
        q->next = p;

        arcnode *r = new arcnode(0);
        r->vex = x;
        q = ar[y].fir;
        while (q->next)
            q = q->next;
        r->next = q->next;
        q->next = r;

        ed++;
    }
    void delete_edge(char u, char v)
    /**
     * @description: 
     * 删边操作同删点操作的思想
     * @param {*char u, char v}
     */
    {
        int x = -1, y = -1;
        for (int i = 0; i < no; ++i)
            if (ar[i].ve == u)
                x = i;
            else if (ar[i].ve == v)
                y = i;
        arcnode *T = ar[x].fir;
        while (T->next)
            if (T->next->vex != y)
                T = T->next;
            else
            {
                if (T->next->next)
                    T->next = T->next->next;
                else
                    T->next = NULL;
                break;
            }

        T = ar[y].fir;
        while (T->next)
            if (T->next->vex != y)
                T = T->next;
            else
            {
                if (T->next->next)
                    T->next = T->next->next;
                else
                    T->next = NULL;
                break;
            }
        ed--;
    }

    void bfs(int u)
    {
        queue<int> q;
        int v;
        cout << ar[u].ve << " ";
        q.push(u);
        vis[u] = true;
        while (!q.empty())
        {
            v = q.front();
            q.pop();
            arcnode *p = ar[v].fir;
            while (p->next)
            {
                p = p->next;
                if (!vis[p->vex])
                {
                    cout << ar[p->vex].ve << " ";
                    vis[p->vex] = true;
                    q.push(p->vex);
                }
            }
        }
    }
    void dfs(int u)
    {
        cout << ar[u].ve << " ";
        vis[u] = true;
        arcnode *p = ar[u].fir;
        while (p->next)
        {
            p=p->next;
            if (!vis[p->vex])
                dfs(p->vex);
        }
    }

    void display_edge()
    {
        cout << "修改后的结果" << endl;
        for (int i = 0; i < no; cout << endl, ++i)
        {
            cout << ar[i].ve << "  :";
            arcnode *T = new arcnode(0);
            T = ar[i].fir->next;
            while (T)
            {
                cout << T->vex << " ";
                T = T->next;
            }
            delete T;
        }
    }
};
void Arc()
{
    cout << "邻接表：\n";
    arc g;
    cout << "请输入点数，边数：\n";
    cin >> V >> E;
    cout << "请输入点\n";
    char cc, u, v;
    for (int i = 0; i < V; ++i)
    {
        cin >> cc;
        g.insert_node(cc);
    }
    cout << "请输入边\n";
    for (int i = 0; i < E; ++i)
    {
        cin >> u >> v;
        g.insert_edge(u, v);
    }
    g.display_edge();
    cout << "请输出宽搜结果\n";
    g.visit();
    g.bfs(0);
    cout << endl;
    cout << "请输出深搜结果\n";
    g.visit();
    g.dfs(0);
    cout << endl;
    cout << "请输入要删除的点的数及点\n";
    cin >> V;
    for (int i = 0; i < V; ++i)
    {
        cin >> cc;
        g.delete_node(cc);
    }
    g.display_edge();
    cout << "请输入要删除的边的数及边\n";
    cin >> E;
    for (int i = 0; i < E; ++i)
    {
        cin >> u >> v;
        g.delete_edge(u, v);
    }
    g.display_edge();
}

int main()
{
    int _ = 1;
    //sf(_);
    while (_--)
    {
        Arc();
    }

    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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280