C语言邻接矩阵深度优先与广度优先
时间: 2023-12-10 17:04:02 浏览: 73
C语言中,邻接矩阵是一种常用的图的存储方式。在邻接矩阵中,矩阵的行和列分别表示图中的顶点,矩阵中的元素表示两个顶点之间是否有边相连。如果有,则为1,否则为0。邻接矩阵的深度优先遍历和广度优先遍历如下:
深度优先遍历:
1. 从图中任意一个顶点开始遍历,将该顶点标记为已访问。
2. 依次访问该顶点的邻接点,如果邻接点未被访问,则递归访问该邻接点。
3. 重复步骤2,直到该顶点的所有邻接点都被访问过。
4. 从未被访问的顶点中选择一个顶点,重复步骤2和步骤3,直到所有顶点都被访问过。
广度优先遍历:
1. 从图中任意一个顶点开始遍历,将该顶点标记为已访问,并将该顶点入队。
2. 从队列中取出一个顶点,依次访问该顶点的邻接点,如果邻接点未被访问,则将该邻接点标记为已访问,并将该邻接点入队。
3. 重复步骤2,直到队列为空。
相关问题
邻接矩阵广度优先遍历c语言算法代码
以下是邻接矩阵广度优先遍历的C语言算法代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // 最大顶点数
int arc[MAX][MAX]; // 边表二维数组,对,行列的下标对应实际存在的顶点,值为1表示两顶点间有边
int visited[MAX]; // 访问标志数组,0表示未访问,1表示已访问
// 邻接矩阵广度优先遍历算法
void BFS(int v, int n) {
int queue[MAX], front = 0, rear = 0; // 队列
int i, j;
printf("%d ", v); // 访问初始顶点v并标记为已访问
visited[v] = 1;
queue[rear++] = v; // 初始顶点v入队列
while (front != rear) { // 队列不为空时循环
i = queue[front++]; // 出队列
for (j = 0; j < n; j++) {
if (arc[i][j] == 1 && visited[j] == 0) { // 顶点i与顶点j有边且顶点j未被访问
printf("%d ", j); // 访问顶点j并标记为已访问
visited[j] = 1;
queue[rear++] = j; // 顶点j入队列
}
}
}
}
int main() {
int n = 5; // 顶点数
int m = 6; // 边数
int i, j, v1, v2;
// 初始化边表
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
arc[i][j] = 0;
}
}
// 建立边表
for (i = 0; i < m; i++) {
scanf("%d%d", &v1, &v2);
arc[v1][v2] = 1;
arc[v2][v1] = 1;
}
// 初始化访问标志数组
for (i = 0; i < n; i++) {
visited[i] = 0;
}
// 从顶点0开始广度优先遍历
BFS(0, n);
return 0;
}
```
c语言对图进行深度优先和广度优先遍历
在 C 语言中,可以使用邻接矩阵或邻接表来表示图。下面给出两种遍历图的方法。
1. 深度优先遍历
深度优先遍历使用栈来实现。具体步骤如下:
1. 从初始节点开始,将其标记为已访问,并将其压入栈中。
2. 从栈中弹出一个节点,访问它的邻居节点。
3. 对于未访问的邻居节点,将其标记为已访问,并将其压入栈中。
4. 重复步骤 2 和 3,直到栈为空。
以下是使用邻接矩阵表示图的深度优先遍历的代码示例:
```c
#define MAX_SIZE 100
int visited[MAX_SIZE]; // 记录节点是否被访问过
void dfs_matrix(int graph[][MAX_SIZE], int n, int start) {
int stack[MAX_SIZE], top = -1;
stack[++top] = start;
visited[start] = 1;
while (top != -1) {
int node = stack[top--];
printf("%d ", node);
for (int i = 0; i < n; i++) {
if (graph[node][i] && !visited[i]) {
visited[i] = 1;
stack[++top] = i;
}
}
}
}
```
以下是使用邻接表表示图的深度优先遍历的代码示例:
```c
typedef struct Node {
int val;
struct Node* next;
} Node;
Node* graph[MAX_SIZE]; // 邻接表
void dfs_list(int start) {
int stack[MAX_SIZE], top = -1;
stack[++top] = start;
visited[start] = 1;
while (top != -1) {
int node = stack[top--];
printf("%d ", node);
Node* cur = graph[node];
while (cur) {
int neighbor = cur->val;
if (!visited[neighbor]) {
visited[neighbor] = 1;
stack[++top] = neighbor;
}
cur = cur->next;
}
}
}
```
2. 广度优先遍历
广度优先遍历使用队列来实现。具体步骤如下:
1. 从初始节点开始,将其标记为已访问,并将其加入队列中。
2. 从队列中取出一个节点,访问它的邻居节点。
3. 对于未访问的邻居节点,将其标记为已访问,并将其加入队列中。
4. 重复步骤 2 和 3,直到队列为空。
以下是使用邻接矩阵表示图的广度优先遍历的代码示例:
```c
void bfs_matrix(int graph[][MAX_SIZE], int n, int start) {
int queue[MAX_SIZE], front = 0, rear = 0;
queue[rear++] = start;
visited[start] = 1;
while (front != rear) {
int node = queue[front++];
printf("%d ", node);
for (int i = 0; i < n; i++) {
if (graph[node][i] && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
}
```
以下是使用邻接表表示图的广度优先遍历的代码示例:
```c
void bfs_list(int start) {
int queue[MAX_SIZE], front = 0, rear = 0;
queue[rear++] = start;
visited[start] = 1;
while (front != rear) {
int node = queue[front++];
printf("%d ", node);
Node* cur = graph[node];
while (cur) {
int neighbor = cur->val;
if (!visited[neighbor]) {
visited[neighbor] = 1;
queue[rear++] = neighbor;
}
cur = cur->next;
}
}
}
```