提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
一、深度优先遍历
1.题目
2.代码
#include<iostream>
using namespace std;
const int MaxLen = 20;
class Map
{
private:
bool Visit[MaxLen];
int Matrix[MaxLen][MaxLen];
int Vexnum;
void DFS(int v);
public:
void SetMatrix(int vnum, int mx[MaxLen][MaxLen]);
void DFSTraverse();
};
void Map::SetMatrix(int vnum, int mx[MaxLen][MaxLen])
{
int i, j;
Vexnum = vnum;
for (int i = 0; i < MaxLen; i++)
{
for (int j = 0; j < MaxLen; j++)
{
Matrix[i][j] = 0;
}
}
for (i = 0; i < Vexnum; i++)
{
for (j = 0; j < Vexnum; j++)
{
Matrix[i][j] = mx[i][j];
}
}
}
void Map::DFSTraverse()
{
int v;
for (v = 0; v < Vexnum; v++)
{
Visit[v] = false;
}
for (v = 0; v < Vexnum; v++)
{
if (Visit[v] == false)
{
DFS(v);
}
}
}
void Map::DFS(int v)
{
int w, i, k;
Visit[v] = true;
cout << v << " ";
int* Adjvex = new int[Vexnum];
for (i = 0; i < Vexnum; i++)
{
Adjvex[i] = -1;
}
k = 0;
for (i = 0; i < Vexnum; i++)
{
if (Matrix[v][i] == 1)
{
Adjvex[k++] = i;
}
}
i = 0;
for (w = Adjvex[i]; w >= 0; w = Adjvex[++i])
{
if (!Visit[w])
DFS(w);
}
delete[]Adjvex;
}
int main()
{
int t, n;
cin >> t;
while (t--)
{
cin >> n;
Map a;
int m[MaxLen][MaxLen];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int temp;
cin >> temp;
m[i][j] = temp;
}
}
a.SetMatrix(n, m);
a.DFSTraverse();
cout << endl;
}
return 0;
}
二、广度优先遍历
1.题目
2.代码
#include<iostream>
#include<queue>
using namespace std;
const int MaxLen = 20;
class Map
{
private:
bool Visit[MaxLen];
int Matrix[MaxLen][MaxLen];
int Vexnum;
void DFS(int v);
void BFS(int v);
public:
void SetMatrix(int vnum, int mx[MaxLen][MaxLen]);
void DFSTraverse();
void BFSTraverse();
};
void Map::BFSTraverse()
{
BFS(0);
}
void Map::BFS(int v)
{
int w, u;
int i, k;
queue<int> Q;
i = 0;
for (v = 0; v < Vexnum; ++v)
{
if (!Visit[v])
{
Visit[v] = true;
cout << v << " ";
Q.push(v);
while (!Q.empty())
{
u = Q.front();
Q.pop();
for (w = 0; w < Vexnum; w++) {
if (Matrix[w][u] == 1 && Visit[w] == 0) {
cout << w << " ";
Visit[w] = 1;
Q.push(w);
}
}
}
}
}
}
void Map::SetMatrix(int vnum, int mx[MaxLen][MaxLen])
{
int i, j;
Vexnum = vnum;
for (int i = 0; i < MaxLen; i++)
{
for (int j = 0; j < MaxLen; j++)
{
Matrix[i][j] = 0;
}
}
for (i = 0; i < Vexnum; i++)
{
for (j = 0; j < Vexnum; j++)
{
Matrix[i][j] = mx[i][j];
}
}
}
int main()
{
int t, n;
cin >> t;
while (t--)
{
cin >> n;
Map a;
int m[MaxLen][MaxLen];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int temp;
cin >> temp;
m[i][j] = temp;
}
}
a.SetMatrix(n, m);
//a.DFSTraverse();
a.BFSTraverse();
cout << endl;
}
return 0;
}
三、图非0面积
1.题目
2.代码
#include<iostream>
#include<queue>
using namespace std;
class Graph
{
private:
int** map;
int m;
int n;
public:
Graph() {}
void set(int m, int n);
void display();
void change();
};
void Graph::change()
{ //0 up 1 down 2 left 3 right
int xm[4] = { 0,0,-1,1 };
int ym[4] = { 1,-1,0,0 };
queue<int>x;
queue<int>y;
x.push(0);
y.push(0);
while (!x.empty())
{
for (int i = 0; i < 4; i++)
{
if (x.front() + xm[i] <= m && x.front() + xm[i] >= 0 && y.front() + ym[i] <= n && y.front() + ym[i] >= 0 && map[x.front() + xm[i]][y.front() + ym[i]] == 0)
{
x.push(x.front() + xm[i]);
y.push(y.front() + ym[i]);
map[x.front() + xm[i]][y.front() + ym[i]] = 1;
}
}
x.pop();
y.pop();
}
}
void Graph::set(int M, int N)
{
m = M;
n = N;
map = new int* [m + 1];
for (int i = 0; i <= m; i++)
{
map[i] = new int[n + 1];
}
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
map[i][j] = 0;
}
}
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> map[i][j];
}
}
}
void Graph::display()
{
int num = 0;
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (map[i][j] == 0)
{
num++;
}
}
}
cout << num << endl;
}
int main()
{
int t;
cin >> t;
int** map;
while (t--)
{
int m, n;
cin >> m >> n;
Graph a;
a.set(m, n);
a.change();
a.display();
}
}
3.思路
与最外层相连的0不会被包围，可以将其变为1；
又二维数组的第一个元素可能为1，故先扩大该二维数组，即创建数组时，多一行一列，第0行与第0列都赋值为0；
四、图的连通
1.题目
2.代码
#include<iostream>
using namespace std;
class Graph
{
private:
int n;
int** Matrix;
int* Visit;
void DFS(int m);
int sum = 0;
public:
Graph(int N);
void DFSTraverse();
void display(int b);
};
Graph::Graph(int N)
{
n = N;
Matrix = new int* [n];
for (int i = 0; i < n; i++)
{
Matrix[i] = new int[n];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> Matrix[i][j];
}
}
}
void Graph::DFSTraverse()
{
int b = 1;
int* flag = new int[n];
for (int i = 0; i < n; i++)
{
flag[i] = -1;
}
for (int i = 0; i < n; i++)
{
Visit = new int[n];
for (int i = 0; i < n; i++)
{
Visit[i] = -1;
}
sum = 0;
DFS(i);
if (sum == n)
{
flag[i] = 1;
}
}
for (int i = 0; i < n; i++)
{
if (flag[i] != 1)
{
b = 0;
}
}
display(b);
}
void Graph::DFS(int m)
{
Visit[m] = 1;
sum++;
int* Link = new int[n];
for (int i = 0; i < n; i++)
{
Link[i] = -1;
}
int k = 0;
for (int i = 0; i < n; i++)
{
if (Matrix[m][i] == 1)
{
Link[k++] = i;
}
}
int i = 0;
int w = Link[i];
while (w != -1) {
if (Visit[w] != 1) {
DFS(w);
}
w = Link[++i];
}
delete[]Link;
}
void Graph::display(int b)
{
int w;
w = b;
if (w == 0)
{
cout << "No";
}
else
{
cout << "Yes";
}
cout << endl;
}
int main()
{
int t;
cin >> t;
int n;
while (t--)
{
cin >> n;
Graph a(n);
a.DFSTraverse();
}
}
3.思路
想知道是否任意两个点都有路径，可以对每一个点进行深度优先遍历，能够到达的节点数与该图包含的节点数做对比。
五、其他
动态创建二维数组
int** Matrix;
Matrix = new int* [n];
for (int i = 0; i < n; i++)
{
Matrix[i] = new int[n];
}