关于图的遍历
#include<stdio.h>#include<stdlib.h>
#define N 5
typedef struct aa
{
char vexs[N];//顶点数组
int arcs[N][N];//邻接矩阵
}graph;
//图的两种存储方法的结构体
typedef struct bb
{
int adjvex;
struct bb *next;
}edgenode;
typedef struct cc
{
char vertex;
edgenode *link;
}vexnode;
//队列的结构体
typedef struct node
{
int data;
struct node *next;
}linklist;
typedef struct
{
linklist *front,*rear;
}linkqueue;
//void DFS_matrix(graph g,int i,int visited[N]);//图按照邻接矩阵存储时的深度优先搜索遍历
//void DFS_AdjTable(vexnode ga[N],int i,int visited[N]);//图按照邻接矩表存储时的深度优先搜索遍历
void SetNull(linkqueue *q)//置空
{
q->front=(linklist *)malloc(sizeof(linklist));
q->front->next=NULL;
q->rear=q->front;
}
int Empty(linkqueue *q)//判空
{
if(q->front==q->rear)
return 1;
else
return 0;
}
int Front(linkqueue *q)//取队头元素
{
if(Empty(q))
{
printf("queue is empty!");
return -1;
}
else
return q->front->next->data;
}
void ENqueue(linkqueue *q,int x)//入队
{
linklist * newnode=(linklist *)malloc(sizeof(linklist));
q->rear->next=newnode;
q->rear=newnode;
q->rear->data=x;
q->rear->next=NULL;
}
int DEqueue(linkqueue *q)//出队
{
int temp;
linklist *s;
if(Empty(q))
{
printf("queue is empty!");
return -1;
}
else
{
s=q->front->next;
if(s->next==NULL)
{
q->front->next=NULL;
q->rear=q->front;
}
else
q->front->next=s->next;
temp=s->data;
return temp;
}
}
void CreateAdjTable(vexnode ga[N],int e)//创建邻接表
{
int i,j,k;
edgenode *s;
printf("\n输入顶点的内容:");
for(i=0;i<N;i++)
{
//scanf("\n%c",ga[i].vertex);
ga[i].vertex=getchar();
ga[i].link=NULL;//初始化
}
printf("\n");
for(k=0;k<e;k++)
{
printf("输入边的两个顶点的序号:");
scanf("%d%d",&i,&j);//读入边的两个顶点的序号
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=j;
s->next=ga[i].link;
ga[i].link=s;
s=(edgenode *)malloc(sizeof(edgenode));
s->adjvex=i;
s->next=ga[j].link;
ga[j].link=s;
}
}
void DFS_matrix(graph g,int i,int visited[N])
{
printf("%c\n",g.vexs[i]);
visited[i]=1;
for(int j=0;j<N;j++)
if(g.arcs[i][j]==1&&visited[j]==0)//是否有未被访问的邻接点
DFS_matrix(g,j,visited);//递归
}
void DFS_AdjTable(vexnode ga[N],int i,int visited[N])
{
edgenode *p;
printf("%c\n",ga[i].vertex);
visited[i]=1;
p=ga[i].link;
while(p!=NULL)//p是否为空
{
if(visited[p->adjvex]==0)
DFS_AdjTable(ga,p->adjvex,visited);
p=p->next;
}
}
int main()
{
graph g;
int visited[5]={0};//初始化
int visited1[5]={0};
g.vexs[0]='A';
g.vexs[1]='B';
g.vexs[2]='C';
g.vexs[3]='D';
g.vexs[4]='E';
int a[5][5]={{0,1,0,1,1},{ 1,0,1,0,1},{ 0,1,0,0,0},{ 1,0,0,0,0},{ 1,1,0,0,0}};
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
g.arcs[i][j]=a[i][j];
printf("图按照邻接矩阵存储时的深度优先搜索遍历:\n");
DFS_matrix(g,0,visited);
vexnode ga[N];
CreateAdjTable(ga,5);//5为边的条数
printf("图按照邻接表存储时的深度优先搜索遍历:\n");
DFS_AdjTable(ga,0,visited1);//0为开始的顶点的序号
return 0;
}
//运行没有结果,不知道为什么,求大神指导