精华内容
下载资源
问答
  • 每组测试数据第一行为两个正整数nm,表示有向图的顶点数和边数,顶点序号 从1开始记。接下来为m行,每行两个正整数, 表示一条边的起点终点。每条边出现一次 且仅一次,不存在自身环重边。输入文件最后一行为0...
    ///数组下标元素是从0开始记的,而图的顶点序号通常是从1开始计的,
    ///为避免繁琐,通常默认这种关系
    /*
    输入描述:输入文件中包含多组测试数据;每组测试数据描绘了一个无权有向图;
    每组测试数据第一行为两个正整数n和m,表示有向图的顶点数和边数,顶点序号
    从1开始记。接下来为m行,每行两个正整数, 表示一条边的起点和终点。每条边出现一次
    且仅一次,不存在自身环和重边。输入文件最后一行为0 0,表示文件结束
    输出描述:输出两行。第一行为n个正整数,表示每个顶点的出度。第二行为
    n个整数,表示每个顶点的入度;每两个正整数之间用一个空格隔开,每行的最后
    一个正整数之后没有空格。
    */
    #include<cstdio>
    #include<cstring>
    #define MAXN 100
    int Edge[MAXN][MAXN];
    int main()
    {
        int n,m;
        int u,v;
        int od,id;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            if(n==0&&m==0) break;
            memset(Edge,0,sizeof(Edge));
            for(int i=0;i<m;i++)///构造临结矩阵
            {
                scanf("%d%d",&u,&v);
                Edge[u-1][v-1]=1;
            }
            for(int i=0;i<n;i++)///输出出度
            {
                od=0;
                for(int j=0;j<n;j++) od+=Edge[i][j];
                if(i==0) printf("%d",od);
                else printf(" %d",od);
            }
            printf("\n");
            for(int j=0;j<n;j++)///输出入度
            {
                id=0;
                for(int i=0;i<n;i++) id+=Edge[i][j];
                if(j==0) printf("%d",id);
                else printf(" %d",id);
            }
            printf("\n");
        }
        return 0;
    }
    

     

    展开全文
  • 2.求有向图的入度,出度,度 3.输出图(图的遍历) (注:图的创建时,直接输入字符定点之间关系) #include &amp;amp;amp;lt;iostream&amp;amp;amp;gt; #include &amp;amp;amp;lt;stdio.h&amp;amp;...

    设计算法实现:
    1.建立有向邻接表
    2.求有向图的入度,出度,度
    3.输出图(图的遍历)
    (注:图的创建时,直接输入字符和定点之间关系)

    这里写图片描述

    #include <iostream>
    #include <stdio.h>//注意
    #include <stdlib.h>//注意
    using namespace std;
    #define MAX_VERTEX_NUM  20
    typedef char VertexType,VexType;
    typedef int EdgeType,InfoType;
    typedef struct ArcNode{ //边(弧)结点的类型定义
        int  adjvex;   //边(弧)的另一顶点的在数组中的位置
        ArcNode *nextarc;//指向下一边(弧)结点的指针
        InfoType *info;      //该弧相关信息的指针
    }ArcNode;
    typedef struct Vnode{//顶点结点及其数组的类型定义
        VertexType data;    //顶点信息
        ArcNode * firstarc;    //指向关联该顶点的边(弧)链表
    } Vnode, AdjList[MAX_VERTEX_NUM];
    typedef struct {
        AdjList  vertices;
        int  vexnum, arcnum;    //图的当前顶点数和弧数
        int  kind;    //图的种类标志
    } ALGraph;    //图邻接表类型
    
    int  LocateVex(ALGraph  &G , VexType vp)
    {
        int  k=0 ;
        for (k=0 ; k<G.vexnum ; k++)
        {if (G. vertices[k].data==vp)  return(k) ;}
        return(-1) ;     /*  图中无此顶点  */
    }
    void CreatALGraph(ALGraph &G)//有向带权图的创建
    {
        char e1,e2=0;
        int k,l=0,m=0;
        ArcNode *s;
        cin>>G.vexnum>>G.arcnum; //输入顶点数和边数
        for( int i=0;i<G.vexnum;i++)
        {   cin>>G.vertices[i].data;//输入顶点信息
            G.vertices[i].firstarc=NULL;
        }
        for(k=0;k<G.arcnum;k++)
        {   cin>>e1>>e2;
            s=(ArcNode*)malloc(sizeof(ArcNode));
            l=LocateVex(G, e1);
            m=LocateVex(G , e2);
            s->adjvex=m;
            s->nextarc=G.vertices[l].firstarc;
            G.vertices[l].firstarc=s;
        }
    }
    void OutputALGraph(ALGraph &G)//邻接表的输出
    {   int i;
        for(i=0;i<G.vexnum;i++)
        {   ArcNode * s;
            s=G.vertices[i].firstarc;
            while(s!=NULL)
            {  printf("\t%d",s->adjvex);
                s=s->nextarc;   }
            printf("\n");
        }
    }
    void Degree(ALGraph &G)//入度 出度 度
    {   int k,t;
        ArcNode *p ;
        int indegree[100];
        int outdegree[100];
        for (k=0; k<G.vexnum; k++)
        {   indegree[k]=0 ;/*  顶点入度初始化  */}
    
        for (k=0; k<G.vexnum; k++)
        {
            outdegree[k]=0;/*  顶点出度初始化  */
            p=G.vertices[k].firstarc ;
            t=0;
            while (p!=NULL)     /*  顶点入度统计  */
            {   t=p->adjvex;
                outdegree[k]++;
                //printf("%d",t);
                indegree[t]++ ;
                p=p->nextarc ;   }
        }
        for(int i=0;i<G.vexnum;i++)
        {
            cout <<G.vertices[i].data<<" "<<indegree[i]<<" "<<outdegree[i]<<" "<<indegree[i]+outdegree[i]<<endl;
        }
    }
    
    int main()
    {
        ALGraph G;
        CreatALGraph(G);
        //OutputALGraph(G);
        Degree(G);
        return 0;
    }
    
    

    结果如下:
    这里写图片描述

    展开全文
  • 邻接矩阵   邻接矩阵是为图服务的,记录了图间定顶点间的关系。图又分为有向图和无向图。...  度:   顶点的度就是该顶点的入度和出度之和   入度:   以该顶点为终点的有向边的数目。(其实就是

    邻接矩阵
      邻接矩阵是为图服务的,记录了图间定顶点间的关系。图又分为有向图无向图

    有向图:

      概念:
       图中的每条边都是由方向的 ,所有边都有方向的图称为有向图。

      例图:
    在这里插入图片描述

    无向图:

      概念:
       图中的每一条边都是无方向的,以此构成的图就是无向图

      例图:
    ![在这里插入图片描述---(https://img-blog.csdnimg.cn/20190901085541378.png)

    怎么在邻接矩阵中查看度呢?
    概念:
       邻接矩阵就是为了表示图中各个顶点间的关系,有关系是1,没有关系是0.
      
    度:
       顶点的度就是该顶点的入度和出度之和
      
    入度:
       以该顶点为终点的有向边的数目。(其实就是被指向。——>自己)
      
    出度:
       以该顶点为起点的有向边的数目。(其实就是指出去 自己——>)

    看图:
      有向图邻接矩阵
      (与上图有向图例图一致)
    在这里插入图片描述
      如何依据临界矩阵推出某点的入度、出度、度呢

      以A为例。A的入度为1,出度为3。对应临界矩阵如下图
      A的入度:
        在这里插入图片描述
      A的出度:
        在这里插入图片描述
        总结:;邻接矩阵横向为该顶点的出度,纵向为该节点的入度,度=横向+纵向
    无向图邻接矩阵
        无向图没有入度和出度的概念,所以只涉及到度,下面叙述如何通过邻接矩阵找出无向图的度。
        无向图是一个中线对称的。
    在这里插入图片描述
        通过邻接矩阵我们可以看出,无向图是一个中埃及
        依旧以A为例,查看A的度。
    在这里插入图片描述
    在这里插入图片描述
        因为无向图的特殊性所以它的横向和纵向是一一对应的,看度的话我们只需要选择其一看接可以

    展开全文
  • 欧拉回路第一题TVT 本题的一个小技巧在于: 【建立一个存放点与边关系的邻接...有向图: 欧拉回路:连通 + 所有点的入度 == 出度 欧拉路径:连通 + 源点 出度-入度=1 && 终点 入度 - 出度 = 1 &&...

    欧拉回路第一题TVT

    本题的一个小技巧在于:

    【建立一个存放点与边关系的邻接矩阵】

    1.先判断是否存在欧拉路径

    无向图:

    欧拉回路:连通 + 所有定点的度为偶数

    欧拉路径:连通 + 除源点和终点外都为偶数

     

    有向图: 

    欧拉回路:连通 + 所有点的入度 == 出度

    欧拉路径:连通 + 源点 出度-入度=1 && 终点 入度 - 出度 = 1 && 其余点 入度 == 出度;

     

    2.求欧拉路径 :

    step 1:选取起点(如果是点的度数全为偶数任意点为S如果有两个点的度数位奇数取一个奇数度点为S)

    step 2:对当前选中的点的所有边扩展,扩展条件(这条边为被标记),若可扩展 ->step 2;否则 step 3;

    step 3:将次边计入path结果保存。

     

    思路还是很清晰的。

    贴代码了:

     1 #include <stdio.h>
     2 #include <string.h>
     3 #include <stdlib.h>
     4 #include <math.h>
     5 #include <iostream>
     6 #include <stack>
     7 #include <queue>
     8 #include <algorithm>
     9 
    10 #define ll long long
    11 using namespace std;
    12 const int INF = 0x3f3f3f3f;
    13 const int MAXN = 8000;
    14 int vis[2000], indegree[50], map[50][2000], n;
    15 stack <int> s;
    16 
    17 void init(){
    18     n = 0;
    19     memset(vis, 0, sizeof(vis));
    20     memset(map, 0, sizeof(map));//define the relationship between vertex and edge
    21     memset(indegree, 0, sizeof(indegree));
    22 }
    23 
    24 int euler(int u){
    25     int i;
    26     for(i = 1; i <= n; ++i){// n represents edges
    27         if(map[u][i] && !vis[i]){
    28             vis[i] = 1;
    29             euler(map[u][i]);
    30             s.push(i);
    31         }
    32     }
    33     return 0;
    34 }
    35 
    36 int main(){
    37     int first, i, j, x, y, w;
    38     while(cin >> x >> y){
    39         if(x == 0 && y == 0)    break;
    40         cin >> w;
    41         init();
    42         map[x][w] = y;
    43         map[y][w] = x;
    44         ++indegree[x];
    45         ++indegree[y];
    46         first = x > y ? y : x;//get first vertex , but speacil judge as u casual
    47         n = n > w ? n : w;//get numbered largest edge
    48         while(true){
    49             cin >> x >> y;
    50             if(!x && !y)
    51                 break;
    52             cin >> w;
    53             map[x][w] = y;
    54             map[y][w] = x;
    55             ++indegree[x];
    56             ++indegree[y];
    57             n = n > w ? n : w;
    58         }
    59         for(i = 1; i < 45; ++i)//judge if exists solution
    60             if(indegree[i] % 2) break;
    61         if(i < 45)
    62             cout << "Round trip does not exist.\n";
    63         else{
    64             euler(first);
    65             while(!s.empty()){
    66                 cout << s.top() << ' ';
    67                 s.pop();
    68             }
    69             cout << endl;
    70         }
    71     }
    72     return 0;
    73 }

     

    转载于:https://www.cnblogs.com/wushuaiyi/p/3890960.html

    展开全文
  • 6.1_1_图的基本概念

    2020-06-04 23:30:47
    图的定义 图G由顶点集V和边集E组成,|V|表示顶点的个数,又称作G的阶,|E|表示边的条数 线性表可以使空表,树可以使空树,但图不可以是空...有向图入度 = 出度 = |e| 顶点-顶点的关系 路径–顶点p到顶点q的路径是顶
  • 入度有向图中某点作为图中边终点次数之 出度: 对于有向图来说,顶点出边条数即为该顶点的出度 调度系统中有向无环图 数据调度系统中,多个任务之间依赖关系,用图可以表示,如下图所示,每个顶点表示...
  • 图 1.图简述 ...有向图的边是有明确方向的; 有向无环图:如果一个有向图,从任意顶点出发无法经过若干条边回到该顶点,那么它就是一个有向无环图。 3.2 出度和入度 出度 入度适用于有向图; 出度
  • 题意: 给出推到关系,那么问还要几步才能推出所有命题等价 思路: 命题等价就是双连通,所以...算法是强连通分量数-(出度入度的最大值) 代码: #include #include #include #include #include #include using nam
  • 备战蓝桥杯 依旧是二蛋小白的迷惑...2.所有顶点的入度 等于 出度。 3.n个顶点的有向完全图有n(n-1)条边。 4.n个顶点的强连通图至少有n条边。 无向图* 在无向图中有以下几点结论: 1.所有顶点的度数之
  • 一:总结图的基本概念: 1.图分为有向图(入度和出度)和无向图(最大边数n(n-1)/2); 2.图的存储结构: 1)关联矩阵(表示了图的结构,即图中各结点的后件关系):...有向图的不一定是对称矩阵且对角线不一定为0;
  • 图中入口节点的入度和出口节点的出度都为0,其余任意节点都至少有一条入边和一条出边。 根据有向无环图的性质,每一个有向无环图中的所有节点能形成有限个拓扑序,拓扑序中的节点只能向后序的节点出边(即一条依赖
  • 【alg4-图】有向图

    2020-12-17 08:55:30
    有向图有向图中,边是单向的:每条边所连接的两个顶点都是一个有序对,它们的...除了特殊的图,一幅有向图中的两个顶点的关系可能有4种: 没有边相连; 存在从v到w的边v->w; 存在从w到v的边w->v; 即存在v-&
  • 图的介绍 图 ( Graph ),是一种复杂的非线性表结构,图中的元素成为顶点 ( vertex ),每...根据图的边,是否有单向性,分为有向图和无向图,在有向图中,度分为入度和出度,入度是有多少条边指向顶点,出度是有多少...
  • 图的概念 树中的元素称为节点,图中的元素称为作顶点Vertex。...无向图中度表示一个顶点有多少条边,在有向图中,把度分为入度In-Degree和出度Out-Degree。 入度表示有多少条边指向这个顶点,出...
  • 度数:分为入度和出度,入度表示被指向数,出度表示出发数 路径:如1到5路径 有向图、无向图:边是否带有箭头,图中表示有向图 为什么需要图? 假设一个项目中有多个任务,这些任务之间部分是存在现后顺序...
  • 有向图和无向图:指代方向的边的集合与不带方向的变得集合(两个方向的边的集合) (如下图)   度 点的入度:以该顶点为终点的边的数目。 点的出度:以该顶点为起点的边的数目。 点的度:等于该...
  • 传送门 第一次做这种题, 尽管ac了但是完全不知道为什么这么做。 题目就是给一些边, 有向边与无向边混合, 问你是否存在欧拉回路。... 如果全都满足, 就判断每个点的入度出度的大小关系, 入度>出度,...
  • 图常用的几个概念: 有很少边或弧(如 ee 顶点的度是指依附于某个顶点的边数。下图是电视剧《琅琊榜》的人物关系图,从图上我们发现和顶点“萧景琰...在有向图中,我们需要学习顶点的入度和出度这两个概念。顶点的
  • 有向图顶点分为入度和出度。 图上边或弧带有权则称为网。 图中顶点间存在路径,两顶点存在路径则说明是连通,如果路径最终回到起始点则称为环,当中不重复叫简单路径。若任意两顶点都是连通,则图就是连通...
  • 图的概念 ...在有向图中又分为入度和出度,入度表示多少条边指向这个顶点,出度表示有多少条边是以这个顶点为起点指向其他顶点。 图的存储方法 1. 邻接矩阵(adjacency matrix)   邻接矩阵底层依...
  • 数据结构(七)

    2017-09-23 21:43:51
    度(有向图分为入度和出度) 第一个顶点到最后一个顶点相同路径称为回路或环。 序列中不重复出现路径称为简单路径。 除了第一个顶点和最后一个顶点之外,其余顶点不重复出现回路,称为简单回路或
  • 边有方向的图叫做“有向图”。 顶点的入度(In-degree),表示有多少条边指向这个顶点 顶点的出度(Out-degree),表示有多少条边是以这个顶点为起点指向其他顶点 对应到微博的例子,入度就表示有多少粉丝,...
  • 图的简介

    2021-03-08 09:47:49
    无向图顶点A1度为3,有向图A1入度为1,出度为2,度为3 何为简单图? 无向完全图: 有向完全图: 在图中如果边含有权值,则一般称之为网。 子图: 路径: 环: 简单路径: 简单环同理,不能出现重复顶点...
  • 2019-12-09 21:08:10
    图: 如何存储微博、微信等这些社交网络好友关系? 为什么产生? 特点? 使用场景? ...树中元素称为节点,图中...边上增加方向概念就是有向图,此时无向图中度分为 入度 出度入度:多少条边指向这个...
  • 有向,无向,权,路径回路,连通域,邻接点,度,入边,出边,入度出度等等,很好理解,不赘述,可以参考这篇博客:http://www.cnblogs.com/skywang12345/p/3691463.html图的存储结构图可以使用两种存储结构,分别...
  • 判断方法:首先必须是强连通,对于有向图入度等于出度;对于无向图,度数为奇点是0个 欧拉开路:每条边只经过一次,且不用回到起点。 判断方法:首先必须是强连通,对于有相图,两个顶点出入度不相等,起点...
  • 题意:一些单词他们之间只要满足A最后一个字母B第一个字母相同。...(1)所有结点入度=出度一个节点入度-出度=1另一个节点出度-入度=1其他节点入度-出度。 (2)当前是弱连通。(就是当前换成...
  • 拓扑排序

    2020-03-31 21:30:28
    拓扑排序需要根据点的入度和出度,一个点的入度和出度体现了这个点的先后关系。如果一个点的入度等于0,说明它是起点,是排在最前面的。如果它的出度等于0,说明排在最后面。因为优先级相同的数的存在,拓扑排序可能...

空空如也

空空如也

1 2 3 4 5 6
收藏数 117
精华内容 46
关键字:

有向图的入度和出度的关系