无向图采用邻接矩阵进行存储,完成以下操作:(1)建立无向图的邻接矩阵存储(2)输出邻接矩阵(3)基于邻接矩阵的深度优先遍历(4)基于邻接矩阵的广度优先遍历
时间: 2024-05-25 13:08:51 浏览: 173
对于无向图采用邻接矩阵进行存储,我们可以按照如下步骤进行操作:
(1)建立无向图的邻接矩阵存储
邻接矩阵是一个二维数组,矩阵的行和列分别表示图中的顶点,数组中的值表示两个顶点之间是否有边相连。如果顶点i和顶点j之间有边相连,则邻接矩阵中第i行第j列和第j行第i列的元素都为1,否则为0。
具体实现可以参考以下代码:
```c
#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef struct {
char vertex[MAX_VERTEX_NUM]; // 顶点数组
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点数
int edge_num; // 边数
} Graph;
void createGraph(Graph *G) {
int i, j;
printf("请输入顶点数和边数:");
scanf("%d %d", &(G->vertex_num), &(G->edge_num));
getchar(); // 吸收回车符
printf("请输入顶点信息:");
for (i = 0; i < G->vertex_num; i++) {
scanf("%c", &(G->vertex[i]));
getchar(); // 吸收回车符
}
for (i = 0; i < G->vertex_num; i++) {
for (j = 0; j < G->vertex_num; j++) {
G->edge[i][j] = 0; // 初始化邻接矩阵
}
}
printf("请输入边信息:\n");
for (i = 0; i < G->edge_num; i++) {
int v1, v2;
printf("请输入第%d条边(v1, v2)的顶点序号:", i+1);
scanf("%d %d", &v1, &v2);
G->edge[v1][v2] = 1;
G->edge[v2][v1] = 1; // 对称矩阵赋值
}
}
```
(2)输出邻接矩阵
输出邻接矩阵只需要遍历二维数组即可。
```c
void printGraph(Graph G) {
int i, j;
printf("邻接矩阵为:\n");
for (i = 0; i < G.vertex_num; i++) {
for (j = 0; j < G.vertex_num; j++) {
printf("%d ", G.edge[i][j]);
}
printf("\n");
}
}
```
(3)基于邻接矩阵的深度优先遍历
深度优先遍历需要借助栈来实现,遍历过程中需要标记已经访问过的节点。
```c
void DFS(Graph G, int v, int *visited) {
printf("%c ", G.vertex[v]);
visited[v] = 1;
int i;
for (i = 0; i < G.vertex_num; i++) {
if (G.edge[v][i] == 1 && visited[i] == 0) {
DFS(G, i, visited);
}
}
}
void DFSTraverse(Graph G) {
int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有节点未访问
int i;
printf("深度优先遍历结果为:");
for (i = 0; i < G.vertex_num; i++) {
if (visited[i] == 0) {
DFS(G, i, visited);
}
}
}
```
(4)基于邻接矩阵的广度优先遍历
广度优先遍历需要借助队列来实现,同样需要标记已经访问过的节点。
```c
void BFS(Graph G, int v, int *visited) {
Queue Q;
initQueue(&Q); // 初始化队列
printf("%c ", G.vertex[v]);
visited[v] = 1;
enQueue(&Q, v); // 入队
while (!isQueueEmpty(Q)) { // 队列不为空时循环
int u = deQueue(&Q); // 出队
int i;
for (i = 0; i < G.vertex_num; i++) {
if (G.edge[u][i] == 1 && visited[i] == 0) {
printf("%c ", G.vertex[i]);
visited[i] = 1;
enQueue(&Q, i); // 入队
}
}
}
}
void BFSTraverse(Graph G) {
int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有节点未访问
int i;
printf("广度优先遍历结果为:");
for (i = 0; i < G.vertex_num; i++) {
if (visited[i] == 0) {
BFS(G, i, visited);
}
}
}
```
阅读全文