#include<stdio.h>
#include<iostream>
using namespace std;
#include<stdlib.h>
#define Maxn 100//最大顶点数
//队列结构
typedef struct {
int top;
int rear;
char data[Maxn];
}Q;
void Init(Q *q){
q->top=0;
q->rear=0;
}
bool IsEmpty(Q q){
return q.rear==q.top;
}
void push(Q*q,char t){
q->data[q->rear]=t;
q->rear++;
}
void pop(Q*q){
if(IsEmpty(*q)){
return ;
}
q->top++;
}
char GetTop(Q q){
if(IsEmpty(q)){
return '#';
}
return q.data[q.top];
}
typedef struct{
char vex[Maxn];//顶点表
int arc[Maxn][Maxn];//邻接矩阵，权值为int类型
int vexnum,arcnum; //图的当前顶点数和边数。
}Graph;
//确定顶点再顶点表中的位置；
int LocatedVex(Graph g,char v){
for(int i=0;i<g.vexnum;i++){
if(v==g.vex[i]){
return i;
}
}
return -1;
}
//邻接矩阵建立无向网
Graph CreatG(){
Graph g;
printf("请输入顶点的数量和边的数量：\n");
cin>>g.vexnum>>g.arcnum;
printf("请输入每个顶点的值：\n");
for(int i=0;i<g.vexnum;i++){
cin>>g.vex[i];
//scanf("%c",&(g.vex[i]));error
//g.vex[i]=getchar();error
}
for(int i=0;i<g.vexnum;i++){
for(int j=0;j<g.vexnum;j++){
g.arc[i][j]=0;
}
}
printf("请输入两个顶点，以及他们边的权值：\n");
for(int k=0;k<g.arcnum;k++){
char v1,v2;//两个顶点
int w;//两个顶点之间边的权值。
scanf(" %c %c %d",&v1,&v2,&w);
int i= LocatedVex(g,v1);
int j= LocatedVex(g,v2);
g.arc[i][j]=w;
g.arc[j][i]=w;
}
return g;
}
//邻接矩阵建立有向网
Graph DirCreatG(){
Graph g;
printf("请输入顶点的数量和边的数量：\n");
cin>>g.vexnum>>g.arcnum;
printf("请输入每个顶点的值：\n");
for(int i=0;i<g.vexnum;i++){
cin>>g.vex[i];
//scanf("%c",&(g.vex[i]));error
//g.vex[i]=getchar();error
}
for(int i=0;i<g.vexnum;i++){
for(int j=0;j<g.vexnum;j++){
g.arc[i][j]=0;
}
}
printf("请输入两个顶点，以及他们边的权值：\n");
for(int k=0;k<g.arcnum;k++){
char v1,v2;//两个顶点
int w;//两个顶点之间边的权值。
scanf(" %c %c %d",&v1,&v2,&w);
int i= LocatedVex(g,v1);
int j= LocatedVex(g,v2);
g.arc[i][j]=w;
}
return g;
}
//DFS深度优先遍历无向网的邻接矩阵
int visit[Maxn];
void DFS(Graph g,int v){
cout<<g.vex[v]<<" ";//访问第v个结点
visit[v]=1;
for(int w=0;w<g.vexnum;w++){
if(g.arc[v][w]!=0&&(!visit[w]))
DFS(g,w);
}
}
//BFS广度优先遍历无向网的邻接矩阵
void BFS(Graph g) {
for(int i=0;i<Maxn;i++){
visit[i]=0;
}
Q q;
Init(&q);
for(int i=0;i<g.vexnum;i++){
if(!visit[i]){
cout<<g.vex[i]<<" ";
visit[i]=1;
push(&q,i);
while(!IsEmpty(q)){
pop(&q);
for(int j=0;j<g.vexnum;j++){
if(!visit[j]&&g.arc[i][j]!=0){
cout<<g.vex[j]<<" ";
visit[j]=1;
push(&q,j);
}
}
}
}
}
}
int main(){
Graph g=CreatG();
int visit[g.vexnum]={0};
cout<<"邻接矩阵："<<endl;
for(int i=0;i<g.vexnum;i++){
for(int j=0;j<g.vexnum;j++){
printf("%d ",g.arc[i][j]);
}
printf("\n");
}
printf("请输入遍历开始结点n=");
int n;
cin>>n;
printf("\n深度优先遍历DFS:");
DFS(g,n-1);
printf("\n广度优先遍历DFS:");
BFS(g);
}
