06-图1 列出连通集

​ 给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:

​ 输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式:

​ 按照”{ v1 v2 … v**k }”的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:

8 6
0 7
0 1
2 0
4 1
2 4
3 5

输出样例:

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

步骤

1. 读入顶点数、边数
2. 构造图，插入边
3. DFS搜索, 遍历所有结点
4. 重置visited标记位
5. BFS搜索, 遍历所有结点

编码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MaxVertexNum 10

typedef int Vertex;// 用整形表示顶点
typedef int WeightType; // 权重
typedef char DataType;// 顶点数据，字符型
bool Visited[MaxVertexNum];

typedef struct GNode *PtrToGNode;
typedef PtrToGNode MGraph;
struct GNode {
    int Nv; //顶点数
    int Ne; // 边数
    WeightType G[MaxVertexNum][MaxVertexNum];//邻接矩阵
    DataType Data[MaxVertexNum];//顶点数据，点的权重
};

typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
struct ENode {
    Vertex V1, V2;//有向边<v1,v2>
    WeightType Weight; // 权重
};

typedef struct QNode *PtrToQNode;
// 数组存放元素，最大容量为MaxSize-1，可重复存放元素
struct QNode {
    Vertex *Data;
    int front, rear;
    int MaxSize;
};
typedef PtrToQNode Queue;

Queue CreateQueue(int MaxSize) {
   Queue queue;
   queue = (Queue) malloc(sizeof(struct QNode));
   queue->Data = (Vertex *) malloc(sizeof(Vertex) * MaxSize);
   queue->MaxSize = MaxSize;
   queue->front = 0;
   queue->rear = 0;
   return queue;
}

bool IsEmpty(Queue queue) {
   return queue->rear == queue->front;
}

bool IsFull(Queue queue) {
   return (queue->rear + 1) % queue->MaxSize == queue->front;
}

bool AddQ(Queue queue, Vertex item) {
   bool IsFull(Queue queue);
   if (IsFull(queue)) {
       printf("queue is full!");
       return false;
   }
   queue->rear = (queue->rear + 1) % queue->MaxSize;
   queue->Data[queue->rear] = item;
   return true;
}

Vertex DeleteQ(Queue queue) {
   bool IsEmpty(Queue queue);
   if (IsEmpty(queue)) {
       printf("queue is empty!");
       return -1;
   }
   queue->front = (queue->front + 1) % queue->MaxSize;
   return queue->Data[queue->front];
}

MGraph CreateGraph(int VertexNum, int EdgeNum) {
   // 创建一个有VertexNum个顶点0条边的图
   Vertex V, W;
   MGraph Graph;
   Graph = (MGraph) malloc(sizeof(struct GNode));
   Graph->Nv = VertexNum;
   Graph->Ne = EdgeNum;
   // 初始化二维数组
   for (V = 0; V < Graph->Nv; V++) {
       Visited[V] = false;
       for (W = 0; W < Graph->Nv; W++)
           Graph->G[V][W] = -1;
   }
   return Graph;
}

void InsertEdge(MGraph Graph, Edge E) {
   // 插入边<v1,v2>
   Graph->G[E->V1][E->V2] = E->Weight;
   // 如果是无向图还需要插入反向点，对称矩阵
   Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph() {
   MGraph Graph;
   Edge E;
   int Nv, Ne, i;
   scanf("%d %d", &Nv, &Ne);
   Graph = CreateGraph(Nv, Ne);
   if (Graph->Ne != 0) {
       E = (Edge) malloc(sizeof(struct ENode));
       for (i = 0; i < Graph->Ne; i++) {
           // 循环读入一条边,并插入Graph中
           scanf("%d %d", &E->V1, &E->V2);
           E->Weight = 1;
           InsertEdge(Graph, E);
       }
   }
   return Graph;
}

bool isEdge(MGraph Graph, Vertex V, Vertex W) {
   return Graph->G[V][W] <= -1 ? true : false;
}

void Visit(Vertex V) {
   printf("%d ", V);
}

void BFS(MGraph Graph, Vertex S, void(*Visit)(Vertex)) {
   Queue Q;
   Vertex V, W;
   Q = CreateQueue(MaxVertexNum);
   Visit(S);
   Visited[S] = true;
   AddQ(Q, S);
   while (!IsEmpty(Q)) {
       V = DeleteQ(Q);
       for (W = 0; W < Graph->Nv; W++) {
           // 若W是V的邻接点并且未访问过 Graph->G[V][W]为-1表示v-w未连接，为1表示连接
           if (!Visited[W] && Graph->G[V][W] > 0) {
               Visit(W);
               Visited[W] = true;
               AddQ(Q, W);
           }
       }
   }
}

void DFS(MGraph Graph, Vertex V, void(*Visit)(Vertex)) {
   // 先访问结点v，并将标记置为true
   Visit(V);
   Visited[V] = true;
   Vertex W;
   for (W = 0; W < Graph->Nv; W++) {
       //找到下一个与V点相交的点，同时该点未被访问
       if (Graph->G[V][W] > 0 && !Visited[W]) {
           DFS(Graph, W, Visit);
       }
   }
}

int main() {
   // 1.读入顶点数、边数
   // 2.构造图，插入边
   MGraph Graph = BuildGraph();
   // 3.DFS搜索, 遍历所有结点
   Vertex S;
   for (S = 0; S < Graph->Nv; S++) {
       if (!Visited[S]) {
           printf("{ ");
           DFS(Graph, S, &Visit);
           printf("}\n");
       }
   }
   // 4.重置visited标记位
   for (S = 0; S < MaxVertexNum; S++) {
       Visited[S] = false;
   }
   // 5.BFS搜索, 遍历所有结点
   for (S = 0; S < Graph->Nv; S++) {
       if (!Visited[S]) {
           printf("{ ");
           BFS(Graph, S, &Visit);
           printf("}\n");
       }
   }
   return 0;
}

小结：

1. 图的结构用邻接矩阵还是邻接表？因为需要按顶点顺序输出，而邻接表插入边时并不是按顶点顺序插入，所以邻接表不适用(需要改造，按序插入边)，建议用邻接矩阵。
2. DFS深度优先搜索完成后需要重置标记位visited，否则BFS无法访问
3. 注意顶点是从0开始计算还是从1开始