c语言邻接矩阵和邻接表
时间: 2023-09-21 10:09:14 浏览: 60
邻接矩阵实现图的深度优先遍历和广度优先遍历:
深度优先遍历:
1. 定义一个栈,将起始节点入栈。
2. 当栈不为空时,取出栈顶节点,访问该节点,并将其未被访问的邻居节点入栈。
3. 标记已访问的节点。
4. 重复步骤2和3,直到栈为空。
邻接矩阵实现深度优先遍历的代码:
```c
#define MAX_VERTEX_NUM 100 //最大顶点数
#define INFINITY 65535 //表示无穷大
typedef struct {
int vexs[MAX_VERTEX_NUM]; //顶点表
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
int vexnum, arcnum; //图的当前顶点数和弧数
} MGraph;
int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过
void DFS(MGraph G, int v) {
visited[v] = 1; //标记节点v已被访问
printf("%d ", G.vexs[v]); //访问节点v
for (int i = ; i < G.vexnum; i++) {
if (G.arcs[v][i] != INFINITY && !visited[i]) { //如果节点i是节点v的邻居且未被访问
DFS(G, i); //递归访问节点i
}
}
}
void DFSTraverse(MGraph G) {
for (int i = ; i < G.vexnum; i++) {
visited[i] = ; //初始化visited数组
}
for (int i = ; i < G.vexnum; i++) {
if (!visited[i]) { //如果节点i未被访问
DFS(G, i); //从节点i开始深度优先遍历
}
}
}
```
广度优先遍历:
1. 定义一个队列,将起始节点入队。
2. 当队列不为空时,取出队首节点,访问该节点,并将其未被访问的邻居节点入队。
3. 标记已访问的节点。
4. 重复步骤2和3,直到队列为空。
邻接矩阵实现广度优先遍历的代码:
```c
#define MAX_VERTEX_NUM 100 //最大顶点数
#define INFINITY 65535 //表示无穷大
typedef struct {
int vexs[MAX_VERTEX_NUM]; //顶点表
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
int vexnum, arcnum; //图的当前顶点数和弧数
} MGraph;
int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过
void BFS(MGraph G, int v) {
int queue[MAX_VERTEX_NUM]; //定义队列
int front = , rear = ; //队首和队尾指针
visited[v] = 1; //标记节点v已被访问
printf("%d ", G.vexs[v]); //访问节点v
queue[rear++] = v; //将节点v入队
while (front != rear) { //队列不为空时
int w = queue[front++]; //取出队首节点w
for (int i = ; i < G.vexnum; i++) {
if (G.arcs[w][i] != INFINITY && !visited[i]) { //如果节点i是节点w的邻居且未被访问
visited[i] = 1; //标记节点i已被访问
printf("%d ", G.vexs[i]); //访问节点i
queue[rear++] = i; //将节点i入队
}
}
}
}
void BFSTraverse(MGraph G) {
for (int i = ; i < G.vexnum; i++) {
visited[i] = ; //初始化visited数组
}
for (int i = ; i < G.vexnum; i++) {
if (!visited[i]) { //如果节点i未被访问
BFS(G, i); //从节点i开始广度优先遍历
}
}
}
```
邻接表实现图的深度优先遍历和广度优先遍历:
深度优先遍历:
1. 定义一个栈,将起始节点入栈。
2. 当栈不为空时,取出栈顶节点,访问该节点,并将其未被访问的邻居节点入栈。
3. 标记已访问的节点。
4. 重复步骤2和3,直到栈为空。
邻接表实现深度优先遍历的代码:
```c
#define MAX_VERTEX_NUM 100 //最大顶点数
typedef struct ArcNode { //边表节点
int adjvex; //邻接点在顶点表中的位置
struct ArcNode *nextarc; //指向下一个边表节点
} ArcNode;
typedef struct VNode { //顶点表节点
int data; //顶点数据
ArcNode *firstarc; //指向第一个边表节点
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; //邻接表
int vexnum, arcnum; //图的当前顶点数和弧数
} ALGraph;
int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过
void DFS(ALGraph G, int v) {
visited[v] = 1; //标记节点v已被访问
printf("%d ", G.vertices[v].data); //访问节点v
ArcNode *p = G.vertices[v].firstarc;
while (p) {
if (!visited[p->adjvex]) { //如果节点p->adjvex未被访问
DFS(G, p->adjvex); //递归访问节点p->adjvex
}
p = p->nextarc;
}
}
void DFSTraverse(ALGraph G) {
for (int i = ; i < G.vexnum; i++) {
visited[i] = ; //初始化visited数组
}
for (int i = ; i < G.vexnum; i++) {
if (!visited[i]) { //如果节点i未被访问
DFS(G, i); //从节点i开始深度优先遍历
}
}
}
```
广度优先遍历:
1. 定义一个队列,将起始节点入队。
2. 当队列不为空时,取出队首节点,访问该节点,并将其未被访问的邻居节点入队。
3. 标记已访问的节点。
4. 重复步骤2和3,直到队列为空。
邻接表实现广度优先遍历的代码:
```c
#define MAX_VERTEX_NUM 100 //最大顶点数
typedef struct ArcNode { //边表节点
int adjvex; //邻接点在顶点表中的位置
struct ArcNode *nextarc; //指向下一个边表节点
} ArcNode;
typedef struct VNode { //顶点表节点
int data; //顶点数据
ArcNode *firstarc; //指向第一个边表节点
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; //邻接表
int vexnum, arcnum; //图的当前顶点数和弧数
} ALGraph;
int visited[MAX_VERTEX_NUM]; //标记节点是否被访问过
void BFS(ALGraph G, int v) {
int queue[MAX_VERTEX_NUM]; //定义队列
int front = , rear = ; //队首和队尾指针
visited[v] = 1; //标记节点v已被访问
printf("%d ", G.vertices[v].data); //访问节点v
queue[rear++] = v; //将节点v入队
while (front != rear) { //队列不为空时
int w = queue[front++]; //取出队首节点w
ArcNode *p = G.vertices[w].firstarc;
while (p) {
if (!visited[p->adjvex]) { //如果节点p->adjvex未被访问
visited[p->adjvex] = 1; //标记节点p->adjvex已被访问
printf("%d ", G.vertices[p->adjvex].data); //访问节点p->adjvex
queue[rear++] = p->adjvex; //将节点p->adjvex入队
}
p = p->nextarc;
}
}
}
void BFSTraverse(ALGraph G) {
for (int i = ; i < G.vexnum; i++) {
visited[i] = ; //初始化visited数组
}
for (int i = ; i < G.vexnum; i++) {
if (!visited[i]) { //如果节点i未被访问
BFS(G, i); //从节点i开始广度优先遍历
}
}
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)