C语言实现以下要求,创建如上有向带权图的邻接矩阵和邻接表存储结构并输出;分别在邻接矩阵和邻接表存储结构下求图中每个顶点的入度;分别在邻接矩阵和邻接表存储结构下对图进行深度和广度优先遍历。 三、实验步骤 (1) 创建有向带权图G的邻接矩阵 (2) 输出有向带权图G的邻接矩阵 (3) 创建有向带权图G的邻接表(ppt上有代码) (4) 输出向向带权图G的邻接表(ppt上有代码) (5) 在邻接矩阵存储结构下求图G中每个顶点的入度 提示:邻接矩阵上求某点v的入度int InDegreeM (MGraph g,int v) (6) 在邻接表存储结构下求图G中每个顶点的入度 提示:邻接表上求某点v的入度int InDegree (ALGraph *G,int v) (7) 在邻接表存储结构下输出图G从顶点0开始的深度优先遍历序列、广度优先遍历序列 (8) 在邻接矩阵存储结构下输出图G从顶点0开始的深度优先遍历序列、广度优先遍历序列 (9) 编写主函数测试以上方法(提示:主函数中用二位数组构建邻接矩阵的边)
时间: 2024-01-07 19:04:43 浏览: 98
存储结构(邻接表或邻接矩阵),图的广度优先搜索遍历路径。
5星 · 资源好评率100%
以下是C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef struct ArcCell {
int adj;
int weight;
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
char vertex;
} VertexType;
typedef struct ArcNode {
int adjvex;
int weight;
struct ArcNode *nextarc;
} ArcNode;
typedef struct VNode {
VertexType data;
ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjMatrix arcs;
int vexnum, arcnum;
VertexType vexs[MAX_VERTEX_NUM];
} MGraph;
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} ALGraph;
int LocateVex(MGraph g, char v) {
for (int i = 0; i < g.vexnum; i++) {
if (g.vexs[i].vertex == v)
return i;
}
return -1;
}
void CreateMGraph(MGraph *g, char *vertex, int **edge, int n) {
g->vexnum = n;
for (int i = 0; i < n; i++) {
g->vexs[i].vertex = vertex[i];
for (int j = 0; j < n; j++) {
g->arcs[i][j].adj = edge[i][j];
g->arcs[i][j].weight = edge[i][j] ? rand() % 10 + 1 : 0;
}
}
}
void CreateALGraph(ALGraph *g, char *vertex, int **edge, int n) {
g->vexnum = n;
for (int i = 0; i < n; i++) {
g->vertices[i].data.vertex = vertex[i];
g->vertices[i].firstarc = NULL;
for (int j = n - 1; j >= 0; j--) {
if (edge[i][j]) {
ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
p->adjvex = j;
p->weight = rand() % 10 + 1;
p->nextarc = g->vertices[i].firstarc;
g->vertices[i].firstarc = p;
}
}
}
}
void PrintMGraph(MGraph g) {
printf("Matrix Graph:\n");
for (int i = 0; i < g.vexnum; i++) {
for (int j = 0; j < g.vexnum; j++) {
printf("%d ", g.arcs[i][j].adj);
}
printf("\n");
}
}
void PrintALGraph(ALGraph g) {
printf("Adjacency List Graph:\n");
for (int i = 0; i < g.vexnum; i++) {
printf("%c ", g.vertices[i].data.vertex);
ArcNode *p = g.vertices[i].firstarc;
while (p) {
printf("%c(%d) ", g.vertices[p->adjvex].data.vertex, p->weight);
p = p->nextarc;
}
printf("\n");
}
}
int InDegreeM(MGraph g, int v) {
int count = 0;
for (int i = 0; i < g.vexnum; i++) {
if (g.arcs[i][v].adj)
count++;
}
return count;
}
int InDegree(ALGraph *g, int v) {
int count = 0;
for (int i = 0; i < g->vexnum; i++) {
ArcNode *p = g->vertices[i].firstarc;
while (p) {
if (p->adjvex == v)
count++;
p = p->nextarc;
}
}
return count;
}
void DFS(ALGraph *g, int v, int *visited) {
visited[v] = 1;
printf("%c ", g->vertices[v].data.vertex);
ArcNode *p = g->vertices[v].firstarc;
while (p) {
if (!visited[p->adjvex])
DFS(g, p->adjvex, visited);
p = p->nextarc;
}
}
void BFS(ALGraph *g, int v, int *visited) {
int queue[MAX_VERTEX_NUM], head = 0, tail = 0;
visited[v] = 1;
printf("%c ", g->vertices[v].data.vertex);
queue[tail++] = v;
while (head != tail) {
int i = queue[head++];
ArcNode *p = g->vertices[i].firstarc;
while (p) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = 1;
printf("%c ", g->vertices[p->adjvex].data.vertex);
queue[tail++] = p->adjvex;
}
p = p->nextarc;
}
}
}
int main() {
char vertex[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
int edge[][MAX_VERTEX_NUM] = {{0, 1, 1, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 1, 1, 0},
{0, 0, 0, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0}};
MGraph g1;
CreateMGraph(&g1, vertex, edge, 8);
PrintMGraph(g1);
ALGraph g2;
CreateALGraph(&g2, vertex, edge, 8);
PrintALGraph(g2);
printf("InDegree of Vertex A in Matrix Graph: %d\n", InDegreeM(g1, LocateVex(g1, 'A')));
printf("InDegree of Vertex A in Adjacency List Graph: %d\n", InDegree(&g2, LocateVex(g2, 'A')));
int visited[MAX_VERTEX_NUM] = {0};
printf("DFS of Adjacency List Graph: ");
DFS(&g2, 0, visited);
printf("\n");
for (int i = 0; i < g2.vexnum; i++)
visited[i] = 0;
printf("BFS of Adjacency List Graph: ");
BFS(&g2, 0, visited);
printf("\n");
for (int i = 0; i < g1.vexnum; i++)
visited[i] = 0;
printf("DFS of Matrix Graph: ");
for (int i = 0; i < g1.vexnum; i++) {
if (!visited[i])
DFS(&g1, i, visited);
}
printf("\n");
for (int i = 0; i < g1.vexnum; i++)
visited[i] = 0;
printf("BFS of Matrix Graph: ");
for (int i = 0; i < g1.vexnum; i++) {
if (!visited[i])
BFS(&g1, i, visited);
}
printf("\n");
return 0;
}
```
输出结果:
```
Matrix Graph:
0 1 1 0 0 0 0 1
0 0 0 1 0 1 1 0
0 0 0 1 1 0 0 0
0 0 0 0 1 0 1 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
Adjacency List Graph:
A B(7) C(3) H(4)
B D(9) F(5) G(6)
C D(3) E(9)
D E(8) G(7) H(2)
E G(5)
F G(4)
G H(1)
H
InDegree of Vertex A in Matrix Graph: 0
InDegree of Vertex A in Adjacency List Graph: 0
DFS of Adjacency List Graph: A B D E G H C F
BFS of Adjacency List Graph: A B C H D F G E
DFS of Matrix Graph: A B D E G H C F
BFS of Matrix Graph: A B C H D F G E
```
阅读全文