浙江大学第六周数据结构之06-图1 列出连通集

题目详情：

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

输入格式:

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

输出格式:

按照"{ v1​ v2​ ... vk​ }"的格式，每行输出一个连通集。先输出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）定义图的数据结构，分为图节点与边节点两部分

/*图节点*/
typedef struct GraphNode* PToGraphNode;
struct GraphNode {int VertexNums;int EdgeNums;int WeightBetweenTwoEdge[MAX_SIZE][MAX_SIZE];
};
typedef PToGraphNode MatrixGraph;
/*边界点*/
typedef struct EdgeNode* PToEdgeNode;
struct EdgeNode {int Start, End;int Weight;
};
typedef PToEdgeNode Edge;

（2）创建一个没有边的图

MatrixGraph CreateGraph() {int vertixNums;scanf("%d", &vertixNums);MatrixGraph Graph = (MatrixGraph)malloc(sizeof(struct GraphNode));Graph -> VertexNums = vertixNums;Graph -> EdgeNums = 0;for(int i = 0; i < (Graph -> VertexNums); i++) {for(int j = 0; j < (Graph -> VertexNums); j++) {Graph -> WeightBetweenTwoEdge[i][j] = 0;}}return Graph;
}

 （3）插入边

void InsertEdge(MatrixGraph graph, Edge edge) {graph -> WeightBetweenTwoEdge[edge -> Start][edge -> End] = edge -> Weight;graph -> WeightBetweenTwoEdge[edge -> End][edge -> Start] = edge -> Weight;
}

（4）创建图

MatrixGraph BuildGraph() {MatrixGraph graph = CreateGraph();scanf("%d", &(graph -> EdgeNums));if((graph -> EdgeNums) != 0) {for(int i = 0; i < (graph -> EdgeNums); i++) {Edge edge = (Edge)malloc(sizeof(struct EdgeNode));scanf("%d %d", &(edge -> Start), &(edge -> End));edge -> Weight = WEIGHT; InsertEdge(graph, edge); }}return graph;
}

 

（二）DFS的实现（记忆：DFS的D谐音递归）

DFS是通过递归找到一条一条路径

关于图的DFS 有常规思路如下：

void DFS(u) {vis[u] = true;	// 设置为已访问Visit[u]           //访问节点for(从u出发能达到的所有顶点v)	// 枚举从u出发可以到达的所有顶点if vis[v] == false	// 没有被访问DFS(v)	// 递归访问
}void DFSTravel(G) {for(G所有顶点u)    if vis[u] == falseDFS(u)
}

（三）BFS的实现

BFS就是广义化的层序遍历 

BFS常规思路

void BFS(int u) {queue q;q.push(u);inq[u] = true;	// 设置 u 已经入队while(!q.empty()) {Visit[q.front()]        //取出队首元素进行访问for(从u出发可到达所有顶点v)if(inq[v] == false)将 v 入队inq[v] = true}
}void BFSTravel() {for(G所有顶点u) {if(inq[u] == false)BFS(u)}
}

无论是BFS还是DFS，一层循环找到的都是一个图里面的连通集 

BFS和DFS里面设置的Vis数组用于记录当前元素是否访问过，如果访问过，说明该元素已经存在于之前建立的一个连通集中了

代码实现：

/*
利用二维邻接矩阵创建图
(1)定义图的数据结构，分为图节点与边节点两部分
(2)定义创建一个没有边的图的函数
(3)定义插入边的函数
(4)定义创建图的函数
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 11
#define WEIGHT 1
#define TRUE 1
#define FALSE 0
#define NONE -1
/*定义图的数据结构*/
typedef struct MartixGraphNode MartixGraphNode;
typedef MartixGraphNode* MatrixGraph;
struct MartixGraphNode {int VertexNums;int EdgeNums;int Weight[MAX_SIZE][MAX_SIZE];
};
/*定义边的数据结构*/
struct EdgeNode{int Start, End;int Weight;
};
/*创建一个空的图*/
MatrixGraph CreateEmptyGraph(int vertexNums) {MatrixGraph graph = (MatrixGraph)malloc(sizeof(MartixGraphNode));graph->VertexNums = vertexNums;graph->EdgeNums = 0;for(int i = 0; i < vertexNums; i++) {for(int j = 0; j < vertexNums; j++) {graph->Weight[i][j] = 0;}}return graph;
} 
/*插入边*/
void InsertEdge(MatrixGraph graph, int start, int end, int weight) {graph->Weight[start][end] = weight;graph->Weight[end][start] = weight;return;
}
/*建立图*/
MatrixGraph BuildGraph(int vertexNums, int edgeNums) {MatrixGraph graph = CreateEmptyGraph(vertexNums);graph->VertexNums = vertexNums;graph->EdgeNums = edgeNums;for(int i = 0; i < edgeNums; i++) {int start, end;scanf("%d %d", &start, &end);InsertEdge(graph, start, end, WEIGHT);}return graph;
}
/*DFS*/
int Vis[MAX_SIZE];
void DFS(MatrixGraph graph, int index) {Vis[index] = TRUE;printf("%d ", index);for(int i = 0; i < (graph->VertexNums); i++) {if(Vis[i] == FALSE && graph->Weight[i][index] == WEIGHT) {DFS(graph, i);}}return;
}
void Erase() {for(int i = 0; i < MAX_SIZE; i++) {Vis[i] = FALSE;}return;
}
/*队列的数据结构*/
typedef struct QueueNode QueueNode;
typedef QueueNode* Queue;
struct QueueNode {int Data[MAX_SIZE];int Size;int head, rear;
};
void Init(Queue* q) {(*q)->Size = 0;(*q)->head = 0;(*q)->rear = -1;for(int i = 0; i < MAX_SIZE; i++) {(*q)->Data[i] = NONE;}return;
}
int IsFull(Queue* q) {if((*q)->Size == MAX_SIZE) {return TRUE;}else {return FALSE;}
}
int IsEmpty(Queue* q) {if((*q)->Size == 0) {return TRUE;}else {return FALSE;}
}
int Dequeue(Queue* q) {if(IsEmpty(q)) { return;}int front = (*q)->Data[(*q)->head++ % MAX_SIZE];if((*q)->head > 0) {(*q)->Data[(*q)->head - 1] = NONE;}(*q)->Size--;   return front;
}
void Enqueue(Queue* q, int data) {if(IsFull(q)) {return;}(*q)->Data[++(*q)->rear % MAX_SIZE] = data;(*q)->Size++;return; 
}
void BFS(MatrixGraph graph, int index) {Queue q = (Queue)malloc(sizeof(QueueNode));Init(&q);Enqueue(&q, index);Vis[index] = TRUE;while(!IsEmpty(&q)) {int index = Dequeue(&q);printf("%d ", index);for(int i = 0; i < graph->VertexNums; i++) {if(graph->Weight[i][index] == WEIGHT && Vis[i] == FALSE) {Vis[i] = TRUE;Enqueue(&q, i);}}}
}
int main() {int vertexNums, edgeNums;scanf("%d %d", &vertexNums, &edgeNums);MatrixGraph graph = BuildGraph(vertexNums, edgeNums);/*DFS*/    for(int i = 0; i < vertexNums; i++) {if(Vis[i] == FALSE) {printf("{ ");DFS(graph, i);printf("}\n");}}Erase();for(int i = 0; i < vertexNums; i++) {if(Vis[i] == 0) {printf("{ ");BFS(graph, i);printf("}\n");}}return 0;
}