【数据结构_浙江大学MOOC】第六七八讲 图
鱼天翱 2019-06-28
列出连通集
题目
给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。
输入格式:
输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。
输出格式:
按照 ${v_1, v_2, ···, v_k}$ 的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。
输入样例:
8 6 0 7 0 1 2 0 4 1 2 4 3 5
输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }实现代码
#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;
#define MAX 10
int a[MAX][MAX], dfs_visited[MAX], bfs_visited[MAX], N, E; //dfs_visited数组表示dfs
queue<int> q;
void dfs(int c){
dfs_visited[c] = 1; //1表示访问过了
printf(" %d", c);
for(int i = 0; i < N; i++)
if(a[c][i] && !dfs_visited[i]) //利用二维数组的一行就是该节点的邻接点，如果那个邻接点还没没访问过则递归访问
dfs(i);
}
void bfs(int c){
bfs_visited[c] = 1; //1表示访问过了
q.push(c);
printf(" %d", c);
while(!q.empty()){ //如果队列不空则每次从队列中取出一个节点找出该节点的第一层bfs节点，并加入队列中
int temp = q.front();
q.pop();
for(int i = 0; i < N; i++){ //找出第一层bfs的节点,依次输出并加入队列，跟树的层次遍历很像
if(a[temp][i] && !bfs_visited[i]){
printf(" %d", i);
bfs_visited[i] = 1;
q.push(i);
}
}
}
}
int main(){
int temp1, temp2;
scanf("%d%d", &N, &E);
for(int i = 0; i < E; i++){
scanf("%d%d", &temp1, &temp2);
a[temp1][temp2] = 1; //因为是无向图所有邻接矩阵是关于主对角线对称的
a[temp2][temp1] = 1;
}
for(int i = 0; i < N; i++){
if(!dfs_visited[i]){
putchar('{');
dfs(i);
printf(" }\n");
}
}
for(int i = 0; i < N; i++){
if(!bfs_visited[i]){
putchar('{');
bfs(i);
printf(" }\n");
}
}
return 0;
}提交结果
哈利·波特的考试
题目
哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。
现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。
输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。
输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。
输入样例:
6 11 3 4 70 1 2 1 5 4 50 2 6 50 5 6 60 1 3 70 4 6 60 3 6 80 5 1 100 2 4 60 5 2 80
输出样例:
4 70
解读题目
本题可以视为一个无向带权图，题目里以字符长度来衡量难度，因此带鼠去，无论是变猫还是变鱼，都只需要4个字符。在输入样例中，第一行的6代表动物个数，即图里面顶点的个数，11表示边的个数，接下来的每一行给出两个顶点和它们之间的权重，这些数据对应一张无向的网图。
本题的目的在于找出任意两个顶点之间的最短路径，用 FLoyd 算法。将图用邻接矩阵表示后，对每一个顶点扫描它到其它顶点的最大值， 记录下来，再在这些最大值里找一个最小值，即我们想要得到的那个顶点。在本题中，也就是哈利应该带该点所对应的动物去。这样，我们就成功的帮哈利完成了考试该带什么去的难题！
程序框架如下：
int main()
{
Graph G = BuildGraph(); //读入图
FindAnimal(G); //分析图
return 0;
}实现代码
#include<iostream>
#include<fstream>
using namespace std;
//ifstream InFile("C:\\Users\\DELL\\Desktop\\in.txt",ios::in);
#define MaxVertexNum 200 //最大顶点数设为100
#define INFINITY1 65535 //∞设为双字节无符号整数的最大值65535
typedef int Vertex; //用顶点下标表示顶点，为整形
typedef int WeightType; //边的权值设为整形
typedef char DataType; //顶点储存的数据类型设为字符型
//图结点的定义
typedef struct GNode* PtrToGNode;
struct GNode{
int Nv; //顶点数
int Ne; //边数
WeightType G[MaxVertexNum][MaxVertexNum]; //邻接矩阵
DataType Data[MaxVertexNum]; //存顶点的数据
//注意：若顶点无数据，此时Data[]可以不出现
};
typedef PtrToGNode MGraph;
//边的定义
typedef struct ENode* PtrToENode;
struct ENode{
Vertex V1,V2; //无向边（v1,v2）
WeightType Weight; //权重
};
typedef PtrToENode Edge;
MGraph CreateGraph(int VertexNum)
{
MGraph Graph = new GNode;
Graph->Nv = VertexNum;
Graph->Ne = 0;
for(int i=0;i<Graph->Nv+2 ;++i){
for(int j=0;j<Graph->Nv+2 ;++j){
Graph->G[i][j] = INFINITY1;
}
}
return Graph;
}
void InsertEdge(MGraph Graph,Edge E)
{
Graph->G[E->V1][E->V2] = E->Weight;
Graph->G[E->V2][E->V1] = E->Weight;
}
MGraph BulidGraph()
{
Vertex N,M;
cin >> N>>M;
Edge E=new ENode;
MGraph Graph = CreateGraph(N);
if(Graph->Nv >0){
for(int i=0;i<M;++i){
cin >> E->V1 >> E->V2 >> E->Weight;
InsertEdge(Graph, E);
}
}
return Graph;
}
//Floyd
bool Floyd(MGraph Graph,WeightType D[][MaxVertexNum])
{
for(int i=0;i<Graph->Nv +2;++i){
for(int j=0;j<Graph->Nv +2;++j){
D[i][j] = Graph->G[i][j];
}
}
for(int k=1;k<=Graph->Nv ;++k){
for(int i=0;i<=Graph->Nv ;++i){
for(int j=0;j<=Graph->Nv ;++j){
if(i!=j&&D[i][k]+D[k][j]<D[i][j]){
D[i][j] = D[i][k] + D[k][j];
if (i == j&&D[i][j]<0) {
return false;
}
}
}
}
}
return true;
}
void FindAnimal(MGraph Graph)
{
WeightType D[MaxVertexNum][MaxVertexNum];
WeightType Max[MaxVertexNum];
Floyd(Graph, D);
for(int i=1;i<=Graph->Nv ;++i){
int m = -1;
for(int j=1;j<=Graph->Nv ;++j){
if(i!=j&&m<D[i][j]){
m = D[i][j];
}
if(i!=j&&D[i][j]==INFINITY1){
cout << 0 << endl;
return;
}
}
Max[i] = m;
}
int ret = 1;
for(int i = 2; i <= Graph->Nv; ++i){
//cout << Max[i] << endl;
if(Max[ret]>Max[i]){
ret = i;
}
}
cout << ret << " " << Max[ret] << endl;
}
int main()
{
MGraph Graph = BulidGraph();
FindAnimal(Graph);
delete Graph;
//InFile.close();
system("pause");
return 0;
}提交结果
旅游规划
题目
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20
输出样例:
3 40
题目解读
这是一个图论里单源最短路径问题，我们用 Dijkstra 算法解决。这道题里面城市为结点，公路为边。一个复杂的问题是每一条边的权重，在这道题里有距离和收费两种权重，首先要找距离意义上最短路径，当最短路不止一条的时候，就需要找收费最短的路。
根据输入样例，有下面的图：
绿色表示权重距离，紫色表示权重收费。我们用基于 Dijkstra 算法的方法来解决，首先以距离为权重应用 Dijkstra 算法，我们知道到每收录一个结点的时候要判断其它结点有没有被影响，会不会得到一个更短的距离，如果更短的话我们要更新这个距离，如果是等长的话，在原本的 Dijkstra 算法中就什么都不做了，但在本题中，当距离相等的时候，我们还需要按照收费来做一个更新。
实现代码
#include<iostream>
using namespace std;
#define MaxNum 10000
typedef int ElemType;
int main()
{
int N,M;
ElemType S,D;
cin>>N>>M>>S>>D;
//用邻接矩阵存储图
int **len = new int*[N]; //储存公路长度
int **cost = new int*[N]; //储存费用
for(int i=0; i<N; i++)
{
len[i] = new int[N];
cost[i] = new int[N];
}
//初始化
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
len[i][j] = MaxNum;
cost[i][j] = MaxNum;
}
}
//构建邻接矩阵，处理输入数据
for(int i=0;i<M;i++)
{
ElemType c1,c2;
int l,c;
cin>>c1>>c2>>l>>c;
len[c1][c2] = l;
len[c2][c1] = l;
cost[c1][c2] = c;
cost[c2][c1] = c;
}
//Dijastra算法开始
int *dist = new int[N]; //记录当前路径长度
int *acost = new int[N]; //记录当前花费
//初始化
for(int i=0;i<N;i++)
{
dist[i] = MaxNum;
acost[i] = MaxNum;
}
dist[S] = 0;
acost[S] = 0;
//进行算法
for(int k=0;k<2;k++)
{
for(int v=0;v<N;v++)
{
for(int w=0;w<N;w++)
{
if(dist[v] != MaxNum)
{
if(dist[v]+len[v][w] < dist[w])
dist[w] = dist[v] + len[v][w];
else if(dist[v] + len[v][w] == dist[w] && acost[v] != MaxNum && acost[v]+cost[v][w] <acost[w])
acost[w] = acost[v] + cost[v][w];
}
}
}
}
cout<<dist[D] << " " <<acost[D] <<endl;
return 0;
}提交结果
关于浙江大学MOOC数据结构课程的习题记录就到这里了，主要记录了线性表、树、图的必做编程题内容，附上课程大纲：
第一讲 基本概念（1:15:26）[陈越]1.1 什么是数据结构（4节共32:43）
1.2 什么是算法（3节共22:41）
1.3 应用实例：最大子列和问题（3节共20:02）
第二讲 线性结构（2:19:00）[何钦铭]
2.1 线性表及其实现(6小节共45:04)
2.2 堆栈(4小节共39:51)
2.3 队列(2小节共15:45)
2.4 应用实例：多项式加法运算(1小节10:37)
小白专场：多项式乘法与加法运算- C实现（3小节共27:43）
第三讲 树(上) （1:50:08）[何钦铭]
3.1 树与树的表示(5小节共38:54)
3.2 二叉树及存储结构(2小节共16:43)
3.3 二叉树的遍历(4小节共37:02)
小白专场：树的同构 - C语言实现（2小节共17:29）
第四讲 树（中）（1:06:31）[何钦铭]
4.1 二叉搜索树(3小节共20:57)
4.2 平衡二叉树(2小节共22:53)
小白专场：是否同一棵二叉搜索树- C实现（3小节共22:41）
线性结构之习题选讲[陈越]：Reversing Linked List（3小节共13:08）
第五讲 树（下）（1:53:28）[何钦铭]
5.1 堆（4小节共30:05）
5.2 哈夫曼树与哈夫曼编码（3小节共19:52）
5.3 集合及运算（2小节共12:57）
小白专场：堆中的路径 - C语言实现（1小节共7:51）
小白专场[陈越]：File Transfer - C语言实现（4小节共42:43）
第六讲 图（上）（1:29:32）[陈越]
6.1 什么是图（3小节共24:02）
6.2 图的遍历（4小节共22:22）
6.3 应用实例：拯救007（1小节共14:40）
6.4 应用实例：六度空间（1小节共8:06）
小白专场：如何建立图- C语言实现（6小节共20:22）
第七讲 图（中）（2:11:35）[陈越]
树之习题选讲-Tree Traversals Again（2小节共12:16）
树之习题选讲-Complete Binary Search Tree（3小节共25:47）
树之习题选讲- Huffman Codes（3小节共18:11）
7.1 最短路径问题（6小节共56:38）
小白专场：哈利•波特的考试- C语言实现（4小节共18:43）
第八讲 图（下）（57:02）[陈越]
8.1 最小生成树问题（2小节共20:16）
8.2 拓扑排序（2小节共27:57）
图之习题选讲-旅游规划（2小节共8:49）
第九讲 排序（上）（1:11:44）[陈越]
9.1 简单排序（冒泡、插入）（4小节共23:26）
9.2 希尔排序（1小节共9:29）
9.3 堆排序（2小节共10:27）
9.4 归并排序（3小节共28:22）
第十讲 排序（下）（54:20）[陈越]
10.1 快速排序（4小节共25:25）
10.2 表排序（2小节共12:41）
10.3 基数排序（3小节共12:13）
10.4 排序算法的比较（1小节共4:01）
第十一讲 散列查找（1:43:39）[何钦铭]
11.1 散列表(2小节共13:43)
11.2 散列函数的构造方法(2小节共13:05)
11.3 冲突处理方法(6小节共36:26)
11.4 散列表的性能分析(1小节10:26)
11.5 应用实例:词频统计(1小节6:01)
小白专场[陈越]：电话聊天狂人- C语言实现（4小节共23:58）
第十二讲 综合习题选讲（30:12） [陈越]
习题选讲-Insert or Merge（2小节共11:51）
习题选讲-Sort with Swap(0,*)（2小节共11:06）
习题选讲-Hashing - Hard Version（1小节共7:15）
最后给出一张数据结构和算法的思维导图：
剩下的内容将在之后的算法学习中进行。
参考链接：
06-图1 列出连通集 (25分)
07-图4 哈利·波特的考试（25 分）
旅游规划
$$$$
不足之处，欢迎指正。
