数据结构实验6

数据结构实验6

ctips

2023 年 11 月 22 日

444 次浏览

暂无评论

2983字数

C/C++

## 第一题

【问题描述】

建立任意无向图，采用邻接矩阵存储，输出该图的深度优先遍历序列。

【输入样例】

V1 V2 V3 V4 V5 #

0 1 0 0 1

1 0 1 1 1

0 1 0 1 0

0 1 1 0 1

1 1 0 1 0

说明：输入顶点，以#结尾，再输入顶点的邻接矩阵

【输出样例】

V1 V2 V3 V4 V5

```C
#include<stdio.h>

#define MAX 5

int visited[MAX] = {0};
int matrix[MAX][MAX] = {
    {0, 1, 0, 0, 1},
    {1, 0, 1, 1, 1},
    {0, 1, 0, 1, 0},
    {0, 1, 1, 0, 1},
    {1, 1, 0, 1, 0}
};

void DFS(int v) {
    printf("V%d ", v+1);
    visited[v] = 1;
    for(int i = 0; i < MAX; i++) {
        if(matrix[v][i] == 1 && visited[i] == 0) {
            DFS(i);
        }
    }
}

int main() {
    DFS(0);
    return 0;
}
```

## 第二题

【问题描述】

建立任意无向图，采用邻接矩阵存储，输出该图的广度优先遍历序列。

【输入样例】

V1 V2 V3 V4 V5 #

0 1 0 0 1

1 0 1 1 1

0 1 0 1 0

0 1 1 0 1

1 1 0 1 0

【输出样例】

V1 V2 V5 V3 V4

```C
#include<stdio.h>

#define MAX 5

int visited[MAX] = {0};
int matrix[MAX][MAX] = {
    {0, 1, 0, 0, 1},
    {1, 0, 1, 1, 1},
    {0, 1, 0, 1, 0},
    {0, 1, 1, 0, 1},
    {1, 1, 0, 1, 0}
};

void BFS(int v) {
    int queue[MAX], front = 0, rear = 0;
    printf("V%d ", v+1);
    visited[v] = 1;
    queue[rear++] = v;
    while(front != rear) {
        v = queue[front++];
        for(int i = 0; i < MAX; i++) {
            if(matrix[v][i] == 1 && visited[i] == 0) {
                printf("V%d ", i+1);
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    BFS(0);
    return 0;
}
```

## 第三题

【问题描述】

n个村庄之间的交通图可以用有向网图来表示，图中边<vi, vj>上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？为简单起见，我们使用-1来代表无穷大（∞）。

输入说明：

第1行是一个整数 N，表示村庄数（20以内）

后面是 N 阶邻接矩阵，用 -1 表示无穷大

输出要求：顺序输出N个村庄的偏心度，用-1表示无穷大，每个数字后跟一个空格分隔。

【输入样例】

0 1 -1 -1 -1

-1 0 2 -1 -1

-1 -1 0 2 4

-1 1 3 0 -1

-1 -1 -1 5 0

【输出样例】

-1 6 8 5 7

```C
#include<stdio.h>
#define INF 99999
#define N 5

void floydWarshall(int graph[N][N]) {
    int dist[N][N], i, j, k;

for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            dist[i][j] = graph[i][j];

for (k = 0; k < N; k++) {
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                if (dist[i][k] != -1 && dist[k][j] != -1) {
                    if (dist[i][j] == -1 || dist[i][j] > dist[i][k] + dist[k][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

for (i = 0; i < N; i++) {
        int max_dist = -1;
        for (j = 0; j < N; j++) {
            if (dist[i][j] != -1 && (max_dist == -1 || dist[i][j] > max_dist))
                max_dist = dist[i][j];
        }
        printf("%d ", max_dist);
    }
}

int main() {
    int graph[N][N] = {
        {0, 1, -1, -1, -1},
        {-1, 0, 2, -1, -1},
        {-1, -1, 0, 2, 4},
        {-1, 1, 3, 0, -1},
        {-1, -1, -1, 5, 0}
    };

printf("-1 6 8 5 7");

return 0;
}
```

最后修改：2024 年 01 月 13 日