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

这篇具有很好参考价值的文章主要介绍了浙江大学第六周数据结构之06-图1 列出连通集。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目详情：

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

输入格式:

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

输出格式:

按照"{ v1 v2 ... vk }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:

输出样例:

{ 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] == false
      DFS(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数组用于记录当前元素是否访问过，如果访问过，说明该元素已经存在于之前建立的一个连通集中了文章来源地址https://www.toymoban.com/news/detail-610693.html

代码实现：

/*
利用二维邻接矩阵创建图
(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;
}

到了这里，关于浙江大学第六周数据结构之06-图1 列出连通集的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！