6 6
A B C D E F
A B
A C
B E
C E
A D
D F

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

``````#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版》严蔚敏 李冬梅 吴伟民