526互联

图的建立与深度、广度遍历

发布时间 2023-11-19 19:37:53作者: 小白不败

  • 图的建立有两种方式，一种是邻接矩阵，也就是顺序存储。另一种则是邻接表

在遍历过程中我们需要有一个数组，用来标记结点是否被调用过，我们称它为visited数组。
我们需要初始化一个二维矩阵edge[i][j],用来存储边的集合，含义为第i个结点与第j个结点之间有边。
其次我们在创建一个存储顶点的数组，是一个string类型的数组
//构造函数
Graph::Graph(string arry[], int n, int e) {
	int i, j;
//	int k;
	vertexnumber = n;
	edgenumber = e;
	for ( i = 0; i < vertexnumber; i++) { //初始化vertexnumber数组
		vertexarry[i] = arry[i];
	}
	for ( i = 0; i < vertexnumber; i++) {
		for ( j = 0; j < vertexnumber; j++) {
			edge[i][j] = 0;
		}
	}
        //偷个懒
	edge[0][1] = edge[1][0] = 1;
	edge[0][3] = edge[3][0] = 1;
	edge[3][4] = edge[4][3] = 1;
	edge[4][5] = edge[5][4] = 1;
	edge[2][3] = edge[3][2] = 1;
	edge[2][5] = edge[5][2] = 1;
	edge[1][5] = edge[5][1] = 1;
}

  • 对于邻接表存储（链式存储）

需要两个结构体，其中一个边集，一个顶点集.
在类中定义一个结构体类型的数组，这个数组长度=2*n-1,初始化边集、顶点集数组。
struct EdgeNode {//这是一个有关边集数组的结点
	int adjvex;
	EdgeNode* next;
};
struct VertexNode {//这是一个有关顶点集数组的结点
	string vertex;
	EdgeNode* firstedge;//每一个EdgeNode类型数组的头指针
};
//构造函数
ADGraph::ADGraph(string a[], int n, int e) {
	vertexnumber = n;
	edgenumber = e;
	int i, j, k;
	EdgeNode* s = NULL;
	for ( i = 0; i < vertexnumber; i++) {//初始化顶点集数组
		adjlist[i].vertex = a[i];
		adjlist[i].firstedge = NULL;
	}
	for ( k = 0; k < edgenumber; k++) {//初始化边集数组
		cin >> i >> j;
		s = new EdgeNode;
		s->adjvex = j;
		s->next = adjlist[i].firstedge;
		adjlist[i].firstedge = s;
	}
	
}
对于深度、广度遍历方法。深度遍历调用递归算法，广度遍历方法则是调用队列。
  • 深度遍历方法：
//深度优先遍历
void Graph::DFTraverse(int v) {
	cout << vertexarry[v]<<" ";
	visited1[v] = 1;//标记以访问的结点
	for (int i = 0; i < vertexnumber; i++) {
		if (edge[v][i] == 1 && visited1[i] == 0) {
			DFTraverse(i);
		}
	}
}
  • 广度优先遍历
//广度优先遍历
void Graph::BFTraverse(int v){
	int Queue[10];
	int front=-1,rear=-1,w,i;
	cout<<vertexarry[v]<<" ";
	visited2[v]=1;
	Queue[++rear]=v;            //入队
	while(front!=rear){
		w=Queue[++front];       //出队
		for( i=0;i<vertexnumber;i++){
			if(edge[w][i]==1 && visited2[i]==0){//第w结点与第i结点有边且第i个结点没有被访问过。
				cout<<vertexarry[i]<<" ";
				visited2[i]=1;
				Queue[++rear]=i;
			}
		}
	}
}

1 ### 邻接矩阵完整代码

//邻接矩阵建立图
#include <iostream>
using namespace std;
class Graph {
	private:
		int vertexnumber, edgenumber;
		string vertexarry[10];//结点类型的顶点变量名数组
		int edge[10][10];//边集数组
		int visited1[10] = {0};//用来作为访问的标志
	int visited2[10] = {0};//用来作为访问的标志

	public:
		Graph(string arry[], int n, int e); //构造函数,传入顶点数据、顶点个数、边的个数
		~Graph();//析构函数
		void DFTraverse(int v);//深度优先遍历函数
		void BFTraverse(int v);//广度优先遍历函数

};

//构造函数
Graph::Graph(string arry[], int n, int e) {
	int i, j;
//	int k;
	vertexnumber = n;
	edgenumber = e;
	for ( i = 0; i < vertexnumber; i++) { //初始化vertexnumber数组
		vertexarry[i] = arry[i];
	}
	for ( i = 0; i < vertexnumber; i++) {
		for ( j = 0; j < vertexnumber; j++) {
			edge[i][j] = 0;
		}
	}
	edge[0][1] = edge[1][0] = 1;
	edge[0][3] = edge[3][0] = 1;
	edge[3][4] = edge[4][3] = 1;
	edge[4][5] = edge[5][4] = 1;
	edge[2][3] = edge[3][2] = 1;
	edge[2][5] = edge[5][2] = 1;
	edge[1][5] = edge[5][1] = 1;
}

//析构函数
Graph::~Graph() {
	cout << "删除成功！" << endl;
}

//深度优先遍历
void Graph::DFTraverse(int v) {
	cout << vertexarry[v]<<" ";
	visited1[v] = 1;
	for (int i = 0; i < vertexnumber; i++) {
		if (edge[v][i] == 1 && visited1[i] == 0) {
			DFTraverse(i);
		}
	}
}

//广度优先遍历
void Graph::BFTraverse(int v){
	int Queue[10];//队列
	int front=-1,rear=-1,w,i;
	cout<<vertexarry[v]<<" ";
	visited2[v]=1;
	Queue[++rear]=v;//入队
	while(front!=rear){
		w=Queue[++front];
		for( i=0;i<vertexnumber;i++){
			if(edge[w][i]==1 && visited2[i]==0){
				cout<<vertexarry[i]<<" ";
				visited2[i]=1;
				Queue[++rear]=i;
			}
		}
	}
}

int main() {
	string arry[6] = {"v0", "v1", "v2", "v3", "v4", "v5"}; //用来存储每个结点的变量名
	Graph g(arry, 6, 7);
	cout<<"深度优先遍历：";
	g.DFTraverse(0);//深度遍历
	cout<<endl;
	cout<<"广度优先遍历：";		
	g.BFTraverse(0);//广度遍历
	cout<<endl;
	return 0;
}

2 ### 邻接表完整代码

//邻接表建立图
#include <iostream>
using namespace std;
struct EdgeNode {//这是一个有关边集数组的结点
	int adjvex;
	EdgeNode* next;
};
struct VertexNode {//这是一个有关顶点集数组的结点
	string vertex;
	EdgeNode* firstedge;
};

class ADGraph {
private:
	int vertexnumber, edgenumber;
	VertexNode adjlist[10];
	int visited1[10] = {0};
	int visited2[10] = {0};
	int Queue[10];
public:
	ADGraph(string a[], int n, int e); //构造函数
	~ADGraph();//析构函数
	void DFTraverse(int v);//深度遍历
	void BFTraverse(int v);//广度遍历
};

//构造函数
ADGraph::ADGraph(string a[], int n, int e) {
	vertexnumber = n;
	edgenumber = e;
	int i, j, k;
	EdgeNode* s = NULL;
	for ( i = 0; i < vertexnumber; i++) {
		adjlist[i].vertex = a[i];
		adjlist[i].firstedge = NULL;
	}
	for ( k = 0; k < edgenumber; k++) {
		cin >> i >> j;
		s = new EdgeNode;
		s->adjvex = j;
		s->next = adjlist[i].firstedge;
		adjlist[i].firstedge = s;
	}
	
}

//析构函数
ADGraph::~ADGraph() {
	EdgeNode *p = NULL;
	EdgeNode *q = NULL;
	for (int i = 0; i < vertexnumber; i++) {
		p = q = adjlist[i].firstedge;
		while (p != NULL) {
			p = p->next;
			delete q;
			q = p;
		}
	}
}

//深度优先
void ADGraph::DFTraverse(int v) {
	int j;
	EdgeNode* p = NULL;
	cout << adjlist[v].vertex << " ";
	visited1[v] = 1;
	p = adjlist[v].firstedge;
	while (p != NULL) {
		j = p->adjvex;
		if (visited1[j] == 0) {
			DFTraverse(j);
		}
		p = p->next;
	}
}

//广度优先遍历
void ADGraph::BFTraverse(int v) {
	int w, j;
	int front = -1, rear = -1;
	EdgeNode*p = NULL;
	cout << adjlist[v].vertex << " ";
	visited2[v] = 1;
	Queue[++rear] = v;
	while (front != rear) {
		w = Queue[++front];
		p = adjlist[w].firstedge;
		while (p != NULL) {
			j = p->adjvex;
			if (visited2[j] == 0) {
				cout << adjlist[j].vertex << " ";
				visited2[j] = 1;
				Queue[++rear] = j;
			}
			p = p->next;
		}
	}
}

int main() {
	string w[5] = {"v0", "v1", "v2", "v3", "v4"};
	ADGraph a(w, 5, 6);
	cout << "深度优先遍历：";
	a.DFTraverse(0);
	cout << endl;
	cout << "广度优先遍历：";
	a.BFTraverse(0);
	return 0;
}