难题
初始化，在下面的代码中，我们创建了一个具有十个结点的图结构，并且通过rand函数来给各结点之间的路径赋值。
typedef struct Graph { //创建图结构
int values[10][10]; //图结构的邻接矩阵，权值为0意味两结点无路径
} Graph;
void FillGraph(Graph &g) { //初始化出一个随机权值的图结构
srand((unsigned int)time(NULL)); //声明时间种子
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (i != j) { //判断是否同个结点
g.values[i][j] = rand() % 2; //权值取0~1的随机数
g.values[j][i] = g.values[i][j];//对称赋值
} else
g.values[i][j] = 0; //同个结点到同个结点之间权值为0
}
}
}
//展示图结构中各结点之间的权值
void ShowValues(Graph g) {
cout << "Values of each node:" << endl;
for(int i = 0; i < 10; i++) {
cout<< i << ": ";
for(int j = 0; j < 10; j++) {
cout << g.values[i][j] << " ";
}
cout << endl;
}
cout<<endl;
}
暴力遍历
倘若通过暴力遍历，显然也是能得到各结点的度的，但从时间复杂度和空间复杂度来讲并不完美。
- 时间复杂度：O(V2)，其中*V*是节点的数量。由于使用了两层循环来遍历所有节点，时间复杂度为*O*(*V*2)。
- 空间复杂度：O(V)，需要一个大小为V的数组来记录每个节点的度数。
//暴力遍历得到图中各结点的度
void PowerDegree(const Graph g) {
vector<int> degree(10, 0); //记录各结点度的数组，初始化为0
for (int i = 0; i < 10; i++) { //通过二层循环来得到各结点之间的度
for (int j = 0; j < 10; j++) {
if (g.values[i][j] != 0) {
degree[i]++;
}
}
}
cout << "Power to Degrees of each node:" << endl; //输出暴力遍历得到的结果
for (int i = 0; i < 10; i++) {
cout << "Node " << i << ": " << degree[i] << endl;
}
cout << endl;
}
接下来，我们需要了解一下有关图的广度优先遍历和深度优先遍历。
广度优先遍历BFS
广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。
BFS 通常借助队列来实现，代码如下所示。队列具有“先入先出”的性质，这与 BFS 的“由近及远”的思想异曲同工。
实现步骤：
- 将起始节点放入队列。
- 从队列中取出第一个节点，访问它，并将它的所有未访问的邻居节点加入队列。
- 重复步骤2，直到队列为空。
时间复杂度：O(V+E)，V为节点数，E为边数。空间复杂度：O(V)，因为最多同时存储V个节点
如上图，
1.1将结点0放入队列 队列（0）
1.2结点0取出并访问，将结点1和结点3放入队列 队列（1，3）
2.2 取出结点1并访问，将结点2和结点4放入队列 队列（3，2，4）
3.2 取出结点3并访问，将结点6放入队列 队列（2，4，6）
…
关键
-
重复放入队列的问题？
在这里有个重复结点4，即结点1相邻结点4，通过结点1放入结点4之后，访问结点3时不必再放入。
因此需要来记录当前结点有没有被访问过，因为本文使用的是C语言，所以直接用一个长度跟结点数一样的布尔数组来记录，倘若C++与Java可以使用哈希表来记录更便捷。
-
算法实现时，怎么将一个结点相邻的多个结点放入队列呢？
通过一层循环判断是否有权值+是否已访问，得到当前节点是否可以放入队列。
代码
//广度优先遍历来得到图中各结点的度
void BFSDegree(Graph g) {
vector<int> degree(10, 0); //记录各结点度的数组，且初始化为0
vector<bool> isvisit(10, false); //记录当前结点是否被访问，且初始化为false
queue<int> q; //声明BFS需要的队列
q.push(0); //将结点0放入队列中
while (!q.empty()) { //队列不为空是循环条件
int index = q.front(); //访问（得到）队首元素
q.pop(); //取出队首元素
isvisit[index] = true; //意味已访问
for(int j = 0; j < 10; j++) { //循环得到度
if(j == index) continue; //如果是本身结点，就跳过本次循环
if(g.values[index][j]) degree[index]++; //有路径，访问结点度数加一
if(!isvisit[j]){ //当未访问时，可放入队列
q.push(j);
isvisit[j] = true;
}
}
}
cout <<"BFS to Degrees of each node:" << endl; //输出广度优先搜索得到的结果
for (int i = 0; i < 10; i++) {
cout << "Node " << i << ": " << degree[i] << endl;
}
cout << endl;
}
总代码
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;
typedef struct Graph { //创建图结构
int values[10][10]; //图结构的邻接矩阵，权值为0意味两结点无路径
} Graph;
void FillGraph(Graph &g) { //初始化出一个随机权值的图结构
srand((unsigned int)time(NULL)); //声明时间种子
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (i != j) { //判断是否同个结点
g.values[i][j] = rand() % 2; //权值取0~1的随机数
g.values[j][i] = g.values[i][j];//对称赋值
} else
g.values[i][j] = 0; //同个结点到同个结点之间权值为0
}
}
}
//展示图结构中各结点之间的权值
void ShowValues(Graph g) {
cout << "Values of each node:" << endl;
for(int i = 0; i < 10; i++) {
cout<< i << ": ";
for(int j = 0; j < 10; j++) {
cout << g.values[i][j] << " ";
}
cout << endl;
}
cout<<endl;
}
//暴力遍历得到图中各结点的度
void PowerDegree(const Graph g) {
vector<int> degree(10, 0); //记录各结点度的数组，初始化为0
for (int i = 0; i < 10; i++) { //通过二层循环来得到各结点之间的度
for (int j = 0; j < 10; j++) {
if (g.values[i][j] != 0) {
degree[i]++;
}
}
}
cout << "Power to Degrees of each node:" << endl; //输出暴力遍历得到的结果
for (int i = 0; i < 10; i++) {
cout << "Node " << i << ": " << degree[i] << endl;
}
cout << endl;
}
//广度优先遍历来得到图中各结点的度
void BFSDegree(Graph g) {
vector<int> degree(10, 0); //记录各结点度的数组，且初始化为0
vector<bool> isvisit(10, false); //记录当前结点是否被访问，且初始化为false
queue<int> q; //声明BFS需要的队列
q.push(0); //将结点0放入队列中
while (!q.empty()) { //队列不为空是循环条件
int index = q.front(); //访问（得到）队首元素
q.pop(); //取出队首元素
isvisit[index] = true; //意味已访问
for(int j = 0; j < 10; j++) { //循环得到度
if(j == index) continue; //如果是本身结点，就跳过本次循环
if(g.values[index][j]) degree[index]++; //有路径，访问结点度数加一
if(!isvisit[j]){ //当未访问时，可放入队列
q.push(j);
isvisit[j] = true;
}
}
}
cout <<"BFS to Degrees of each node:" << endl; //输出广度优先搜索得到的结果
for (int i = 0; i < 10; i++) {
cout << "Node " << i << ": " << degree[i] << endl;
}
cout << endl;
}
int main() {
Graph g;
FillGraph(g);
ShowValues(g);
PowerDegree(g);
BFSDegree(g);
return 0;
}
运行结果
