【数据结构_浙江大学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;
}

提交结果

【数据结构_浙江大学MOOC】第六七八讲 图

哈利·波特的考试

题目

哈利·波特要考试了,他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是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 算法。将图用邻接矩阵表示后,对每一个顶点扫描它到其它顶点的最大值, 记录下来,再在这些最大值里找一个最小值,即我们想要得到的那个顶点。在本题中,也就是哈利应该带该点所对应的动物去。这样,我们就成功的帮哈利完成了考试该带什么去的难题!

【数据结构_浙江大学MOOC】第六七八讲 图

程序框架如下:

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;
}

提交结果

【数据结构_浙江大学MOOC】第六七八讲 图

旅游规划

题目

有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。

输入格式:
输入说明:输入数据的第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 算法解决。这道题里面城市为结点,公路为边。一个复杂的问题是每一条边的权重,在这道题里有距离收费两种权重,首先要找距离意义上最短路径,当最短路不止一条的时候,就需要找收费最短的路。

根据输入样例,有下面的图:

【数据结构_浙江大学MOOC】第六七八讲 图

绿色表示权重距离,紫色表示权重收费。我们用基于 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】第六七八讲 图


关于浙江大学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)


最后给出一张数据结构和算法的思维导图:

【数据结构_浙江大学MOOC】第六七八讲 图

剩下的内容将在之后的算法学习中进行。


参考链接:
06-图1 列出连通集 (25分)
07-图4 哈利·波特的考试(25 分)
旅游规划

$$$$
不足之处,欢迎指正。

相关推荐

wangjunyi / 0评论 2012-06-27