#include <stdio.h>
typedef int datatype;
#define maxsize 1024
# define n 100
typedef char VEXTYPE;
typedef float ADJTYPE;
typedef struct
{
VEXTYPE vexs[n] ;
ADJTYPE arcs[n][n] ;
int num ;
}GRAPH;
void GraphInit(GRAPH *L)
{
L->num=0;
}
int GraphVexs(GRAPH *L)
{
return(L->num);
}
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf(" Please enter the number of vertices: ");
scanf("%d",&L->num);
printf(" Please enter information for each vertex ( Single symbol) : ");
for(i=0;i<L->num;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}
printf(" Please enter the information of the edge weight matrix: ");
for(i=0;i<L->num;i++)
{
for(j=0;j<L->num;j++)
{
scanf("%f",&L->arcs[i][j]);
}
}
printf(" The diagram is created! ");
}
void GraphOut(GRAPH L)
{
int i,j;
printf("n The number of vertices of the graph is: %d",L.num);
printf("n The information of each vertex of the graph is: n");
for(i=0;i<L.num;i++)
printf("%c ",L.vexs[i]);
printf("n The information of the edge weight matrix of the figure is: n");
for(i=0;i<L.num;i++)
{
for(j=0;j<L.num;j++)
{
printf("%6.2f ",L.arcs[i][j]);
}
printf("n");
}
printf(" The graph has been output! ");
}
void DFS(GRAPH g,int qidian,int mark[])
//Starting from the qidian point, depth first travels through the vertices that can be accessed in graph g
{
int v1;
mark[qidian]=1;
printf("%c ",g.vexs[qidian]);
for(v1=0;v1<g.num;v1++)
{
if(g.arcs[qidian][v1]!=0&&mark[v1]==0)
DFS(g,v1,mark);
}
}
void GraphDFS(GRAPH g)
//Depth-first traversal graph g can access each vertex
{
int qidian,v,v1,mark[maxsize];
printf("n Deep travel: ");
printf("n Please enter the subscript of the starting point: ");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}
typedef int DATATYPE; //The data type of the queue element
typedef struct
{
DATATYPE data[maxsize]; //Element in the team
int front,rear; //The subscript of the header element and the subscript of the position behind the header element
} SEQQUEUE;
void QueueInit(SEQQUEUE *sq)
//Empty the sequence loop queue sq (initialized)
{
sq->front=0;
sq->rear=0;
}
int QueueIsEmpty(SEQQUEUE sq)
//If the sequential loop queue sq is empty, it returns 1 on success, or 0 on failure
{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//Save the queue head element of the sequential loop queue sq to the address indicated by e, return 1 on success, 0 on failure
{
if (QueueIsEmpty(sq))
{ printf("queue is empty!n");return 0;}
else
{ *e=sq.data[(sq.front)]; return 1;}
}
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//Put the element x at the end of the queue sq, return 1 on success, 0 on failure
{
if (sq->front==(sq->rear+1)%maxsize)
{
printf("queue is full!n");
return 0;
}
else
{
sq->data[sq->rear]=x;
sq->rear=(sq->rear+1)%maxsize;
return(1);
}
}
int QueueOut(SEQQUEUE *sq)
//Remove the first element of the queue sq team from the queue, return 1 on success, return 0 on failure
{
if (QueueIsEmpty(*sq))
{
printf("queue is empty!n");
return 0;
}
else
{
sq->front=(sq->front+1)%maxsize;
return 1;
}
}
void BFS(GRAPH g,int v,int mark[])
//Breadth first travel from v to the vertices that can be accessed in graph g
{
int v1,v2;
SEQQUEUE q;
QueueInit(&q);
QueueIn(&q,v);
mark[v]=1;
printf("%c ",g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,&v1);
QueueOut(&q);
for(v2=0;v2<g.num;v2++)
{
if(g.arcs[v1][v2]!=0&&mark[v2]==0)
{
QueueIn(&q,v2);
mark[v2]=1;
printf("%c ",g.vexs[v2]);
}
}
}
}
void GraphBFS(GRAPH g)
//Depth-first traversal graph g can access each vertex
{
int qidian,v,v1,mark[maxsize];
printf("n Breadth tour: ");
printf("n Please enter the subscript of the starting point: ");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}
void main()
{
GRAPH tu;
GraphCreate(&tu);
GraphOut(tu);
GraphDFS(tu);
GraphBFS(tu);
}