C语言邻接矩阵 图的遍历
作者:
leimingze
,
2023-11-23 00:26:15
,
所有人可见
,
阅读 115
//图的邻接矩阵
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define MAXN 110
typedef struct{
int ver_num;
int edge_num;
char ver[MAXN];
int edges[MAXN][MAXN];
}MGraph;//图的邻接矩阵
typedef struct{
int data[MAXN];
int front,rear;
}SqQueue;//顺序队列
void init_st();//初始化st
void create_graph(MGraph *G);//邻接矩阵的创建
void init_SqQueue(SqQueue *q);//顺序队列初始化
bool SqQueue_empty(SqQueue *q);//顺序队列判空
bool en_SqQueue(SqQueue *q,int e);//顺序队列插入元素
int de_SqQueue(SqQueue *q);//删除顺序队列队头元素,并返回队头
int getfront(SqQueue q);//顺序队列获取队头元素 (不删除)
void init_SqQueue(SqQueue &q)//顺序队列初始化
{
q.front=q.rear=0;
for(int i=0;i<MAXN;i++)q.data[i]=-1;
}
bool SqQueue_empty(SqQueue &q)//顺序队列判空
{
return q.front==q.rear;
}
bool en_SqQueue(SqQueue &q,int e)//顺序队列插入元素
{
if(q.rear>=MAXN)
{
printf("插入失败,顺序队列已满\n");
return false;
}
else
{
q.data[q.rear++]=e;
return true;
}
}
int de_SqQueue(SqQueue &q)//删除顺序队列队头元素
{
if(SqQueue_empty(q))
{
printf("队列为空,删除失败\n");
return -1;
}
return q.data[q.front++];
}
int getfront(SqQueue q)//顺序队列获取队头元素(不删除)
{
return q.data[q.front];
}
bool st[11];
void init_st()//初始化st
{
for(int i=0;i<MAXN;i++)st[i]=false;
}
void create_graph(MGraph *G)//邻接矩阵的创建
{
int n=7,e=7;
G->ver_num=n,G->edge_num=e;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j)G->edges[i][j]=0;
else G->edges[i][j]=INF;
}
}
for(int i=0;i<n;i++)G->ver[i]='A'+i;
G->edges[6][0]=G->edges[0][6]=1;
G->edges[0][1]=G->edges[1][0]=1;
G->edges[0][2]=G->edges[2][0]=1;
G->edges[1][5]=G->edges[5][1]=1;
G->edges[2][5]=G->edges[5][2]=1;
G->edges[2][3]=G->edges[3][2]=1;
G->edges[3][4]=G->edges[4][3]=1;
}
//dfs
void dfs(MGraph G,int v)
{
printf("%c ",G.ver[v]);
st[v]=true;
for(int i=0;i<G.ver_num;i++)
if(!st[i]&&G.edges[v][i]!=INF)
dfs(G,i);
}
void func_dfs(MGraph G)
{
init_st();
printf("DFS\n");
dfs(G,0);
printf("\n");
}
//bfs
void bfs(MGraph &G,SqQueue &q)
{
q.data[q.rear++]=0;
st[0]=true;
while(q.front<q.rear)
{
int t=de_SqQueue(q);
printf("%c ",G.ver[t]);
for(int i=0;i<G.ver_num;i++)
{
if(!st[i]&&G.edges[t][i]!=INF)
{
st[i]=true;
en_SqQueue(q,i);
}
}
}
}
void func_bfs(MGraph G)
{
SqQueue q;
init_SqQueue(q);
init_st();
printf("BFS\n");
bfs(G,q);
printf("\n");
}
int main()
{
MGraph G;
create_graph(&G);
func_dfs(G);
func_bfs(G);
}