|
|
发表于 2018-4-21 18:57:28
|
显示全部楼层
#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100 // 最大顶点数
#define FALSE 0
#define TRUE 1
typedef int Boolean; // 这里我们定义Boolean为布尔类型，其值为TRUE或FALSE
Boolean visited[MAXVEX];
typedef int ElemType;
typedef struct
{
char vexs[MAXVEX]; // 顶点表
int arc[MAXVEX][MAXVEX]; // 邻接矩阵
int numVertexes, numEdges; // 图中当前的顶点数和边数
} MGraph;
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct {
QueuePtr front, rear; // 队头、尾指针
} LinkQueue;
void initQueue(LinkQueue *q)
{
q->front=q->rear=(QueuePtr)malloc(sizeof(QNode));
if( !q->front )
exit(0);
q->front->next = NULL;
}
void EnQueue(LinkQueue *q, ElemType e)
{
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if( p == NULL )
exit(0);
p->data = e;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
int DeQueue(LinkQueue *q, ElemType *e)
{
QueuePtr p;
if( q->front == q->rear )
return 0;
p = q->front->next;
*e = p->data;
q->front->next = p->next;
if( q->rear == p )
q->rear = q->front;
free(p);
return 1;
}
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->numVertexes, &G->numEdges);
printf("请输入各个顶点:\n");
for( i=0; i < G->numVertexes; i++ )
{
scanf("%c", &G->vexs[i]);
}
for( i=0; i < G->numVertexes; i++ )
{
for( j=0; j < G->numVertexes; j++ )
{
G->arc[i][j] =0; // 邻接矩阵初始化
}
}
for( k=0; k < G->numEdges; k++ )
{
printf("请输入边(Vi,Vj)上的下标i,并将权标为1表示连通:\n");
fflush(stdin);
scanf("%d %d", &i, &j);
G->arc[i][j] = 1;
G->arc[j][i] = G->arc[i][j]; // 是无向网图，对称矩阵
}
}
void PrintVexs(MGraph*G)
{
int i,j;
printf("当前无向图的邻接矩阵为:\n");
for(i=0;i<G->numVertexes;i++)
{
for(j=0;j<G->numVertexes;j++)
{
printf("%2d ",G->arc[i][j]);
}
printf("\n");
}
printf("\n");
}
void BFSTraverse(MGraph *G)
{
int i,j;
LinkQueue Q;
for(i=0;i<G->numVertexes;i++)
{
visited[i]=FALSE;
}
initQueue(&Q);
for(i=0;i<G->numVertexes;i++)
{
if(!visited[i])
{
printf("%c ",G->vexs[i]);
visited[i]=TRUE;
EnQueue(&Q,i);
while(!QueueEmpty(&Q))
{
DeQueue(&Q,&i);
for(j=0;j<G->numVertexes;j++)
{
if(G->arc[i][j]==1&&!visited[j])
{
printf("%c",G->vexs[i]);
visited[i]=TRUE;
EnQueue(&Q,i);
}
}
}
}
}
}
int main()
{
MGraph*G;
G=(MGraph*)malloc(sizeof(MGraph));
CreateMGraph(G);
PrintVexs(G);
BFSTraverse(G);
printf("\n");
return 0;
}
|
|
[复制链接]
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2017-11-27 14:03:30
）
置顶卡
千斤顶
显身卡
发表于 2017-11-27 20:52:45
