（1）深度优先类似于前序遍历，广度优先类似于层序遍历

【1】深度优先遍历代码和图例

这是要遍历的图

这是代码的逻辑实现图

#include<bits/stdc++.h>
using namespace std;
typedef char VertexType;
typedef int EdgeType;
#define MAXSIZE 100
struct Mat_Grph{
	VertexType vertex[MAXSIZE];//顶点
	EdgeType arc[MAXSIZE][MAXSIZE];//边
	int vertex_num;
	int edge_num; 
};
int visited[MAXSIZE];
void create_graph(Mat_Grph *G){
	G->vertex_num=9;
	G->edge_num=15;
	G->vertex[0]='A';
	G->vertex[1]='B';
	G->vertex[2]='C';
	G->vertex[3]='D';
	G->vertex[4]='E';
	G->vertex[5]='F';
	G->vertex[6]='G';
	G->vertex[7]='H';
	G->vertex[8]='I';
	for(int i=0;i<G->vertex_num;i++){
		for(int j=0;j<G->vertex_num;j++){
			G->arc[i][j]=0;
		}
	} 
	//A-B A-F
	G->arc[0][1]=1;
	G->arc[0][5]=1;
	//B-C B-G B-I
	G->arc[1][2]=1;
	G->arc[1][6]=1;
	G->arc[1][8]=1;
	//C-D C-I
	G->arc[2][3]=1;
	G->arc[2][8]=1;
	//D-E D-G D-H D-I
	G->arc[3][4]=1;
	G->arc[3][6]=1;
	G->arc[3][7]=1;
	G->arc[3][8]=1;
	//E-F E-H
	G->arc[4][5]=1;
	G->arc[4][7]=1;
	//F-G
	G->arc[5][6]=1;
	//G-H
	G->arc[6][7]=1;
	for(int i=0;i<G->vertex_num;i++){
		for(int j=0;j<G->vertex_num;j++){
			G->arc[j][i]=G->arc[i][j];
		}
	}
}
void dfs(Mat_Grph G,int i){
	visited[i]=1;
	cout<<G.vertex[i]<<endl;
	for(int j=0;j<G.vertex_num;j++)
	{
		if(G.arc[i][j]==1&&visited[j]==0){
			dfs(G,j);
		}
	}
}
int main()
{
	Mat_Grph G;
	create_graph(&G);//图的创建 
	for(int i=0;i<G.vertex_num;i++){
		visited[i]=0;
	}//顶点有没有被访问过 
	dfs(G,0);//A的下标 
}

【2】广度优先遍历

#include<bits/stdc++.h>
using namespace std;
typedef char VertexType;
typedef int EdgeType;
#define MAXSIZE 100
struct Mat_Grph{
	VertexType vertex[MAXSIZE];
	EdgeType arc[MAXSIZE][MAXSIZE];
	int vertex_num;
	int edge_num; 
};
int visited[MAXSIZE];
int front=0;
int rear=0;
int queue1[MAXSIZE];
void create_graph(Mat_Grph *G){
	G->vertex_num=9;
	G->edge_num=15;
	G->vertex[0]='A';
	G->vertex[1]='B';
	G->vertex[2]='C';
	G->vertex[3]='D';
	G->vertex[4]='E';
	G->vertex[5]='F';
	G->vertex[6]='G';
	G->vertex[7]='H';
	G->vertex[8]='I';
	for(int i=0;i<G->vertex_num;i++){
		for(int j=0;j<G->vertex_num;j++){
			G->arc[i][j]=0;
		}
	} 
	//A-B A-F
	G->arc[0][1]=1;
	G->arc[0][5]=1;
	//B-C B-G B-I
	G->arc[1][2]=1;
	G->arc[1][6]=1;
	G->arc[1][8]=1;
	//C-D C-I
	G->arc[2][3]=1;
	G->arc[2][8]=1;
	//D-E D-G D-H D-I
	G->arc[3][4]=1;
	G->arc[3][6]=1;
	G->arc[3][7]=1;
	G->arc[3][8]=1;
	//E-F E-H
	G->arc[4][5]=1;
	G->arc[4][7]=1;
	//F-G
	G->arc[5][6]=1;
	//G-H
	G->arc[6][7]=1;
	for(int i=0;i<G->vertex_num;i++){
		for(int j=0;j<G->vertex_num;j++){
			G->arc[j][i]=G->arc[i][j];
		}
	}
}
void bfs(Mat_Grph G){
	int i=0;
	visited[i]=1;//A的顶点 
	cout<<G.vertex[i]<<endl;
	queue1[rear]=i;
	rear++;
	while(front!=rear){
	i=queue1[front];//出队 
	front++;
	for(int j=0;j<G.vertex_num;j++)
	{
		if(G.arc[i][j]==1&&visited[j]==0){
			visited[j]=1;
			cout<<G.vertex[j]<<endl;
			queue1[rear]=j;//入队 
			rear++;
		}
	}
	}
}
int main()
{
	Mat_Grph G;
	create_graph(&G);//图的创建 
	for(int i=0;i<G.vertex_num;i++){
		visited[i]=0;
	}//顶点有没有被访问过 
	bfs(G);//层序遍历 
}

（2）最小生成树