数据结构 图连通与最小生成树(下)

简介: 数据结构 图连通与最小生成树(下)

3. 图的应用之——图的连通


题目描述


给定一个图的邻接矩阵,请判断该图是否是连通图。连通图:任意两个顶点之间都有路径。


–程序要求–

若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件,不看代码,作0分处理

不允许使用第三方对象或函数实现本题的要求


输入


第1行输入一个整数k,表示有k个测试数据


第2行输入一个整数n,表示有n个结点


从第3行起到第n+2行输入一个邻接矩阵,其中Matrix[i,j]=1表示第i,j个结点之间有边,否则不存在边。


接下来是第2到第k个测试数据的结点数和邻接矩阵


输出


输出Yes or No表示图是否是强连通图


输入样例


2

4

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

7

0 1 0 0 0 0 0

0 0 1 1 0 0 0

1 0 0 0 0 0 0

1 0 1 0 0 0 0

0 0 0 0 0 1 1

0 1 0 0 0 0 0

0 0 0 1 0 1 0


输出样例


Yes

No


参考代码

#include<iostream>
using namespace std;
const int MaxLen = 20;
class Map
{
private:
    bool Visit[MaxLen];
    int Matrix[MaxLen][MaxLen];
    int Vexnum;
    void DFS(int v)
    {
        int w, i, k;
        Visit[v] = true;
        count1++;
        //cout<<v<<" ";
        //寻找邻接点
        int *AdjVex = new int[Vexnum];
        for (i = 0; i < Vexnum; i++)
            AdjVex[i] = -1;
        k = 0;
        for (i = 0; i < MaxLen; i++)
            if (Matrix[v][i] == 1)
                AdjVex[k++] = i;
        i = 0;
        for (w = AdjVex[i++]; w >= 0; w = AdjVex[i++])
        {
            if (Visit[w] == false)
                DFS(w);
        }
        delete[]AdjVex;
    }
public:
    int count1;
    void SetMatrix(int vnum, int mx[MaxLen][MaxLen])
    {
        int i, j;
        Vexnum = vnum;
        for (i = 0; i < MaxLen; i++)
            for (j = 0; j < MaxLen; j++)
                Matrix[i][j] = 0;
        for (i = 0; i < Vexnum; i++)
            for (j = 0; j < Vexnum; j++)
                Matrix[i][j] = mx[i][j];
    }
    void DFSTraverse()
    {
        int v, i;
        for (i = 0; i < Vexnum; i++)
            Visit[i] = false;
        for (v = 0; v < Vexnum; v++)
            if (!Visit[v])
                DFS(v);
        cout << endl;
    }
    int lt()
    {
        int i, j;
        for (i = 0; i < Vexnum; i++)
        {
            for (j = 0; j < Vexnum; j++)
                Visit[j] = false;
            count1 = 0;
            DFS(i);
            if (count1 != Vexnum)
                return 0;
        }
        return 1;
    }
};
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, i, j;
        cin >> n;
        int a[MaxLen][MaxLen];
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                cin >> a[i][j];
        Map map;
        map.SetMatrix(n, a);
        if (map.lt())
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}


4. 广度优先搜索-STL对象版


题目描述


给出一个图的邻接矩阵,对图进行深度优先搜索,从顶点0开始


注意:图n个顶点编号从0到n-1


输入


第一行输入t,表示有t个测试实例


第二行输入n,表示第1个图有n个结点


第三行起,每行输入邻接矩阵的一行,以此类推输入n行


第i个结点与其他结点如果相连则为1,无连接则为0,数据之间用空格隔开


以此类推输入下一个示例


输出


每行输出一个图的广度优先搜索结果,结点编号之间用空格隔开


输入样例


2

4

0 0 1 1

0 0 1 1

1 1 0 1

1 1 1 0

5

0 0 0 1 1

0 0 1 0 0

0 1 0 1 1

1 0 1 0 0

1 0 1 0 0


输出样例


0 2 3 1

0 3 4 2 1


参考代码

#include<iostream>
#include<queue>
using namespace std;
const int MaxLen = 20;
class Map
{
private:
  bool visited[MaxLen];
  int Matrix[MaxLen][MaxLen];
  int vexnum;
  void BFS(int v);
public:
  void SetMatrix(int vnum, int mx[20][20]);
  void BFSTraverse();
};
void Map::SetMatrix(int vnum, int mx[20][20])
{
  int i, j;
  vexnum = vnum;
  for (i = 0;i < vexnum;i++)
    for (j = 0;j < MaxLen;j++)
      Matrix[i][j] = 0;
  for (i = 0;i < vexnum;i++)
    for (j = 0;j < vexnum;j++)
      Matrix[i][j] = mx[i][j];
}
void Map::BFSTraverse()
{
  /*int v;
  int i;
  for (i = 0;i < vexnum;i++)
  {
    visited[i] = false;
  }
  for (v = 0;v < vexnum;v++)
  {
    if (visited[v] == false)DFS(v);
  }
  cout << endl;*/
  BFS(0);
}
void Map::BFS(int v)
{
  int w, u;
  int i, k;
  int* AdjVex = new int[vexnum];
  for (i = 0;i < vexnum;i++)
    AdjVex[i] = -1;
  queue<int>Q;
  for (i = 0;i < vexnum;i++)
    visited[i] = false;
  for (v = 0;v < vexnum;++v)
  {
    if (!visited[v])
    {
      visited[v] = true;
      cout << v << " ";
      Q.push(v);
      while (!Q.empty())
      {
        u = Q.front();
        Q.pop();
        for(i=0,k=0;i<vexnum;i++)
          if (Matrix[u][i] == 1)
          {
            AdjVex[k] = i;
            k++;
          }
        for (i = 0, w = 0;;i++)
        {
          w = AdjVex[i];
          if (w == -1)break;
          if (!visited[w])
          {
            visited[w] = true;
            cout << w << " ";
            Q.push(w);
          }
        }
      }
    }
  }
  cout << endl;
}
int main()
{
  int t;
  int n;
  int i, j, k;
  int mx[20][20];
  cin >> t;
  for (i = 0;i < t;i++)
  {
    cin >> n;
    for (j = 0;j < n;j++)
      for (k = 0;k < n;k++)
        cin >> mx[j][k];
    Map m;
    m.SetMatrix(n, mx);
    m.BFSTraverse();
  }
  return 0;
}


5. 货币套汇(图路径)


题目描述


套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如,假定1 美元可以买0.7 英镑,1 英镑可以买9.5 法郎,1法郎可以买到0.16美元。通过货币兑换,一个商人可以从1 美元开始买入,得到0.7×9.5×0.16=1.064美元,从而获得6.4%的利润。 给定n种货币c1 ,c2 ,… ,cn的有关兑换率,试设计一个有效算法,确定货币间是否存在套汇的可能性。


提示:判断图上是否出现正环,即环上所有的边相乘大于1


输入


第一行:测试数据组数


每组测试数据格式为:


第一行:正整数n (1< =n< =30),正整数m,分别表示n种货币和m种不同的货币兑换率。


2~n+1行,n种货币的名称。


n+2~n+m+1行,每行有3 个数据项ci,rij 和cj ,表示货币ci 和cj的兑换率为 rij。


输出


对每组测试数据,如果存在套汇的可能则输出YES


如果不存在套汇的可能,则输出NO。


输入样例


2

3 3

USDollar

BritishPound

FrenchFranc

USDollar 0.5 BritishPound

BritishPound 10.0 FrenchFranc

FrenchFranc 0.21 USDollar

3 6

USDollar

BritishPound

FrenchFranc

USDollar 0.5 BritishPound

USDollar 4.9 FrenchFranc

BritishPound 10.0 FrenchFranc

BritishPound 1.99 USDollar

FrenchFranc 0.09 BritishPound

FrenchFranc 0.19 USDollar


输出样例


YES

NO


参考代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<utility>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 45
double path[MAX][MAX];
map<string, int>ratemap;
bool Floyd(int n)
{
  for (int k = 0;k < n;k++)
  {
    for (int i = 0;i < n;i++)
    {
      for (int j = 0;j < n;j++)
      {
        if (path[i][j] < path[i][k] * path[k][j])
          path[i][j] = path[i][k] * path[k][j];
      }
    }
  }
  for (int i = 0;i < n;i++)
  {
    if (path[i][i] > 1)
      return true;
  }
  return false;
}
int main()
{
  int n, m, count = 1;
  int t;
  cin >> t;
  string nameA, nameB, name;
  double rate;
  while (t--)
  {
    memset(path, 0, sizeof(path));
    cin >> n >> m;
    for (int i = 0;i < n;i++)
    {
      cin >> name;
      pair<string, int>a(name, i);
      ratemap.insert(a);
      path[i][i] = 1;
    }
    //cin >> m;
    for (int i = 0;i < m;i++)
    {
      cin >> nameA >> rate >> nameB;
      path[ratemap[nameA]][ratemap[nameB]] = rate;
    }
    if (Floyd(n)) cout <<"YES" << endl;
    else cout <<"NO" << endl;
    count++;
    ratemap.clear();
  }
  return 0;
}


相关文章
|
5月前
|
存储 算法
数据结构===图
数据结构===图
|
4月前
|
算法 Python
逆袭之路!用 Python 玩转图的 DFS 与 BFS,让数据结构难题无处遁形
【7月更文挑战第12天】图的遍历利器:DFS 和 BFS。Python 中,图可表示为邻接表或矩阵。DFS 沿路径深入,回溯时遍历所有可达顶点,适合找路径和环。BFS 层次遍历,先近后远,解决最短路径问题。两者在迷宫、网络路由等场景各显神通。通过练习,掌握这些算法,图处理将游刃有余。
59 3
|
4月前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
36 1
|
5月前
|
算法 Java
Java数据结构与算法:贪心算法之最小生成树
Java数据结构与算法:贪心算法之最小生成树
|
5月前
|
算法 C语言
数据结构与算法——最小生成树问题(什么是最小生成树、Prim算法、Kruskal算法)
数据结构与算法——最小生成树问题(什么是最小生成树、Prim算法、Kruskal算法)
30 0
|
5月前
|
存储
数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)
数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)
63 0
|
5月前
|
存储 算法
数据结构学习记录——图应用实例-六度空间(题目描述、算法思路、伪代码及解读、图解)
数据结构学习记录——图应用实例-六度空间(题目描述、算法思路、伪代码及解读、图解)
51 0
|
5月前
|
存储 算法 安全
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
37 0
|
5月前
|
存储 C语言
数据结构学习记录——图的遍历(深度优先搜索、广度优先搜索、为什么需要两种遍历、图不连通怎么办)
数据结构学习记录——图的遍历(深度优先搜索、广度优先搜索、为什么需要两种遍历、图不连通怎么办)
56 0
|
5月前
|
存储 机器学习/深度学习
数据结构学习记录——什么是图(抽象数据类型定义、常见术语、邻接矩阵表示法、邻接表表示法)
数据结构学习记录——什么是图(抽象数据类型定义、常见术语、邻接矩阵表示法、邻接表表示法)
59 0