深圳网站建设的公,网站安装php,页面跳转,网络营销师题目详情#xff1a;
给定一个有N个顶点和E条边的无向图#xff0c;请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时#xff0c;假设我们总是从编号最小的顶点出发#xff0c;按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0
给定一个有N个顶点和E条边的无向图请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时假设我们总是从编号最小的顶点出发按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0N≤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;
}
