企业培训网站,wordpress一直维护,网站收录下降,模板网站最大缺点题目
给定一个有N个顶点和E条边的无向图#xff0c;请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时#xff0c;假设我们总是从编号最小的顶点出发#xff0c;按编号递增的顺序访问邻接点。
输入格式: 输入第1行给出2个整数N(0N≤10)和E…题目
给定一个有N个顶点和E条边的无向图请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时假设我们总是从编号最小的顶点出发按编号递增的顺序访问邻接点。
输入格式: 输入第1行给出2个整数N(0N≤10)和E分别是图的顶点数和边数。随后E行每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式: 按照{ v 1 v 2 … 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 }
代码
#include stdio.h
#include stdlib.h
#include stdbool.h#define MAX_VERTEX_NUM 10
#define ELEMENT_TYPE int
#define ERROR -1
#define QUEUE_SIZE 10typedef int Vertex;struct _Queue
{ELEMENT_TYPE *data;int front, rear;int size;
};
typedef struct _Queue *Queue;struct _Edge
{int v, w;
};
typedef struct _Edge *Edge;struct _MGraph
{int nv, ne;int graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
};
typedef struct _MGraph *MGraph;Queue createQueue(ELEMENT_TYPE size);
bool isFull(Queue q);
bool isEmpty(Queue q);
bool addQ(Queue q, ELEMENT_TYPE x);
ELEMENT_TYPE delQ(Queue q);void initVisited(bool visited[]);
bool isEdge(MGraph g, Vertex v, Vertex w);
MGraph createGraph(int numVertices);
void insertEdge(MGraph g, Edge e);
MGraph buildGraph();
void dfs(MGraph g, Vertex v);
void bfs(MGraph g, Vertex s);
void listComponentsViaDFS(MGraph g);
void listComponentsViaBFS(MGraph g);bool visited[MAX_VERTEX_NUM] {false};/*
06-图1 列出连通集难度1星
重要度3星必须掌握的2种图的遍历方式。无向图用0,1表示顶点间是否有边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 }*/
int main()
{MGraph g buildGraph();listComponentsViaDFS(g);initVisited(visited);listComponentsViaBFS(g);free(g);return 0;
}// 初始化Visited数组将所有顶点的访问状态初始化为false
void initVisited(bool visited[])
{Vertex v;for (v 0; v MAX_VERTEX_NUM; v)visited[v] false;
}bool isEdge(MGraph g, Vertex v, Vertex w)
{return g-graph[v][w] 1;
}MGraph createGraph(int numVertices)
{MGraph g (MGraph)malloc(sizeof(struct _MGraph));g-nv numVertices;g-ne 0;Vertex v, w;for (v 0; v g-nv; v)for (w 0; w g-nv; w)g-graph[v][w] 0; // 初始化为0表示无边return g;
}void insertEdge(MGraph g, Edge e)
{ //(V,W)之间双向置为1表示无向有边g-graph[e-v][e-w] 1;g-graph[e-w][e-v] 1;
}MGraph buildGraph()
{MGraph g;Edge e;Vertex v;int nv, ne;scanf(%d %d, nv, ne);g createGraph(nv);if (ne){g-ne ne;e (Edge)malloc(sizeof(struct _Edge));for (v 0; v g-ne; v){scanf(%d %d, e-v, e-w);insertEdge(g, e);}free(e);}return g;
}void dfs(MGraph g, Vertex v)
{visited[v] true;printf(%d , v);Vertex w;for (w 0; w g-nv; w){if (!visited[w] isEdge(g, v, w)){dfs(g, w);}}
}// 使用深度优先搜索列出连通集
void listComponentsViaDFS(MGraph g)
{Vertex v;for (v 0; v g-nv; v){if (!visited[v]){printf({ );dfs(g, v);printf(}\n);}}
}// 广度优先搜索
void bfs(MGraph g, Vertex s)
{Vertex v, w;Queue q createQueue(g-nv);printf(%d , s);visited[s] true;addQ(q, s);while (!isEmpty(q)){v delQ(q);for (w 0; w g-nv; w){if (!visited[w] isEdge(g, v, w)){printf(%d , w);visited[w] true;addQ(q, w);}}}free(q-data);free(q);
}// 使用广度优先搜索列出连通集
void listComponentsViaBFS(MGraph g)
{Vertex v;for (v 0; v g-nv; v){if (!visited[v]){printf({ );bfs(g, v);printf(}\n);}}
}// 创建队列Size为队列的最大容量
Queue createQueue(ELEMENT_TYPE size)
{Queue q (Queue)malloc(sizeof(struct _Queue));q-data (ELEMENT_TYPE *)malloc(size * sizeof(ELEMENT_TYPE));q-front q-rear 0;q-size QUEUE_SIZE;return q;
}// 判断队列是否已满
bool isFull(Queue q)
{return (q-rear 1) % q-size q-front;
}// 判断队列是否为空
bool isEmpty(Queue q)
{return q-front q-rear;
}// 入队操作
bool addQ(Queue q, ELEMENT_TYPE x)
{if (isFull(q)){printf(Full.\n);return false;}else{q-rear (q-rear 1) % q-size; // 队尾索引加1并考虑循环的情况q-data[q-rear] x; // 将X存入队尾位置return true;}
}// 出队操作
ELEMENT_TYPE delQ(Queue q)
{if (isEmpty(q)){printf(Empty.\n);return ERROR;}else{q-front (q-front 1) % q-size; // 队头索引加1并考虑循环的情况return q-data[q-front]; // 返回队头元素}
}
执行结果 小结
基础的对图的两种方式的遍历需要熟练掌握。
