图
1. DS图遍历–深度优先搜索
题目描述
给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始
注意：图n个顶点编号从0到n-1
代码框架如下：
输入
第一行输入t，表示有t个测试实例
第二行输入n，表示第1个图有n个结点
第三行起，每行输入邻接矩阵的一行，以此类推输入n行
第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开
以此类推输入下一个示例
输出
每行输出一个图的深度优先搜索结果，结点编号之间用空格隔开
输入样例
2
4
0 0 1 1
0 0 1 1
1 1 0 1
1 1 1 0
5
0 0 0 1 1
0 0 1 0 0
0 1 0 1 1
1 0 1 0 0
1 0 1 0 0
输出样例
0 2 1 3
0 3 2 1 4
参考代码
#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 (i = 0; i < Maxlen; i++)
for (j = 0; j < Maxlen; j++)
Matrix[i][j] = 0;
for (i = 0; i < Maxlen; i++)
for (j = 0; j < Maxlen; j++)
Matrix[i][j] = mx[i][j];
}
void Map::DFSTraverse()
{
int v;
for (int i = 0; i < Maxlen; i++)
Visit[i] = false;
for (int i = 0; i < Vexnum; i++)
{
if (!Visit[i])
DFS(i);
}
cout << endl;
}
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])
AdjVex[k++] = i;
i = 0;
for (i = 0; i < k; i++)
{
w = AdjVex[i];
if (!Visit[w])
DFS(w);
}
delete[] AdjVex;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n, i, j;
cin >> n;
int mx[Maxlen][Maxlen];
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
cin >> mx[i][j];
}
Map m;
m.SetMatrix(n, mx);
m.DFSTraverse();
}
}
2. DS图遍历–广度优先搜索
题目描述
给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始
注意：图n个顶点编号从0到n-1
代码框架如下：
输入
第一行输入t，表示有t个测试实例
第二行输入n，表示第1个图有n个结点
第三行起，每行输入邻接矩阵的一行，以此类推输入n行
第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开
以此类推输入下一个示例
输出
每行输出一个图的广度优先搜索结果，结点编号之间用空格隔开
输入样例
2
4
0 0 1 1
0 0 1 1
1 1 0 1
1 1 1 0
5
0 0 0 1 1
0 0 1 0 0
0 1 0 1 1
1 0 1 0 0
1 0 1 0 0
输出样例
0 2 3 1
0 3 4 2 1
参考代码
#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::SetMatrix(int vnum, int mx[Maxlen][Maxlen])
{
int i, j;
Vexnum = vnum;
for (i = 0; i < Maxlen; i++)
for (j = 0; j < Maxlen; j++)
Matrix[i][j] = 0;
for (i = 0; i < Maxlen; i++)
for (j = 0; j < Maxlen; j++)
Matrix[i][j] = mx[i][j];
}
void Map::DFSTraverse()
{
int v;
for (int i = 0; i < Maxlen; i++)
Visit[i] = false;
for (int i = 0; i < Vexnum; i++)
{
if (!Visit[i])
DFS(i);
}
cout << endl;
}
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])
AdjVex[k++] = i;
i = 0;
for (i = 0; i < k; i++)
{
w = AdjVex[i];
if (!Visit[w])
DFS(w);
}
delete[] AdjVex;
}
void Map::BFSTraverse()
{
BFS(0);
}
void Map::BFS(int v)
{
int w, u, i, k;
int *Adjvex = new int[Vexnum];
queue<int> Q;
for (i = 0; i < Vexnum; i++)
Visit[i] = false;
for (v = 0; v < Vexnum; ++v)
{
if (!Visit[v])
{
cout << v << " ";
Visit[v] = true;
Q.push(v);
while (!Q.empty())
{
u = Q.front();
Q.pop();
k = 0;
for (i = 0; i < Vexnum; i++)
if (Matrix[u][i])
Adjvex[k++] = i;
i = 0;
for (i = 0; i < k; i++)
{
w = Adjvex[i];
if(!Visit[w])
{
Visit[w] = true;
cout << w << " ";
Q.push(w);
}
}
}
}
}
cout << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n, i, j;
cin >> n;
int mx[Maxlen][Maxlen];
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
cin >> mx[i][j];
}
Map m;
m.SetMatrix(n, mx);
m.BFSTraverse();
}
}
3. 图综合练习–构建邻接表
题目描述
已知一有向图，构建该图对应的邻接表。
邻接表包含数组和单链表两种数据结构，其中每个数组元素也是单链表的头结点，数组元素包含两个属性，属性一是顶点编号info，属性二是指针域next指向与它相连的顶点信息。
单链表的每个结点也包含两个属性，属性一是顶点在数组的位置下标，属性二是指针域next指向下一个结点。
输入
第1行输入整数t，表示有t个图
第2行输入n和k，表示该图有n个顶点和k条弧。
第3行输入n个顶点。
第4行起输入k条弧的起点和终点，连续输入k行
以此类推输入下一个图
输出
输出每个图的邻接表，每行输出格式：数组下标 顶点编号-连接顶点下标-…-^，数组下标从0开始。
具体格式请参考样例数据，每行最后加入“^”表示NULL。
输入样例
1
5 7
A B C D E
A B
A D
A E
B D
C B
C E
E D
输出样例
0 A-1-3-4-^
1 B-3-^
2 C-1-4-^
3 D-^
4 E-3-^
参考代码
#include <iostream>
using namespace std;
class Node
{
public:
int pos;
Node *next;
Node() : next(NULL){};
Node(int t) : pos(t), next(NULL){};
};
class Map
{
public:
int Vexnum;
Node *head;
char *Vex;
int index(char c)
{
for (int i = 0; i < Vexnum; i++)
{
if (c == Vex[i])
return i;
}
return -1;
}
Map(int n, int k)
{
Vexnum = n;
Vex = new char[Vexnum];
head = new Node[Vexnum];
for (int i = 0; i < n; i++)
{
cin >> Vex[i];
}
for (int i = 0; i < k; i++)
{
char c1, c2;
cin >> c1 >> c2;
int num1 = index(c1), num2 = index(c2);
Node *p = &head[num1];
while (p->next)
p = p->next;
Node *p1 = new Node();
p1->pos = num2;
p->next = p1;
}
}
~Map()
{
delete[] Vex;
for (int i = 0; i < Vexnum; i++)
{
Node *p = head[i].next;
while (p)
{
Node *p1 = p;
p = p->next;
delete p1;
}
}
delete[] head;
}
void display()
{
for (int i = 0; i < Vexnum; i++)
{
cout << i << " " << Vex[i];
Node *p = head[i].next;
while (p)
{
cout << "-" << p->pos;
p = p->next;
}
cout << "-^" << endl;
}
}
};
int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
Map m(n, k);
m.display();
}
}
4. DS图—图的邻接矩阵存储及度计算
题目描述
假设图用邻接矩阵存储。输入图的顶点信息和边信息，完成邻接矩阵的设置，并计算各顶点的入度、出度和度，并输出图中的孤立点（度为0的顶点）
–程序要求–
若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件，不看代码，作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
测试次数T，每组测试数据格式如下：
图类型 顶点数 （D—有向图，U—无向图）
顶点信息
边数
每行一条边（顶点1 顶点2）或弧（弧尾 弧头）信息
输出
每组测试数据输出如下信息（具体输出格式见样例）：
图的邻接矩阵
按顶点信息输出各顶点的度（无向图）或各顶点的出度 入度 度（有向图）。孤立点的度信息不输出。
图的孤立点。若没有孤立点，不输出任何信息。
输入样例
2
D 5
V1 V2 V3 V4 V5
7
V1 V2
V1 V4
V2 V3
V3 V1
V3 V5
V4 V3
V4 V5
U 5
A B C D E
5
A B
A C
B D
D C
A D
输出样例
0 1 0 1 0
0 0 1 0 0
1 0 0 0 1
0 0 1 0 1
0 0 0 0 0
V1: 2 1 3
V2: 1 1 2
V3: 2 2 4
V4: 2 1 3
V5: 0 2 2
0 1 1 1 0
1 0 0 1 0
1 0 0 1 0
1 1 1 0 0
0 0 0 0 0
A: 3
B: 2
C: 2
D: 3
E
参考代码
#include <iostream>
using namespace std;
class Node
{
public:
int in = 0, out = 0, total = 0;
void inadd()
{
in++;
total++;
}
void outadd()
{
out++;
total++;
}
};
class Map
{
public:
int Vexnum;
char type;
Node *head;
string *Vex;
int **Matrix;
int index(string c)
{
for (int i = 0; i < Vexnum; i++)
{
if (c == Vex[i])
return i;
}
}
Map(int n, char t)
{
Vexnum = n;
type = t;
Vex = new string[Vexnum];
Matrix = new int *[Vexnum];
for (int i = 0; i < Vexnum; i++)
Matrix[i] = new int[Vexnum];
head = new Node[Vexnum];
for (int i = 0; i < Vexnum; i++)
{
cin >> Vex[i];
}
for (int i = 0; i < Vexnum; i++)
for (int j = 0; j < Vexnum; j++)
{
Matrix[i][j] = 0;
}
int k;
cin >> k;
while (k--)
{
string c1, c2;
cin >> c1 >> c2;
int num1 = index(c1), num2 = index(c2);
head[num1].outadd();
head[num2].inadd();
if (type == 'U')
{
Matrix[num1][num2] = 1;
Matrix[num2][num1] = 1;
}
else if (type == 'D')
{
Matrix[num1][num2] = 1;
}
}
}
~Map()
{
delete[] Vex;
delete[] head;
for (int i = 0; i < Vexnum;i++)
delete[] Matrix[i];
delete[] Matrix;
}
void display()
{
for (int i = 0; i < Vexnum; i++)
for (int j = 0; j < Vexnum; j++)
{
cout << Matrix[i][j];
if (j != Vexnum - 1)
cout << " ";
if (j == Vexnum - 1)
cout << endl;
}
for (int i = 0; i < Vexnum; i++)
{
cout << Vex[i];
if (head[i].total != 0)
{
cout << ":";
if (type == 'D')
{
cout << " " << head[i].out
<< " " << head[i].in
<< " " << head[i].total;
}
else if (type == 'U')
{
cout << " " << head[i].total;
}
}
cout << endl;
}
}
};
int main()
{
int t;
cin >> t;
while (t--)
{
char c;
int k;
cin >> c >> k;
Map m(k, c);
m.display();
}
}
5. DS图—图非0面积
题目描述
编程计算由"1"围成的下列图形的面积。面积计算方法是统计"1"所围成的闭合曲线中"0"点的数目。如图所示，在10*10的二维数组中，"1"围住了15个点，因此面积为15。
输入
测试次数t
每组测试数据格式为：
数组大小m,n
一个由0和1组成的m*n的二维数组
输出
对每个二维数组，输出符号"1"围住的"0"的个数，即围成的面积。假设一定有1组成的闭合曲线，但不唯一。
输入样例
2
10 10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
5 8
0 1 1 0 0 1 1 0
1 0 1 0 1 0 0 1
0 1 0 1 0 0 1 0
0 1 0 0 1 1 1 0
0 0 0 0 0 0 0 0
输出样例
15
5
参考代码
#include <iostream>
#include <queue>
using namespace std;
int n, m;
int nx[4] = {0, 0, 1, -1};
int ny[4] = {1, -1, 0, 0};
void bfs(int M[40][40], queue<int> x, queue<int> y, int a, int b)
{
x.push(a);
y.push(b);
while (!x.empty())
{
for (int i = 0; i < 4; i++)
{
if (x.front() + nx[i] <= n && x.front() + nx[i] >= 0 && y.front() + ny[i] <= m && y.front() + ny[i] >= 0 && M[x.front() + nx[i]][y.front() + ny[i]] == 0)
{
x.push(x.front() + nx[i]);
y.push(y.front() + ny[i]);
M[x.front() + nx[i]][y.front() + ny[i]] = 1;
}
}
x.pop();
y.pop();
}
}
int main()
{
int T;
cin >> T;
while (T--)
{
int M[40][40] = {0};
queue<int> x;
queue<int> y;
int num = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> M[i][j];
bfs(M, x, y, 0, 0);
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
if (M[i][j] == 0)
{
num++;
}
}
}
cout << num << endl;
}
return 0;
}