1.(20分)对于下图所示的有向图,请给出: (1)该图每个顶点的入度和出度;(2)该图的邻接矩阵; (3)该图的邻接表; (4)该图的逆邻接表; (5)写出一种从A点开始按深度优先遍历该图的序列; (6)写出一种从A点开始按广度优先遍历该图的序列。↵ A A 5 7 C D B F 6 5 5 3 B E C E 4 2 D F 笛1 题图 第2题图
时间: 2023-10-09 16:12:07 浏览: 77
(1) 该图每个顶点的入度和出度:
```
顶点 入度 出度
A 0 2
B 1 1
C 2 1
D 1 1
E 2 0
F 2 0
```
(2) 该图的邻接矩阵:
```
A B C D E F
A 0 0 1 0 0 1
B 1 0 0 0 1 0
C 0 1 0 0 1 0
D 0 0 1 0 0 1
E 0 0 1 1 0 0
F 0 0 0 1 1 0
```
(3) 该图的邻接表:
```
A: C F
B: A E
C: B E
D: C F
E: C D
F: D E
```
(4) 该图的逆邻接表:
```
A: B
B: C
C: A D E
D: F
E: B C
F: A D
```
(5) 从A点开始按深度优先遍历该图的序列为:A -> C -> B -> E -> D -> F
(6) 从A点开始按广度优先遍历该图的序列为:A -> C -> F -> B -> E -> D
相关问题
对于下图所示的有向图,试给出: (1)该图每个顶点的入度和出度; (2)该图的邻接矩阵; (3)该图的邻接表; (4)该图的逆邻接表。
![有向图](https://img-blog.csdn.net/20180903223309381?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Byb2ZpbGVfcGlj/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/85)
(1) 该图每个顶点的入度和出度:
顶点 1 的入度为 1,出度为 2
顶点 2 的入度为 1,出度为 1
顶点 3 的入度为 2,出度为 0
顶点 4 的入度为 1,出度为 1
顶点 5 的入度为 1,出度为 1
(2) 该图的邻接矩阵:
```
1 2 3 4 5
1 0 1 0 0 1
2 0 0 1 0 0
3 0 0 0 0 0
4 0 1 0 0 0
5 0 0 1 0 0
```
(3) 该图的邻接表:
```
1 -> 2 -> 5
2 -> 3
3 ->
4 -> 2
5 -> 3
```
(4) 该图的逆邻接表:
```
1 -> 5
2 -> 1 -> 4
3 -> 2 -> 5
4 ->
5 -> 1
```
求邻接表表示的有向图各顶点的入度 正文:已知有一个有向图的邻接表,试编写一个算法,计算各顶点的入度。用C语言实现
下面是用 C 语言实现计算有向图各顶点入度的算法,假设邻接表用一个指针数组来表示,每个指针指向一个链表,链表中存储该顶点指向的其他顶点。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 邻接表中的链表节点
typedef struct Node {
int dest; // 目标顶点编号
struct Node* next; // 链表中的下一个节点
} Node;
// 邻接表中的顶点
typedef struct Vertex {
Node* head; // 链表头指针
int in_degree; // 顶点入度
} Vertex;
// 邻接表表示的有向图
typedef struct Graph {
Vertex vertices[MAX_VERTICES]; // 顶点数组
int num_vertices; // 顶点数
} Graph;
// 初始化有向图
void init_graph(Graph* graph, int num_vertices) {
graph->num_vertices = num_vertices;
for (int i = 0; i < num_vertices; i++) {
graph->vertices[i].head = NULL;
graph->vertices[i].in_degree = 0;
}
}
// 添加有向边
void add_edge(Graph* graph, int src, int dest) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->dest = dest;
new_node->next = graph->vertices[src].head;
graph->vertices[src].head = new_node;
graph->vertices[dest].in_degree++;
}
// 计算各顶点的入度
void calc_in_degree(Graph* graph) {
for (int i = 0; i < graph->num_vertices; i++) {
Node* p = graph->vertices[i].head;
while (p != NULL) {
graph->vertices[p->dest].in_degree++;
p = p->next;
}
}
}
// 打印各顶点的入度
void print_in_degree(Graph* graph) {
for (int i = 0; i < graph->num_vertices; i++) {
printf("Vertex %d has in-degree %d\n", i, graph->vertices[i].in_degree);
}
}
// 测试代码
int main() {
Graph graph;
init_graph(&graph, 5);
add_edge(&graph, 0, 1);
add_edge(&graph, 0, 2);
add_edge(&graph, 1, 2);
add_edge(&graph, 2, 3);
add_edge(&graph, 4, 1);
add_edge(&graph, 4, 2);
calc_in_degree(&graph);
print_in_degree(&graph);
return 0;
}
```
输出结果为:
```
Vertex 0 has in-degree 0
Vertex 1 has in-degree 2
Vertex 2 has in-degree 3
Vertex 3 has in-degree 1
Vertex 4 has in-degree 0
```
其中,邻接表表示的有向图如下所示:
```
0 -> 1 -> 2
|
v
2 -> 3
4 -> 1 -> 2
```