图的DFS/BFS遍历及基本操作

图的基本操作:

• 初始化图;
• 销毁图;
• 深度优先遍历顶点；
• 广度优先遍历顶点；
• 计算无向图顶点i的度；
• 计算有向图顶点i的入度和出度；
• 打印顶点i的邻接点；
• 打印图的邻接矩阵。

代码实现:

#include <iostream>
#include <queue>
using namespace std;
#define MaxV 50
bool visited[MaxV];

typedef struct AMGraph {
	char vexs[MaxV];
	int arcs[MaxV][MaxV];
	int vexnum, arcnum;
}AM_UDG, AM_DG;

struct ArcNode {
	int adjvex;
	ArcNode* nextarc;
};
typedef struct VexNode {
	char data;
	ArcNode* firstarc;
};
typedef struct ALGraph {
	VexNode vexs[MaxV];
	int vexnum, arcnum;
}AL_UDG, AL_DG;

//查找顶点下标(邻接矩阵)
int LocateVex(AMGraph G, char vex) {
	for (int i = 0; i < G.vexnum; i++) {
		if (G.vexs[i] == vex)
			return i;
	}
}

//查找顶点下标(邻接表)
int LocateVex(ALGraph G, char vex) {
	for (int i = 0; i < G.vexnum; i++) {
		if (G.vexs[i].data == vex)
			return i;
	}
}

//清空辅助数组
void ClearArray(bool visited[]) {
	for (int i = 0; i < MaxV; i++) {
		visited[i] = false;
	}
}

//邻接矩阵创建无向图
void CreateAM_UDG(AM_UDG& G) {
	cout << "输入无向图的顶点数和边数: ";
	cin >> G.vexnum >> G.arcnum;
	char vex1, vex2;
	int i, j, k;
	for (i = 0; i < G.vexnum; i++) {
		printf("第%d个顶点的名称: ", i + 1);
		cin >> vex1;
		G.vexs[i] = vex1;
	}
	for (i = 0; i < G.vexnum; i++) {
		for (j = 0; j < G.vexnum; j++) {
			G.arcs[i][j] = 0;
		}
	}
	for (k = 0; k < G.arcnum; k++) {
		printf("输入第%d条边关联的两个顶点: ", k + 1);
		cin >> vex1 >> vex2;
		i = LocateVex(G, vex1);
		j = LocateVex(G, vex2);
		G.arcs[i][j] = 1;
		G.arcs[j][i] = 1;
	}
	cout << "无向图创建成功!" << endl << endl;
}

//邻接矩阵创建有向图
void CreateAM_DG(AM_DG& G) {
	cout << "输入有向图的顶点数和边数: ";
	cin >> G.vexnum >> G.arcnum;
	char vex1, vex2;
	int i, j, k;
	for (i = 0; i < G.vexnum; i++) {
		printf("第%d个顶点的名称: ", i + 1);
		cin >> vex1;
		G.vexs[i] = vex1;
	}
	for (i = 0; i < G.vexnum; i++) {
		for (j = 0; j < G.vexnum; j++) {
			G.arcs[i][j] = 0;
		}
	}
	for (k = 0; k < G.arcnum; k++) {
		printf("输入第%d条边的弧尾和弧头: ", k + 1);
		cin >> vex1 >> vex2;
		i = LocateVex(G, vex1);
		j = LocateVex(G, vex2);
		G.arcs[i][j] = 1;
	}
	cout << "有向图创建成功!" << endl << endl;
}

//邻接表创建无向图
void CreateAL_UDG(AL_UDG& G) {
	cout << "输入无向图的顶点数和边数: ";
	cin >> G.vexnum >> G.arcnum;
	cout << "输入第1~" << G.vexnum << "个顶点的名称:" << endl;
	for (int i = 0; i < G.vexnum; i++) {
		cin >> G.vexs[i].data;
		G.vexs[i].firstarc = NULL;
	}
	char vex1, vex2;
	int i, j, k;
	for (k = 0; k < G.arcnum; k++) {
		printf("输入第%d条边关联的两个顶点: ", k + 1);
		cin >> vex1 >> vex2;
		i = LocateVex(G, vex1);
		j = LocateVex(G, vex2);
		ArcNode* p1 = new ArcNode;
		p1->adjvex = j;
		p1->nextarc = G.vexs[i].firstarc;
		G.vexs[i].firstarc = p1;
		ArcNode* p2 = new ArcNode;
		p2->adjvex = i;
		p2->nextarc = G.vexs[j].firstarc;
		G.vexs[j].firstarc = p2;
	}
	cout << "无向图创建成功!" << endl;
}

//邻接表创建有向图
void CreateAL_DG(AL_DG& G) {
	cout << "输入有向图的顶点数和边数: ";
	cin >> G.vexnum >> G.arcnum;
	cout << "输入第1~" << G.vexnum << "个顶点的名称:" << endl;
	for (int i = 0; i < G.vexnum; i++) {
		cin >> G.vexs[i].data;
		G.vexs[i].firstarc = NULL;
	}
	char vex1, vex2;
	int i, j, k;
	for (k = 0; k < G.arcnum; k++) {
		printf("输入第%d条边的弧尾和弧头: ", k + 1);
		cin >> vex1 >> vex2;
		i = LocateVex(G, vex1);
		j = LocateVex(G, vex2);
		ArcNode* p1 = new ArcNode;
		p1->adjvex = j;
		p1->nextarc = G.vexs[i].firstarc;
		G.vexs[i].firstarc = p1;
	}
	cout << "有向图创建成功!" << endl;
}

//邻接矩阵深度遍历
void DFS_AM(AMGraph G, int i) {
	cout << G.vexs[i - 1] << " ";
	visited[i - 1] = true;
	for (int j = 0; j < G.vexnum; j++) {
		if ((G.arcs[i - 1][j] != 0) && (!visited[j])) {
			DFS_AM(G, j + 1);
		}
	}
}

//邻接矩阵广度遍历
void BFS_AM(AMGraph G, int i) {
	queue <int> q;
	q.push(i - 1);
	visited[i - 1] = true;
	int j;
	while (!q.empty()) {
		j = q.front();
		q.pop();
		cout << G.vexs[j] << " ";
		for (int k = 0; k < G.vexnum; k++) {
			if ((G.arcs[j][k] != 0) && (!visited[k])) {
				q.push(k);
				visited[k] = true;
			}
		}
	}
	cout << endl;
}

//邻接表深度遍历
void DFS_AL(ALGraph G, int i) {
	cout << G.vexs[i - 1].data << " ";
	visited[i - 1] = true;
	ArcNode* p = G.vexs[i - 1].firstarc;
	while (p) {
		int j = p->adjvex;
		if (!visited[j])
			DFS_AL(G, j + 1);
		p = p->nextarc;
	}
}

//邻接表广度遍历
void BFS_AL(ALGraph G, int i) {
	queue <int> q;
	q.push(i - 1);
	visited[i - 1] = true;
	int j;
	while (!q.empty()) {
		j = q.front();
		q.pop();
		cout << G.vexs[j].data << " ";
		ArcNode* p = G.vexs[j].firstarc;
		while (p) {
			if (!visited[p->adjvex]) {
				q.push(p->adjvex);
				visited[p->adjvex] = true;
			}
			p = p->nextarc;
		}
	}
	cout << endl;
}

//计算无向图的度
void CalDu_UDG(AM_UDG G, int i) {
	int d = 0;
	for (int j = 0; j < G.vexnum; j++) {
		if (G.arcs[i - 1][j] == 1)
			d++;
	}
	printf("第%d个顶点的度为: %d\n", i, d);
}

//计算有向图的出度和入度
void CalDu_DG(AM_DG G, int i) {
	int dIN = 0, dOUT = 0;
	for (int j = 0; j < G.vexnum; j++) {
		if (G.arcs[i - 1][j] == 1)
			dIN++;
	}
	printf("第%d个顶点的出度为: %d\n", i, dIN);
	for (int j = 0; j < G.vexnum; j++) {
		if (G.arcs[j][i - 1] == 1)
			dOUT++;
	}
	printf("第%d个顶点的入度为: %d\n", i, dOUT);
}

//打印无向图的邻接点
void PrintAdjVex_UDG(AM_UDG G, int i) {
	printf("第%d个顶点的邻接点为: ", i);
	for (int j = 0; j < G.vexnum; j++) {
		if (G.arcs[i - 1][j] == 1)
			cout << G.vexs[j] << " ";
	}
	cout << endl;
};

//打印有向图的邻接点
void PrintAdjVex_DG(AM_DG G, int i) {
	printf("第%d个顶点的邻接点为: ", i);
	for (int j = 0; j < G.vexnum; j++) {
		if (G.arcs[i - 1][j] == 1)
			cout << G.vexs[j] << " ";
	}
	for (int k = 0; k < G.vexnum; k++) {
		if (G.arcs[k][i - 1] == 1)
			cout << G.vexs[k] << " ";
	}
	cout << endl;
}

//打印邻接矩阵
void PrintAM(AMGraph G) {
	cout << "*****图的邻接矩阵*****" << endl;
	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			cout << G.arcs[i][j] << "  ";
		}
		cout << endl;
	}
}

//销毁图
void DestroyGraph(AMGraph& G) {
	G.vexnum = G.arcnum = NULL;
	cout << "图已销毁!" << endl;
}

int  main() {
	AM_UDG G1;//邻接矩阵_无向图
	CreateAM_UDG(G1);
	cout << "邻接矩阵_无向图深度优先遍历: ";
	DFS_AM(G1, 1);
	ClearArray(visited);//清空辅助数组
	cout << "\n邻接矩阵_无向图广度优先遍历: ";
	BFS_AM(G1, 1);
	ClearArray(visited);
	CalDu_UDG(G1, 1);
	PrintAdjVex_UDG(G1, 1);
	PrintAM(G1);
	DestroyGraph(G1);
	cout << endl;

	AM_DG G2;//邻接矩阵_有向图
	CreateAM_DG(G2);
	cout << "邻接矩阵_有向图深度优先遍历: ";
	DFS_AM(G2, 1);
	ClearArray(visited);
	cout << "\n邻接矩阵_有向图广度优先遍历: ";
	BFS_AM(G2, 1);
	ClearArray(visited);
	CalDu_DG(G2, 1);
	PrintAdjVex_DG(G2, 1);
	PrintAM(G2);
	DestroyGraph(G2);
	cout << endl;

	AL_UDG G3;//邻接表_无向图
	CreateAL_UDG(G3);
	cout << "邻接表_无向图深度优先遍历: ";
	DFS_AL(G3, 1);
	ClearArray(visited);
	cout << "\n邻接表_无向图广度优先遍历: ";
	BFS_AL(G3, 1);
	ClearArray(visited);
	cout << endl;

	AL_DG G4;//邻接表_有向图
	CreateAL_DG(G4);
	cout << "邻接表_有向图深度优先遍历: ";
	DFS_AL(G4, 1);
	ClearArray(visited);
	cout << "\n邻接表_有向图广度优先遍历: ";
	BFS_AL(G4, 1);
	ClearArray(visited);

	system("pause");
	return 0;
}