以邻接矩阵为存储结构，采用深度优先遍历或广度优先遍历，输出图的所有顶点的值（C语言）

题目：

以邻接矩阵为存储结构，采用深度优先遍历或广度优先遍历，输出图的所有顶点的值

测试数据
输入：
6 6
A B C D E F
A B
A C
B E
C E
A D
D F
输出：BACEDF

以邻接矩阵为存储结构，采用深度优先遍历

#include<iostream>
using namespace std;

#define MAXNUM  100

char visited1[MAXNUM];

typedef struct{
	char vexs[MAXNUM];  //顶点 
	int arcs[MAXNUM][MAXNUM];//边 
	int vexnum,arcnum;
}AMGraph; //邻接矩阵的数据类型 

int LocateVex(AMGraph G,char v){
	for(int i = 0; i < G.vexnum; i++){
		if(G.vexs[i] == v)return i;
	}
	return -1;
}

int CreateUNG(AMGraph &G){ //创建无向图 
	char v1,v2;
	cout<<"请输入顶点数和边数："; 
	cin>>G.vexnum>>G.arcnum;
	
	cout<<"请依次输入顶点：";
	for(int i = 0; i < G.vexnum; i++)cin>>G.vexs[i];
	
	for(int j = 0; j < G.vexnum; j++)
		for(int i = 0; i < G.vexnum; i++)
			G.arcs[j][i] = 0;         //初始化邻接矩阵
	cout<<"请依次输入邻接边："<<endl;	 
	for(int k = 0; k < G.arcnum; k++){
		cin>>v1>>v2;
		int i = LocateVex(G,v1);
		int j = LocateVex(G,v2);
		G.arcs[i][j] = 1;
		G.arcs[j][i] = 1;
	}		
	return 1;
}

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

int main(){
	AMGraph G;
	CreateUNG(G);
	for(int j = 0; j < G.vexnum; j++){  //输出邻接矩阵 
		for(int i = 0; i < G.vexnum; i++)
			cout<<G.arcs[j][i]<<"  "; 
		cout<<endl;	
	}
	cout<<endl<<"输出：";
	DFT_AM(G,0);	//第二个参数决定深度优先遍历从哪里开始
}

以邻接矩阵为存储结构，采用广度优先遍历

#include<iostream>
using namespace std;

#define MaxSize 100
typedef struct{ //队列，广度优先遍历需要使用队列 
	int *base;
	int front;
	int rear;
}Seq; 

int Init(Seq &L){    //初始化队列 
	L.base = new int[MaxSize];
	L.front = L.rear = 0;
	return 1;
}

int Enter(Seq &L,int m){     //入队列
	if((L.rear+1)%MaxSize == L.front){
		cout<<"队列已满！";
		return 0; 
	}
	L.base[L.rear] = m;
	L.rear = (L.rear + 1)%MaxSize;
	return 1;
}

int Out(Seq &L,int &m){    // 出队列
	if(L.rear == L.front){
		cout<<"队列空！";
		return 0;
	}
	m = L.base[L.front];
	L.front = (L.front+1)%MaxSize;
	return 1;
}

int JudgeEmpty(Seq L){//判断队列是否为空 
	if(L.rear == L.front){
		return 0;
	}
	return 1;
}

#define MAXNUM  100
char visited2[MAXNUM];
typedef struct{
	char vexs[MAXNUM];  //顶点 
	int arcs[MAXNUM][MAXNUM];//边 
	int vexnum,arcnum;
}AMGraph; //邻接矩阵的数据类型 

int LocateVex(AMGraph G,char v){
	for(int i = 0; i < G.vexnum; i++){
		if(G.vexs[i] == v)return i;
	}
	return -1;
}

int CreateUNG(AMGraph &G){ //创建无向图 
	char v1,v2;
	cout<<"请输入顶点数和边数："; 
	cin>>G.vexnum>>G.arcnum;
	
	cout<<"请依次输入顶点：";
	for(int i = 0; i < G.vexnum; i++)cin>>G.vexs[i];
	
	for(int j = 0; j < G.vexnum; j++)
		for(int i = 0; i < G.vexnum; i++)
			G.arcs[j][i] = 0;         //初始化邻接矩阵
	cout<<"请依次输入邻接边："<<endl;	 
	for(int k = 0; k < G.arcnum; k++){
		cin>>v1>>v2;
		int i = LocateVex(G,v1);
		int j = LocateVex(G,v2);
		G.arcs[i][j] = 1;
		G.arcs[j][i] = 1;
	}		
	return 1;
}

void BFT_AM(AMGraph G,int i){//广度优先遍历邻接矩阵 
	cout<<G.vexs[i];
	visited2[i] = 1;	
	Seq L;//建立辅助队列 
	int m;
	Init(L);
	Enter(L,i);
	while(JudgeEmpty(L)){
		Out(L,m);
		for(int j = 0; j < G.vexnum; j++){
			if(G.arcs[m][j] == 1 && !visited2[j]){
				cout<<G.vexs[j];
				visited2[j] = 1;
				Enter(L,j);
			} 
		}
	} 
}

int main(){
	AMGraph G;
	CreateUNG(G);
	for(int j = 0; j < G.vexnum; j++){  //输出邻接矩阵 
		for(int i = 0; i < G.vexnum; i++)
			cout<<G.arcs[j][i]<<"  "; 
		cout<<endl;	
	}	
	cout<<endl<<"输出（广度优先遍历）：";
	BFT_AM(G,0);////第二个参数决定深度优先遍历从哪里开始
}

参考资料：
《数据结构 C语言版 第2版》严蔚敏 李冬梅 吴伟民