题目地址：https://pta.patest.cn/pta/test/558/exam/4/question/9495
由于边数E<(n*(n-1))/2 所以我选用了邻接表实现，优先队列用循环队列实现；
DFS基本思路：
1：选择一个点，标志已经访问过；
2：判断这个点的其他邻接点（访问顺序按题目是从小到大）是否访问过，来选择下一个点；
3：重复第2点直到全部点已经访问过。
伪代码如下
DFS( Vertex v )
{
Visit( V );
Visited[V] = true;
foreach( v->neighbor )
if ( Visited[v->neighbor ] == false )
DFS(v->neighbor );
}
BFS基本思路：
1：选择一个点入队，并访问这个点，标志已经访问过；
2：出队，将这个点未访问过的全部邻点访问并入队；
3：重复第二点直到队列为空；
伪代码如下
BFS ( Vertex v )
{
Visit( v );
Visited[v] = true;
EnQueue(Q, v);
while ( !IsEmpty(Q) )
{
w = DeQueue(Q);
foreach ( w->neighor )
if ( Visited[w->neighor] == false )
{
Visit( w->neighor );
Visited[w->neighor] = true;
EnQueue(Q, w->neighor);
}
}
}
具体代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <dos.h>
#define MaxVertexNum 10
typedef int ElementType;
typedef int Position;
typedef struct QNode {
ElementType *Data; /* 存储元素的数组 */
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
}QNode, *Queue;
typedef struct ENode
{
int ivex; //该边指向的顶点位置
struct ENode * next;
}ENode, *PENode;
typedef int VertexType;
typedef struct VNode
{
VertexType data;
ENode * first_edge;
}VNode;
typedef struct LGraph
{
int vexnum; //图的顶点数目
int edgnum; //图的边的数目
VNode * vexs; //存放顶点的数组
}LGraph;
bool TAG; //用于输出格式
bool visited[MaxVertexNum];
LGraph * LGraph_new();
void LGraph_destroy(LGraph * G);
void LGraph_insert(ENode ** head, int ivex);
void ResetVisit();
void DFS(LGraph * G, int vex);
void BFS(LGraph * G, int vex);
void ListComponents(LGraph * G, void (*func)(LGraph * G, int vex));
//优先队列的基本操作
Queue CreateQueue( int MaxSize );
bool IsFull( Queue Q );
bool AddQ( Queue Q, ElementType X );
bool IsEmpty( Queue Q );
ElementType DeleteQ( Queue Q );
int main()
{
LGraph * G = LGraph_new();
ResetVisit();
ListComponents(G, DFS);
ResetVisit();
ListComponents(G, BFS);
system("pause");
;
}
void ListComponents(LGraph * G, void (*func)(LGraph * G, int vex))
{
int i;
; i < G->vexnum; ++i )
{
if (visited[i] == false)
{
(*func)(G, i);
printf("}\n");
TAG = false;
}
}
}
LGraph * LGraph_new()
{
LGraph * G = (LGraph *)malloc(sizeof(LGraph));
scanf("%d %d", &G->vexnum, &G->edgnum);
G->vexs = (VNode *)malloc(G->vexnum * sizeof(VNode));
int i, v1, v2;
; i < G->vexnum; ++i )
{
G->vexs[i].data = i;
G->vexs[i].first_edge = NULL;
}
; i < G->edgnum; ++i )
{
scanf("%d %d", &v1, &v2);
//由于顶点信息就是顶点坐标
LGraph_insert(&G->vexs[v1].first_edge, v2);
LGraph_insert(&G->vexs[v2].first_edge, v1);
}
return G;
}
void ResetVisit()
{
TAG = false;
memset(visited, false, sizeof(visited));
}
void LGraph_insert(ENode ** head, int ivex)
{
ENode *pnew, *p1, *p2;
pnew = (ENode *)malloc(sizeof(ENode));
pnew->ivex = ivex;
if ( *head == NULL )
{
*head = pnew;
pnew->next = NULL;
}
else
{
if ( (*head)->ivex > ivex ) //没头结点的麻烦
{
pnew->next = *head;
*head = pnew;
}
else
{
for (p1 = *head, p2 = p1->next; p2 != NULL ; p1 = p2, p2 = p1->next )
{
if ( p2->ivex > ivex )
break;
}
pnew->next = p2;
p1->next = pnew;
}
}
}
void DFS(LGraph * G, int vex)
{
if (TAG == false)
{
TAG = true;
printf("{ ");
}
printf("%d ", vex);
visited[vex] = true;
ENode * temp = G->vexs[vex].first_edge;
while( temp != NULL )
{
if (visited[temp->ivex] == false)
{
DFS(G, temp->ivex);
}
temp = temp->next;
}
}
void BFS(LGraph * G, int vex)
{
Queue Q = CreateQueue(G->vexnum);
if (TAG == false)
{
TAG = true;
printf("{ ");
}
printf("%d ", vex);
visited[vex] = true;
AddQ(Q, vex);
while (!IsEmpty(Q))
{
vex = DeleteQ(Q);
ENode * temp = G->vexs[vex].first_edge;
while (temp != NULL)
{
if ( visited[temp->ivex] == false )
{
printf("%d ",temp->ivex);
visited[temp->ivex] = true;
AddQ(Q, temp->ivex);
}
temp = temp->next;
}
}
free(Q->Data);
free(Q);
}
//队列基本操作
Queue CreateQueue( int MaxSize )
{
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
Q->Front = Q->Rear = ;
Q->MaxSize = MaxSize;
return Q;
}
bool IsFull( Queue Q )
{
)%Q->MaxSize == Q->Front);
}
bool AddQ( Queue Q, ElementType X )
{
if ( IsFull(Q) ) {
printf("队列满");
return false;
}
else {
Q->Rear = (Q->Rear+)%Q->MaxSize;
Q->Data[Q->Rear] = X;
return true;
}
}
bool IsEmpty( Queue Q )
{
return (Q->Front == Q->Rear);
}
ElementType DeleteQ( Queue Q )
{
if ( IsEmpty(Q) ) {
printf("队列空");
;
}
else {
Q->Front =(Q->Front+)%Q->MaxSize;
return Q->Data[Q->Front];
}
}