广度遍历输出连通集
输入第1行给出2个整数N和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。我用结构体Gpoint数组存储图的顶点，用指针数组建立邻接链表。BFS中队列也是通过指针对顶点进行访问。有的输入会运行出错。
#include <stdio.h>#include <malloc.h>
typedef struct Graph
{
int weight;
int distance;
int color;//0为白色，1为灰色，2为黑色
}Gpoint,*Graphp;
//链表
typedef struct List
{
Graphp data;//指向数组元素的指针
struct List *next;
}Graph_List;
//向链表添加节点
void AddList(Graph_List *head,Graphp s);
//创建邻接链表
Graph_List *CreatList(Graphp s1,Graphp s2);
//队列
typedef struct Node{
Graphp data;//指向节点的指针
Node *next;
}QNode;
//队列指针
typedef struct{
QNode *rear,*front;//指向队尾和队头节点
}LinkQuene;
//队列初始化
LinkQuene *CreateQNode();
//入队
void AddQ(LinkQuene *PtrQ,Graphp tree);
int IsEmptyQ(LinkQuene *PtrQ);
//出队用头结点
Graphp DeleteQ(LinkQuene *PtrQ);
int main()
{
int N,E;
//freopen("in.txt", "r", stdin);
printf("输入节点个数和边的条数\n");
scanf("%d%d",&N,&E);
Gpoint graph[N];
//用链表直接指向数组graph的节点
Graph_List *graphlist[N];//指针数组（注意*的位置）
int i,j;
for(i=0;i<N;i++)
{
graph[i].weight=i;
graph[i].color=0;
}
int a,b;//接收节点权值
int num=0;//记录链表条数
int condition1=0;
int condition2=0;//判断是否需要新建节点
Graph_List *p;
printf("开始输入\n");
//输入为无向图
//按边的形式(两个)输入
for(i=0;i<E;i++)
{
scanf("%d%d",&a,&b);
for(j=0;j<num;j++)
{
/*首先判断如果输入有1个和其他邻接链表的头节点相同
将另一个节点放入该头结点的链表中*/
if(graphlist[j]->data->weight==a)
{
AddList(graphlist[j],&(graph[b]) );//graph[a]和graph[b]只能用于元素都是0~N的整数
condition1=1;
break;
}
else if(graphlist[j]->data->weight==b)
{
AddList(graphlist[j],&( graph[a] ) );
condition1=1;
break;
}
/*如果两个节点都不是头节点，为了能成功遍历到下一层，
以在之前链表中先出现的节点做为新链表的头节点*/
p=graphlist[j]->next;
while(p)
{
if(p->data->weight==a)
{
graphlist[num]=CreatList( &(graph[a]) , &(graph[b]) );
condition1=1;
condition2=1;
break;
}
else if(p->data->weight==b)
{
graphlist[num]=CreatList( &(graph[b]) , &(graph[a]) );
condition1=1;
condition2=1;
break;
}
p=p->next;
}
}
if(condition1==0) graphlist[num++]=CreatList( &(graph[a]) , &(graph[b]) );
else condition1=0;
if(condition2==1) num++;//防止在while中num加1后再次进入for循环
else condition2=0;
}
for(j=0;j<3;j++)
{
p=graphlist[j];
while(p)
{
printf("%d ",p->data->weight);
p=p->next;
}
printf("\n");
}
printf("广度遍历\n");
LinkQuene *PtrQ=CreateQNode();
Graphp vector;
//广度优先
for(j=0;j<num;j++)//选择每一条链表的头节点作为源节点
{
AddQ(PtrQ,graphlist[j]->data);
while( !IsEmptyQ(PtrQ) )
{
vector=DeleteQ(PtrQ);
for(i=j;i<num;i++)//后面是否还有节点 i=j?
if(vector->weight==graphlist[i]->data->weight)
{
p=graphlist[i]->next;
while(p)
{
//防止由于节点有多条边而导致该节点被重复加入堆栈
if( p->data->color==1 || p->data->color==2 )
{
p=p->next;
continue;//后面的节点不一定都是走过的
}
AddQ(PtrQ,p->data);
p->data->color=1;
p=p->next;
}
break;//if语句只需执行1次
}
//防止由于节点有多条边而导致该节点被重复输出
if(vector->color!=2) { printf("%d ",vector->weight); vector->color=2; }
}
printf("\n");//连通集遍历完成
}
return 0;
}
//向链表添加节点
void AddList(Graph_List *head,Graphp s)
{
Graph_List *p1=head;
while(p1->next)
p1=p1->next;//放到链尾
Graph_List *p2=(Graph_List*)malloc( sizeof(Graph_List) );
p2->data=s;
p2->next=NULL;
p1->next=p2;
}
//创建邻接链表
Graph_List *CreatList(Graphp s1,Graphp s2)
{
Graph_List *p1=(Graph_List*)malloc( sizeof(Graph_List) );
//第一次输入
p1->data=s1;
Graph_List *head=p1;
//第二次输入
p1=(Graph_List*)malloc( sizeof(Graph_List) );
p1->data=s2;
head->next=p1;
p1->next=NULL;
return head;
}
//队列初始化
LinkQuene *CreateQNode()
{
LinkQuene *PtrQ=(LinkQuene*)malloc( sizeof(LinkQuene) );
PtrQ->front=NULL;
PtrQ->rear=NULL;
return PtrQ;
}
//入队
void AddQ(LinkQuene *PtrQ,Graphp tree)
{
QNode *Q=(QNode*)malloc( sizeof(QNode) );//Q用完之后不能释放内存，因为两个指针指向同一块内存空间
Q->data=tree;
Q->next=NULL;
if(PtrQ->front==NULL) PtrQ->front=Q;
else PtrQ->rear->next=Q;//指针变化后指针内容得到保存
PtrQ->rear=Q;
PtrQ->rear->next=NULL;
}
int IsEmptyQ(LinkQuene *PtrQ)
{
if(PtrQ->front==NULL)
{
PtrQ->rear=NULL;
return 1;//队列为空
}
else return 0;
}
//出队用头结点
Graphp DeleteQ(LinkQuene *PtrQ)
{
//暂时存储
QNode *Q;
Graphp Tree;
Q=PtrQ->front;
Tree=Q->data;
PtrQ->front=PtrQ->front->next;//头指针指向下一个节点
free(Q);//放到最后，front和Q指向同一空间
return Tree;
}
根据调试，函数部分没有问题，问题应该出在main函数里面。例如输入
4 4
0 1
0 2
1 3
2 3
本来最后一个邻接链表应该是2 3，不知道为什么是3 2.运用printf发现在输入2 3后程序并没有在p->data->weight=2的时候执行if(p->data->weight==a)的内容，反而在p->data->weight=3的时候执行了if(p->data->weight==b)的内容。输入
8 6
0 7
0 1
2 0
4 1
2 4
3 5
邻接链表创建成功，但是无法进行广度遍历
以上是 广度遍历输出连通集 的全部内容， 来源链接： utcz.com/p/195549.html
