数据结构：输入两个数给m,n分别表示图的结点数和边数，建立图的邻边矩阵

发布网友 发布时间：2022-04-23 02:16

我来回答

共1个回答

热心网友 时间：2023-10-11 09:39

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int visited1[20]={0},visited2[20]={0};
typedef struct
{
char vexs[20];/*顶点表*/
int edges[20][20];
int n,e;
}Mgraph;
typedef struct QNode
{
int data;
struct QNode *next;
int Queusize;
}
QNode,*QueuePtr;//定义队列结点类型
typedef struct
{
QueuePtr front;
QueuePtr rear;
}
LinkQueue;//队列的类型
void InitQueue(LinkQueue *Q)//创建队列
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
Q->front->next=NULL;
}
void EnQueue(LinkQueue *Q,int e)//将元素插入队列
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
int DeQueue(LinkQueue *Q)//将元素出列且返回元素的位置
{
int e;
QueuePtr p;
p=Q->front->next;
e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return (e);
}
int QueueEmpty(LinkQueue *Q)//判断队列是否为空
{
if(Q->front==Q->rear )
return 1;
else
return 0;
}
void CreateMGraph(Mgraph *G)
{

int i,j,k;
printf("输入顶点和边数\n");
scanf("%d %d", &G->n,&G->e);
getchar();
printf("输入%d个顶点\n",G->n);
for(i=0;i<G->n; i++ )
G->vexs[i]=getchar();
for (i = 0;i<G->n; i++)
for (j = 0;j <G->n; j++)
G->edges[i][j]=0;
printf("在矩阵中输入%d个元素:\n",2*(G->e));
for(k = 0;k<2*(G->e);k++)
{
scanf("%d%d",&i,&j);
G->edges[i][j]=1;
}
}
void BFS(Mgraph G,int i)//广度优先遍历
{
int u,j;
LinkQueue Q;
InitQueue(&Q);
printf("%c",G.vexs[i]);
visited2[i]=1;//标记
EnQueue(&Q,i);
while(!QueueEmpty(&Q))
{
i=DeQueue(&Q);
for(j=0;j<G.n;j++)
if(G.edges[i][j]==1&&!visited2[j])
{ printf("%c",G.vexs[j]);
visited2[j]=1;
EnQueue(&Q,j);
}
}

}
void DFSM(Mgraph *G, int i)
{
int j;
printf("%c",G->vexs[i]);
visited1[i]=1;
for(j=0;j<G->n; j++)
{
if(G->edges[i][j]==1&&!visited1[j])
DFSM(G,j);
}
}
main()
{
Mgraph G;
CreateMGraph(&G);
printf("广度:\n");
BFS(G,0);
printf("\n");
printf("深度:\n");
DFSM(&G,0);
}
运行下没问题，有什么问题可以联系。