图的遍历

以邻接表作存储结构，编写程序对给定的无向图G（包含n个顶点，编号为0至n-1）进行广度优先遍历，并在遍历的过程中计算图G的连通分量个数及边的数目。

本题限定在遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最小的一个进行访问，以顶点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
\#define  MaxVexNum 30  //最大顶点数

typedef struct ArcNode  //表结点定义

{ 

  int adjvex;

  struct ArcNode *nextarc;

}ArcNode;

typedef struct    //头结点定义

{ 

  ArcNode *firstarc;

}VerNode;

typedef struct 

{ 

  VerNode vertices[MaxVexNum];

  int  vernum, arcnum;

}ALGraph;

输入格式:

第一行输入图的顶点数和边数e。

接下来共e行。每行代表一条边，输入边依附的两个顶点的编号。用头插法建邻接表，各边按第一个顶点编号升序输入，第一个顶点相同时按第二个顶点降序输入。注意：边不能重复输入。

输出格式:

输出分三行

第一行 广度优先遍历序列。序列中每个顶点编号后跟一个空格。

第二行 连通分量个数

第三行 边数

对于下面给出的无向图G

​

输入样例:

9 8

0 2

0 1

1 3

2 6

2 5

3 4

5 6

7 8

输出样例:

0 1 2 3 5 6 4 7 8

2

8

BFS

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
#include<iostream>
using namespace std;

#define   MaxVexNum  30    //最大顶点数

typedef  struct  ArcNode   //表结点定义
{
	int  adjvex;
	struct  ArcNode* nextarc;
}ArcNode;
typedef  struct        //头结点定义
{
	ArcNode* firstarc;
}VerNode;
typedef  struct
{
	VerNode  vertices[MaxVexNum];
	int   vernum, arcnum;//点 边
}ALGraph;

struct queue {
	int count;//入队的次数，这里就是边
	int head;
	int rear;
	int que[MaxVexNum];
}q;
void push(int a) {
	q.que[q.rear] = a;	
	q.rear = (q.rear + 1) % MaxVexNum;
	q.count++;
}
void pop() {
	q.head = (q.head + 1) % MaxVexNum;
}

void create(ALGraph& gra,int(*arr)[2]) {//创建图
	for (int i = 0; i < gra.arcnum; i++) {
		ArcNode* ptr1 = (ArcNode*)malloc(sizeof(ArcNode));
		memset(ptr1, 0, sizeof(ArcNode));
		ptr1->adjvex = arr[i][1];
		ptr1->nextarc = gra.vertices[arr[i][0]].firstarc;
		gra.vertices[arr[i][0]].firstarc = ptr1;

		ArcNode* ptr2 = (ArcNode*)malloc(sizeof(ArcNode));
		memset(ptr2, 0, sizeof(ArcNode));
		ptr2->adjvex = arr[i][0];
		ptr2->nextarc = gra.vertices[arr[i][1]].firstarc;
		gra.vertices[arr[i][1]].firstarc = ptr2;


	}
}

void BFS(ALGraph gra, bool* visit, int i) {//i记录当前位置
	if (visit[i] == false) {
		visit[i] = true;
		cout << i << " ";
		ArcNode* ptr = gra.vertices[i].firstarc;
		while (ptr != NULL) {
			if (visit[ptr->adjvex] == false)//被标记过则不再入队
				push(ptr->adjvex);
			ptr = ptr->nextarc;
		}
		i = q.que[q.head];
		pop();
		BFS(gra, visit, i);
	}
}

int main()
{
	freopen("./data1.txt", "r", stdin);

	ALGraph gra;
	memset(&gra, 0, sizeof(gra));
	memset(&q, 0, sizeof(q));
	int arr[100][2];
	cin >> gra.vernum >> gra.arcnum;
	for (int i = 0; i < gra.arcnum; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	create(gra,arr);//创建图

	bool visit[MaxVexNum] = {false};
	int count = 0;//连通分量
	for (int i = 0; i < gra.arcnum; i++)
		if (visit[i] == false) {
			BFS(gra, visit, i);
			count++;
		}

	cout << endl;
	cout << count << endl;
	cout << q.count;//入队的次数就是边数


}

DFS

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
#include<iostream>
using namespace std;

#define   MaxVexNum  30    //最大顶点数

typedef  struct  ArcNode   //表结点定义
{
	int  adjvex;
	struct  ArcNode* nextarc;
}ArcNode;
typedef  struct        //头结点定义
{
	ArcNode* firstarc;
}VerNode;
typedef  struct
{
	VerNode  vertices[MaxVexNum];
	int   vernum, arcnum;//点 边
}ALGraph;


void create(ALGraph& gra, int(*arr)[2]) {//创建图
	for (int i = 0; i < gra.arcnum; i++) {
		ArcNode* ptr1 = (ArcNode*)malloc(sizeof(ArcNode));
		memset(ptr1, 0, sizeof(ArcNode));
		ptr1->adjvex = arr[i][1];
		ptr1->nextarc = gra.vertices[arr[i][0]].firstarc;
		gra.vertices[arr[i][0]].firstarc = ptr1;

		ArcNode* ptr2 = (ArcNode*)malloc(sizeof(ArcNode));//无向图回来的一边
		memset(ptr2, 0, sizeof(ArcNode));
		ptr2->adjvex = arr[i][0];
		ptr2->nextarc = gra.vertices[arr[i][1]].firstarc;
		gra.vertices[arr[i][1]].firstarc = ptr2;


	}
}

void DFS(ALGraph gra, bool* visit, int i) {//i记录当前位置
	if (visit[i] == false) {
		visit[i] = true;
		cout << i << " ";
		ArcNode* ptr = gra.vertices[i].firstarc;
		while (ptr != NULL) {
			if(visit[ptr->adjvex]==false)
			DFS(gra, visit, ptr->adjvex);
			ptr = ptr->nextarc;
		}
	}
}

int main()
{
	freopen("./data1.txt", "r", stdin);

	ALGraph gra;
	memset(&gra, 0, sizeof(gra));
	int arr[100][2];
	cin >> gra.vernum >> gra.arcnum;
	for (int i = 0; i < gra.arcnum; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	create(gra, arr);//创建图
	bool visit[MaxVexNum] = { false };
	int count = 0;
	for (int i = 0; i < gra.arcnum; i++)
		if (visit[i] == false) {
			DFS(gra, visit, i);
			count++;
		}
}