精华内容
下载资源
问答
  • 判断给定有向图是否存在回路

    千次阅读 2018-06-14 18:17:10
    判断给定有向图是否存在回路。输入第一行为图中顶点的个数n; 第二行为途中弧度条数e; 第二行为顶点信息;接着e行为e条弧依附的两个顶点。输出该图是否存在回路,是输出yes;,不是输出no。样例输入4 4A B C D A B...
    判断给定有向图是否存在回路。

    输入

    第一行为图中顶点的个数n; 第二行为途中弧度条数e; 第二行为顶点信息;接着e行为e条弧依附的两个顶点。

    输出

    该图是否存在回路,是输出yes;,不是输出no。

    样例输入

    4
    A B C D 
    A B 
    A C 
    B D 
    C D

    样例输出

    no
    #include<iostream>
    using namespace std;
    #define maxsize 100
    int vis[maxsize] = {0};
    int a[maxsize][maxsize];
    int juge=0;
      
    void findH(int n,int v)
    {
        //vis[v] = 1;
        //if ( cnt!= 0 && v1 == v)juge = 1;
        int i;
        if (juge)return;
        for (i = 0; i < n; i++)
        {
            if (!vis[i] && a[v][i]){ vis[i] = 1; findH(n, i); vis[i] = 0; }//没有被访问过的点
            else if (a[v][i]&& v != i)juge = 1;
        }
    }
      
    int main()
    {
        int n, m, i;
        char ch[maxsize],char1,char2;
        cin >> n;
        cin >> m;
        for (i = 0; i < n;i++)
        cin >> ch[i];
        for (i = 0; i < m; i++)
        {
                cin >> char1 >> char2;
                a[char1-'A'][char2-'A'] = 1;
        }
        vis[0] = 1;
        findH(n,0);
        juge?cout << "yes":cout << "no";
        //system("pause");
        return 0;
    }

    展开全文
  • 判断给定有向图是否存在回路 swustoj

    千次阅读 2018-05-05 16:05:38
    判断给定有向图是否存在回路 1000(ms) 10000(kb) 1465 / 3415Tags: 图判断给定有向图是否存在回路。输入第一行为图中顶点的个数n; 第二行为途中弧度条数e; 第二行为顶点信息;接着e行为e条弧依附的两个顶点。...
    判断给定有向图是否存在回路
     1000(ms)
     10000(kb)
     1465 / 3415
    Tags: 图
    判断给定有向图是否存在回路。

    输入

    第一行为图中顶点的个数n; 第二行为途中弧度条数e;
    第二行为顶点信息;接着e行为e条弧依附的两个顶点。

    输出

    该图是否存在回路,是输出yes;,不是输出no。

    样例输入

    4
    4
    A B C D
    A B
    A C
    B D
    C D

    样例输出

    no

    #include<iostream>
    using namespace std;
    int map[105][105]={0},v[1005]={0};
    int n,m,k=0;
    void dfs(int x)
    {
    if(k) return;
    for(int i=0;i<n;i++)
    {
    if(map[x][i]&&v[i]==0)
    {
    v[i]=1;
    dfs(i);
    v[i]=0;
    }
    else if(map[x][i])
    k=1;
    }
    }
    int main()
    {
    char a[20];
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
    cin>>a[i];
    }
    while(m--)
    {
    char a,b;
    cin>>a>>b;
    map[a-'A'][b-'A']=1;
    }
    dfs(0);
    if(k) cout<<"yes";
    else cout<<"no";
    return 0;
    }
    展开全文
  • 判断给定有向图是否存在回路。 输入 第一行为图中顶点的个数n; 第二行为途中弧度条数e; 第二行为顶点信息;接着e行为e条弧依附的两个顶点。 输出 该图是否存在回路,是输出yes;,不是输出no。 样例输入 4 4 A B C D...

    题目描述
    判断给定有向图是否存在回路。

    输入
    第一行为图中顶点的个数n; 第二行为途中弧度条数e;
    第二行为顶点信息;接着e行为e条弧依附的两个顶点。

    输出
    该图是否存在回路,是输出yes;,不是输出no。

    样例输入

    4
    4
    A B C D
    A B
    A C
    B D
    C D
    

    样例输出

    no
    

    参考书籍《算法笔记》414页
    做法:
    可通过拓扑排序,判断有向图中是否存在环。步骤如下:
    ①定义一个队列Q,并把所有入度为0的结点加入队列
    ②取队首结点,输出。然后删除所有从它出发的边,并令这些边到达的顶点的入度减一。
    0如果某个顶点的入度减为0,则将其加入队列
    ③反复进行②操作,直到队列为空。如果队列为空时入过队的结点数目恰好为N,说明拓扑排序成功,
    图G为有向无环图;否则,拓扑排序失败,图G中有环

    #include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    const int maxn=100;
    vector<int>G[maxn];//邻接表
    int n,m,inDegree[maxn]={0};
    bool TopSort()
    {
        int num=0;//记录加入拓扑序列的顶点数
        queue<int>q;//存放入度为0的结点
        for(int i=0;i<n;i++)
        {
            if(inDegree[i]==0)//入度为0的结点入队
            {
                q.push(i);
            }
        }
        while(!q.empty())
        {
            int u=q.front();//取队首元素
            q.pop();//出队
            for(int i=0;i<G[u].size();i++)//取邻接点
            {
                int v=G[u][i];//邻接点记为v
                inDegree[v]--;//删除u->v这条边,所有v的入度减一
                if(inDegree[v]==0)//如果v的入度为0,则把v入队
                q.push(v);
            }
            G[u].clear();//删除u的出边
            num++;
        }
        if(num==n) return true;//是有向无环图
        else return false;//不是有向无环图
    }
    int main()
    {
    
        int U,V;
        char u,v,ch;
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            cin>>ch;//可以不用这个数据
        }
        for(int j=0;j<m;j++)
        {
            cin>>u>>v;
            //字母u减去'A',表示字母u与字母A的距离
            //如u=A时,u-'A'=0,即把字母转为数字
            U=(u-'A');
            V=(v-'A');
            G[U].push_back(V);//U的邻接点为V
            inDegree[V]++;//V结点的入度加一
        }
        //TopSort返回是否有环路,无环路,返回true,有环路,返回false
        if(TopSort()) cout<<"no";
        else cout<<"yes";
    }
    
    
    展开全文
  • 1076: 判断给定有向图是否存在回路 题目描述 判断给定有向图是否存在回路。 输入 第一行为图中顶点的个数n; 第二行为途中弧度条数e; 第二行为顶点信息;接着e行为e条弧依附的两个顶点。 输出 该图是否存在回路,是...

    1076: 判断给定有向图是否存在回路
    题目描述
    判断给定有向图是否存在回路。
    输入
    第一行为图中顶点的个数n; 第二行为途中弧度条数e;
    第二行为顶点信息;接着e行为e条弧依附的两个顶点。
    输出
    该图是否存在回路,是输出yes;,不是输出no。
    样例输入

    4
    4
    A B C D
    A B
    A C
    B D
    C D

    样例输出

    no

    #include<bits/stdc++.h>
    using namespace std;
    int m, n, flag=0;
    int a[100][100];
    int visited[100];
    char str[100];
    void DFS(int j, int start)                  //DFS基于深度优先遍历算法(一笔画思想)
    {
        if(visited[j]==0)                       //点j未被访问时
        {
            if(j==start) flag=1;
            visited[j]=1;                       //标记点Vj
            for(int i=0;i<n;i++)
            {
                if(a[j][i]!=0&&visited[i]==0)
                {
                    DFS(i, start);
                }
            }
            visited[j]=0;                       //还原标记点Vj
        }
    }
    int main()
    {
        cin >> n;                               //n为顶点的个数
        cin >> m;                               //e为途中弧度条数
        for(int i=0;i<m;i++)
        {
            getchar();                          //吸收回车和空格
            cin >> str[i];                      //sacnf("%c", &str[i]);为顶点信息
        }
        for(int i=0;i<m;i++)                    //转为邻接矩阵
        {
            char b, c;                          
            getchar();                          //吸收回车
            cin >> b;							//scanf("%c", &b); 
            getchar();                          //吸收空格
            cin >> c;							//scanf("%c", &c); 
            for(int j=0;j<n;j++)                //找到对应行列,将其赋值为1
            {
                if(str[j]==b)
                {
                    for(int k=0;k<n;k++)
                    {
                        if(str[k]==c)
                        {
                            a[j][k]=1;
                            break;
                        }
                    }
                     break;
                }
            }
    
        }
        for(int i=0;i<n;i++)                    //依次判断从起点V0到Vn-1是否有连通回路
        {
            for(int j=0;j<n;j++)
            {
                if(a[i][j]!=0)                  //点Vi到Vj连通
                {
                    DFS(j, i);
                }
            }
        }
    
        if(flag==1) cout << "yes";				//printf("yes");
        else cout << "no";						//printf("no");
    
        return 0;
    }
    

    以上方法仅供参考,欢迎互联网的广大朋友们提出指正。

    展开全文
  • 判断一个有向图是否存在回路

    千次阅读 2020-12-13 10:10:45
    loop函数无论是强连通和非强连通均能判断是否存在回路。 在loop函数中 1.visited数组用于记录被访问过的节点,和DFS算法中的visited数组相同。 2.count数组只有一个元素即count[0],初始值为1,若能找到回路,...
  • 判断给定有向图是否存在回路 1000(ms) 10000(kb) 1969/4499 Tags:图 判断给定有向图是否存在回路。 输入 第一行为图中顶点的个数n; 第二行为途中弧度条数e; 第二行为顶点信息;接着e行为e条弧依附的两个...
  • 5——判断有向是否存在回路

    万次阅读 2019-06-22 09:32:13
    为了判断有向图是否存在环,可以通过深度优先搜索的方法来实现。从编号0的顶点出发,若两个顶点间存在路径,则记录下源顶点标记为已访问(标记为-1)。在遍历的过程中,若有顶点与源顶点相同,则说明存在环。 ...
  • 参考王红梅、胡明、王涛编著的《数据结构(C++版)》中的思想,采用并查集判断无向图是否存在回路。 //无向图判断是否有环路。 #include <iostream> using namespace std; #define N 1000 typedef struct ...
  • 问题:给出一个算法,用它来确定一个给定的无向G=(V,E)中是否包含一个回路。所给出的算法的运行时间为O(V),这一时间独立于|E| 解答:我们都知道对于一个无向而言,如果它能表示成一...那么这个无向一定存在回路
  • 如何判断一个是否存在回路

    千次阅读 2013-09-07 11:25:52
    问题描述:给一个G=,问如何判断这个是否存在回路?请给出至少3中方法 分析: 方法1:利用减枝的方法,如果G为有向:  1)首先删除入读为0的点,并且将对应的和该点相连的点的入读-1。(可以用一...
  • 并查集判断无向是否存在回路

    千次阅读 2018-11-29 21:39:18
    并查集判断图是否存在回路: A连接B,AB的pre本来不相同,Union使它们pre相同;B连接C,BC的pre本来不相同,Union使它们的pre相同; C连接A,AC的pre本来就相同,说明成环。 #include<bits/stdc++.h> ...
  • 判断一个有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用() A 求关键路径的方法 B 求最短路径的Dijkstra方法 C 深度优先遍历算法 D 广度优先遍历算法 答案:C (dfs) 利用深度优先遍历可以判断图G中...
  • 拓扑排序判断,相关解释在代码中就不多赘述了。 #include <iostream> #include <vector> #include <queue> using namespace std; vector<int> m; queue<int> n,s; int A[1005][1005];...
  • 头文件"AdjGraph.h" #include #define VISITED 1 #define UNVISITED 0 #define EXIST 1 #define INEXIST 0 using namespace std;...该有向为:V1->V2 V1->V3 V3->V5 V5->V6 V6->V3 V4->V6
  • cout有向图存在环路!"; } int main() { Graph g; create_graph(g); print_graph(g); cout拓扑排序:"; topologicalsort(g); return 0; } 测试用例一: 测试用例二: ...
  • 判断一个有向是否存在回路,并进行输出(拓扑算法)
  • 给出一个算法,用它来确定一个给定的无向G=(V,E)中是否包含一个回路。所给出的算法的运行时间为O(V),这一时间独立于|E|解答:我们都知道对于一个无向而言,如果它能表示成一棵树,那么它一定没有回路,并且有|E...
  • 题意: 就是对有无向边和有向边的混合判断存不存在欧拉回路。   参考下面的解释:   【混合】 混合(既有有向边又有无向边的)中欧拉环、欧拉路径的判定需要借助网络流! (1)欧拉环的判定: ...
  • C语言判断临界矩阵表示的图是否存在回路?请问代码怎么写,是数据结构里面的?
  • 判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用______。A.求关键路径的方法B.求最短路径的Dijkstra方法C.深度优先遍历算法D.广度优先遍历算法 所有的考研数据结构参考书给出的答案都是C,但...
  • #include&lt;iostream&gt; #include&lt;cstring&gt; using namespace std; int map[50][50]; bool v[50],k; int n,m,i,j; void Init() { for(i=0;i&lt;n;i++) for(j=0;...void...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 850
精华内容 340
关键字:

判断图是否存在回路