精华内容
下载资源
问答
  • 一、邻接矩阵实现 ...(2) 求出图中每个顶点的出度。 (3) 求出图中出度为0 的顶点数。 #include <stdio.h> #include <stdlib.h> #include <iostream> using namespace ...

    一、邻接矩阵实现

    假设不带权有向图采用邻接矩阵 g 存储,设计实现以下功能的算法:

    1) 求出图中每个顶点的入度。

    2) 求出图中每个顶点的出度。

    3) 求出图中出度为0 的顶点数。

     

    #include <stdio.h>
    
    #include <stdlib.h>
    
    #include <iostream>
    
    using namespace std;
    
    
    
    #define INFINITY 65535
    
    #define MAX_VERTEX_NUM 100
    
    typedef char VertexType;
    
    
    
    typedef struct {
    
        VertexType vexs[MAX_VERTEX_NUM];  //顶点数组
    
        int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];     //邻接矩阵
    
        int v, e;      //图顶点和边的数量
    
    } MGraph;
    
    int num=0;   全局变量负责统计出度为0的顶点个数
    
    void CreateMGraph(MGraph &G)
    
    {
    
        int i,j,k,w;
    
        printf("输入顶点数和边数:\n");
    
        scanf("%d%d",&G.v,&G.e);
    
        //for(i=0;i<G.v;i++)
    
            //scanf("%c",G.vexs[i]);
    
        for(i=0;i<G.v;i++)
    
            for(j=0;j<G.v;j++)
    
                G.arcs[i][j]=INFINITY;    //初始化邻接矩阵
    
        for(k=0;k<G.e;k++)
    
        {
    
            printf("输入边(i,j)上的下标i,j和权w\n");
    
            scanf("%d%d%d",&i,&j,&w);
    
            G.arcs[i][j]=w;
    
        }
    
    }
    
    void indu(MGraph G)
    
    {
    
         int n=0;
    
         printf("入度:\n");
    
         for(int i=0;i<G.v;i++)
    
         {
    
             for(int j=0;j<G.v;j++)
    
             {
    
                 if(G.arcs[j][i]!=INFINITY)
    
                    n++;
    
             }
    
             printf("%d ",n);
    
             n=0;
    
         }
    
    }
    
    void outdu(MGraph G)    //要不要加引用,有时候需要仔细考虑一下
    
    {
    
         int n=0;
    
         printf("出度:\n");
    
         for(int i=0;i<G.v;i++)
    
         {
    
             for(int j=0;j<G.v;j++)
    
             {
    
                 if(G.arcs[i][j]!=INFINITY)
    
                    n++;
    
             }
    
             if(n==0)
    
                num++;
    
             printf("%d ",n);
    
             n=0;
    
         }
    
    }
    
    int main()
    
    {
    
        MGraph G;
    
        CreateMGraph(G);
    
        indu(G);
    
        printf("\n");
    
        outdu(G);
    
        printf("\n");
    
        printf("出度为0的顶点个数:%d",num);
    
        return 0;
    
    }
    
    

    二、邻接表

    假设不带权有向图采用邻接表 G 存储,设计实现以下功能的算法:

    (1)求出图中每个顶点的入度。

    (2)求出图中每个顶点的出度。

    (3)求出图中出度为0 的顶点数。

    #include <stdio.h>
    
    #include <stdlib.h>
    
    #include <iostream>
    
    using namespace std;
    
    #define INFINITY 65535
    
    #define MAX_VERTEX_NUM 100
    
    typedef int VertexType;
    
    int num=0;
    
    typedef struct ArcNode {
    
        int adjvex;     //邻接顶点的标号
    
        int weight;    //权重
    
        ArcNode *nextarc;
    
    } ArcNode;   //边表
    
    typedef struct {
    
        VertexType data; //VertexType可以写成结构体类型存储信息
    
        ArcNode *firstarc;
    
    } VNode;   //顶点数组
    
    typedef struct  {
    
        VNode adjlist[MAX_VERTEX_NUM];
    
        int v, e;
    
    } ALGraph;
    
    void CreateALGraph(ALGraph &G)   //创建邻接表
    
    {
    
        int i,j,k;
    
        ArcNode *e;
    
        printf("输入顶点数和边数:\n");
    
        scanf("%d%d",&G.v,&G.e);
    
        for(i=0;i<G.v;i++)
    
        {
    
            //scanf("%d",&G.adjlist[i].data);
    
            G.adjlist[i].firstarc=NULL;
    
        }
    
        for(k=0;k<G.e;k++)
    
        {
    
            printf("输入边(vi,vj)上的顶点序号:\n");
    
            scanf("%d%d",&i,&j);
    
            e=(ArcNode*)malloc(sizeof(ArcNode));
    
            e->adjvex=j;
    
            e->nextarc=G.adjlist[i].firstarc;
    
            G.adjlist[i].firstarc=e;
    
            /*e=(ArcNode*)malloc(sizeof(ArcNode));
    
            e->adjvex=i;
    
            e->nextarc=G.adjlist[j].firstarc;
    
            G.adjlist[j].firstarc=e;*/
    
        }
    
    }
    
    void indu(ALGraph G)
    
    {
    
        int i,j,n=0;
    
        int A[G.v];
    
        for(i=0;i<G.v;i++)
    
            A[i]=0;
    
        ArcNode *e;
    
            for(j=0;j<G.v;j++)
    
            {
    
            while(G.adjlist[j].firstarc!=NULL)
    
            {
    
                A[G.adjlist[j].firstarc->adjvex]++;
    
                e=G.adjlist[j].firstarc->nextarc;
    
                G.adjlist[j].firstarc=e;
    
            }
    
            }
    
            for(i=0;i<G.v;i++)
    
                printf("%d ",A[i]);
    
    }
    
    void outdu(ALGraph G)
    
    {
    
        int n=0,i=0;
    
        ArcNode *e;
    
        for(i=0;i<G.v;i++)
    
        {
    
            while(G.adjlist[i].firstarc!=NULL)
    
            {
    
                n++;
    
                e=G.adjlist[i].firstarc->nextarc;
    
                G.adjlist[i].firstarc=e;
    
            }
    
            if(n==0)
    
                num++;
    
            printf("%d ",n);
    
            n=0;
    
        }
    
    }
    
    int main()
    
    {
    
        ALGraph G;
    
        CreateALGraph(G);
    
        printf("出度:");
    
        outdu(G);
    
        printf("\n");
    
        printf("入度:");
    
        indu(G);
    
        printf("\n");
    
        printf("出度为0的节点数\n");
    
        printf("%d\n",num);
    
        return 0;
    
    }

     

    展开全文
  • 众所周知,这里有向图的邻接表是方便求结点出度的邻接表(对应方便求入度的表为逆邻接表)。而在这种方便求出度的普通邻接表中想求结点入度,只有在结点集合中遍历所有结点(即下图答案中for循环所做事情),...

    在这里插入图片描述
    解题思路:
    众所周知,这里有向图的邻接表指的是方便求结点出度的邻接表(对应方便求入度的表为逆邻接表)。而在这种方便求出度的普通邻接表中想求结点入度,只有在结点集合中遍历所有结点(即下图答案中for循环所做的事情),并在每一个结点的邻接表表头开始依次查找是否有指向k顶点的弧存在(即下图答案中while循环所做的事情)

    在这里插入图片描述
    可见,作为19年的倒数第二道大题,该题的思路和实现方式还是比较简单的。

    展开全文
  • 文章目录一. 图的相关概念和术语概念无向图有向图度,入度出度子图完全无向图和完全有向... 图的存储结构—邻接表无向图有向图有向图的逆邻接表图的邻接表的特点图的邻接表存储结构的类型声明四. 邻接矩阵的相关算...

    一. 图的相关概念和术语

    概念

    1. 图形结构中,结点之间的关系可以是任意的,图中任意个数元素之间都可能相关。
    2. 任何复杂的图都是由顶点和边(弧)构成的。
    3. 采用形式化的定义,图G由两个集合V和E组成,记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是连接V中两个不同顶点的边(弧)的有限集合,记为E(G).
    4. 对于含有n个顶点的图,通常用字母或自然数来唯一标识图中顶点(顶点的编号)。
      如在所给的图中,顶点可以使用字符Vi来表示,也可以用数字i(0<=i<=n-1)来表示第i个顶点Vi的编号。

    无向图

    1. 对于一个图G,若边集E(G)为无向边,则称该图为无向图。如下图。
      在这里插入图片描述
    2. 在一个无向图中,若存在一条边 (i,j),则称顶点i,j为该边的两个顶点,并称它们互为邻接点(或者相邻点)。如上图,0和1互为邻接点。

    有向图

    1. 对于一个图G,若边集E(G)为有向边,则称该图为有向图。如下图。
      在这里插入图片描述
    2. 在一个有向图中,若存在一条边(弧)<i,j>,则称此边(弧)是顶点(弧尾)i 的一条出边,同时也是顶点(弧头)j 的一条入边,称顶点 i 和 j 分别是此边的起始顶点(简称为起点)和终止顶点(简称为终点)。
      如上图,对于边<0,1>,该边是顶点0的出边,顶点1是入边,同时,顶点0称为起点,顶点1称为终点。
    3. 对于边<0,1>,则称顶点0“邻接到”顶点1,顶点1“邻接自”顶点0,弧<0,1>与顶点0和1“相关联”。

    度,入度和出度

    1. 顶点v的度记为D(v)
    2. 对于无向图,每个顶点v的度定义为和v顶点相关联的边的数目。
    3. 对于有向图,顶点的度分为入度出度
    4. 入度是以该顶点为弧头(终点)的入边数目。
    5. 出度是以该顶点为弧尾(起点)的出边数目。
    6. 该顶点的度D(v)=其出度ID(v)+其入度OD(v)
      在这里插入图片描述
    7. 若一个图中(无论有向图还是无向图)中有n个顶点和e条边,每个顶点的度为Di(0<=i<=n-1),则有:
      在这里插入图片描述
      即一个图中所有顶点的度之和=边数的两倍。

    子图

    1. 设有两个图G=(V,E)和G’=(V’,E’),若V’是V的子集,且E’是E的子集,则称G’是G的子图。
    2. 注:对于一个图G=(V,E),V’是V的子集,且E’是E的子集。而(V’,E’)可能不是一个图,所以由V的子集和E的子集并非一定构成G的子图。
      在这里插入图片描述

    完全无向图和完全有向图

    1. 对于无向图,若具有n(n-1)/2条边,则称之为完全无向图。如左图。
    2. 对于有向图,若具有n(n-1)条边,则称之为完全有向图。如右图。
      在这里插入图片描述

    稀疏图和稠密图

    边数较少(边数e<<log2(n),其中n为顶点数)的图称为稀疏图,边数较多的称为稠密图。

    简单路径,回路(环)

    1. 若一条路径的顶点序列中顶点不重复出现,则该路径为简单路径
    2. 若一条路径上的开始点和结束点为同一个顶点,则称该路径为回路(环)
    3. 除开始点和结束点相同外,其余顶点不重复出现的回路称为简单回路(简单环)

    连通,连通图和连通分量(无向图)

    1. 无向图G中,若从顶点 i 到顶点 j 有路径,则称顶点 i 和 j 是连通的
    2. 若G中任意两个顶点都是连通的,则称无向图G为连通图,否则为非连通图。
    3. 无向图G中极大连通子图称为G的连通分量

    强连通图和强联通分量(有向图)

    1. 有向图G中,若任意两个顶点 i 和 j 都是连通的,即从顶点 i 到 j 和从顶点 j 到 i 都存在路径,则称该图是强连通图
    2. 有向图G中极大强联通子图称为G的强联通分量

    权和网

    在一个图中,每条边可以标上具有某种含义的数值,该数值称为该边的,边上带权的图称为带权图,也称为。一般规定所有边的权均为非负数

    二. 图的存储结构—邻接矩阵

    邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图,顶点编号依次为0,1,…,n-1,则G的邻接矩阵是具有如下定义的n阶方阵A。
    若G是不带权的图:
    在这里插入图片描述
    若G是带权图或网:
    在这里插入图片描述
    Wij 为边(i,j)或<i,j>的权

    无向图

    在这里插入图片描述

    1. 无向图的矩阵一定是一个对称矩阵
    2. 每一行或每一列代表相应顶点的度

    有向图

    在这里插入图片描述

    1. 有向图的矩阵不一定是一个对称矩阵。
    2. 每一行代表相应顶点的出度
    3. 每一列代表相应顶点的入度

    有权图(网)

    在这里插入图片描述

    1. 有向图时不一定是一个对称矩阵。
    2. 入度和出度与有向图的计算方式一样。

    图的邻接矩阵的特点

    1. 对于n个顶点e条边的图采用邻接矩阵存储时占据存储空间为O(n*n),与边数e无关(不考虑压缩存储),特别适合存储稠密图
    2. 任何图的邻接矩阵表示是唯一的。
    3. 图采用邻接矩阵存储时判断两个顶点 i 和 j 之间是否有边十分容易。

    图的邻接矩阵类型声明

    #define INF  INT_MAX    //用整型最大值代替∞ 
    #define MAXVEX 30       //图中最大顶点个数 
    typedef char VertexType[4]; //定义VertexType为字符串类型 
    
    typedef struct vertex
    {
    	int adjvex;         //顶点编号 
    	VertexType data;    //顶点的信息 
    }VType;					//顶点类型 
    
    typedef struct graph
    {
    	int n,el			//n为实际顶点数,e为实际边数 
    	VType vexs[MAXVEX]; //顶点集合 
    	int edges[MAXVEX][MAXVEX];  //边的集合 
    }MGraph;				//图的邻接矩阵类型 
    

    三. 图的存储结构—邻接表

    1. 邻接表是图的一种链式存储结构
    2. 在邻接表中,对图中每个顶点建立一个单链表,把该顶点的所有相邻点串起来。
    3. 所有的头指针构成一个数组,称为表头结点数组,用adjlist表示,第 i 个单链表adjlist[ i ] 中的结点表示依附于顶点 i 的边,也就是说头指针数组元素的下标与顶点编号一致。
    4. 表头结点的设置:
      在这里插入图片描述
    5. 单链表中的每个结点由3个域组成:
    顶点域adjvex  :   用以指示该相邻点在头结点数组中的下标
    权值域weight  :   存放对应边的权值
    指针域naxtarc :   用以指向依附于顶点i的下一条边所对应的结点
    
    1. 对于不带权的图,weight域可以不设置;对于带权图,weight域设置为相应边的权值
      在这里插入图片描述

    无向图

    在这里插入图片描述
    每个单链表的长度就是相应顶点的度

    有向图

    在这里插入图片描述

    每个单链表的长度表示相应点的出度大小
    对所有的单链表进行遍历可以计算出相应点的入度大小

    有向图的逆邻接表

    在有向图中求入度大小很麻烦,因此建立一个有向图的逆邻接表,即对每个顶点Vi建立一个链接以Vi为头的弧的表。
    每条单链表的长度为相应点的入度大小

    图的邻接表的特点

    1. 对于n个顶点e条边的图采用邻接矩阵存储时占据存储空间为O(n+e),与边数e有关,特别适合存储稀疏图
    2. 任何图的邻接矩阵表示不一定是唯一的。这是因为邻接表的每个单链表中,各结点的顺序是任意的。
    3. 图采用邻接表存储时查找一个顶点 的所有相邻顶点十分容易。

    图的邻接表存储结构的类型声明

    typedef char VertexType[10];  //VertexType为字符串类型 
    
    
    typedef struct edgenode
    {
    	int adjvex;               //相邻点序号 
    	int weight;				  //边的权值
    	struct edgenode *nextatc; // 下一条边的顶点 
    }ArcNode;					  //每个顶点建立的单链表中边结点的类型 
    
    
    typedef struct vexnode
    {
    	VertexType data;		  //存放一个顶点的信息 
    	ArcNode *firstarc;        //指向第一条边结点 
    }VHeadNode;                   //单链表的头结点类型 
    
    typedef struct
    {
    	int n,e;                  //n为实际顶点数,e为实际边数 
    	VHeafNode adjlist[MAXVEX];//单链表头结点数组 
    }ALGraph;                     //图的邻接表类型 
    

    四. 邻接矩阵的相关算法

    建立图的邻接矩阵算法

    void CreateGraph(MGraph &g, int a[][MAXVEX],int n, int e)
    {
    	int i,j;
    	g.n=n;
    	g.e=e;
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<n;j++)
    		{
    			g.edges[i][j]=A[i][j];
    		}
    	}
    }
    

    求无向图顶定度算法

    int Degree(MGraph g, int v)
    {
    	int i,d=0;
    	if(v<0 || v>=g.n)
    		return -1;      //顶点编号错误返回-1 
    	for(i=0;i<g.n;i++)
    	{
    		if(g.edges[v][i]>0 && g.edges[v][i]<INF)
    			d++;       //统计第v行既不为0也不为∞的边数即度 
    	}
    	return d;
    }
    

    求有向图顶点度算法

    int Degree(MGraph g, int v)
    {
    	int i,d1=0,d2=0,d;
    	if(v<0 || v>=g.n)
    		return -1;      //顶点编号错误返回-1 
    	for(i=0;i<g.n;i++)
    	{
    		if(g.edges[v][i]>0 && g.edges[v][i]<INF)
    			d1++;       //统计第v行既不为0也不为∞的边数即出度 
    	}
    	for(i=0;i<g.n;i++)
    	{
    		if(g.edges[i][v]>0 && g.edges[i][v]<INF)
    			d2++;       //统计第v列既不为0也不为∞的边数即入度 
    	}
    	d=d1+d2;
    	return d;
    }
    

    五. 邻接表的相关算法

    建立图的邻接表算法

    基本思路:
    先创建邻接表头结点数组,并置所有头结点的firstarc为NULL。
    遍历邻接矩阵数组A,当A[i][j]不等0且不等∞时,说明有一条从 i 到 j 的边,建立一个结点p,并置其adjvex域为j,其weight域为A[i][j],将p结点插入到顶点i的单链表头部

    void CreateGraph(ALGraph *&G, int A[][MAXVEX],int n, int e)
    {
    	int i,j;
    	ArcNode *p;
    	G=(ALGraph *)malloc(sizeof(ALGraph));
    	G->n=n;
    	G->e=e;
    	for(i=0;i<G->n;i++)    //邻接表中所有头结点的指针域置空 
    		G->adjlist[i].firstarc=NULL;
    	for(i=0;i<G->n;i++)    //检查A中每个元素 
    	{
    		for(j=G->n-1;j>=0;j--)
    		{
    			if(A[i][j]>0 && A[i][j]<INF)//存在一条边 
    			{
    				p=(ArcNode *)malloc(sizeof(ArcNode))//创建结点p 
    				p->adjvex=j;
    				p->weight=A[i][j];
    				p->nextarc=G->adjlist.firstarc;  //头插法插入p 
    				G->adhlist.firstarc=p;
    			}
    		}
    	}
    }
    

    求无向图顶定度算法

    int Degree(ALGraph *G, int v)
    {
    	int d=0;
    	ArcNode *p;
    	if(v<0 || v>=G->n)
    		return -1;      //顶点编号错误返回-1 
    	p=G->adjlist.firstarc; 
    	while(p!=NULL)//统计v顶点的单链表中边结点个数即度
    	{
    		d++; 
    		p=p->nextarc;
    	}
    	return d;
    }
    

    求有向图顶点度算法

    int Degree(ALGraph *G, int v)
    {
    	int i,d1=0,d2=0,d;
    	ArcNode *p;
    	if(v<0 || v>=G->n)
    		return -1;      //顶点编号错误返回-1 
    	p=G->adjlist.firstarc; 
    	while(p!=NULL)//统计v顶点的单链表中边结点个数即出度
    	{
    		d1++; 
    		p=p->nextarc;
    	}
    	for(i=0;i<G->n;i++)//统计边结点中adjvex为v的个数即入度
    	{
    		p=G->adjlist.firstarc; 
    		while(p!=NULL)
    		{
    			d2++; 
    			p=p->nextarc;
    		}
    	}
    	d=d1+d2;
    	return d;
    }
    
    展开全文
  • #include<iostream> #include<queue> #include<string.h> using namespace std; typedef struct ArcNode { int adjvex; struct ArcNode* nextArc;...typedef struct VNod...

    在这里插入图片描述

    #include<iostream>
    #include<queue>
    #include<string.h>
    using namespace std;
    
    typedef struct ArcNode {
    
        int adjvex;
    	struct ArcNode* nextArc;
    
    }ArcNode;	//边节点
    
    typedef struct VNode {
    
    	int data;
    	int inDegree, outDegree;
    	ArcNode* firstArc;
    
    }VNode, * AdjList;
    
    typedef struct {
    
    	int vNum, arcNum;
    	AdjList vertices;
    
    }ALGraph;
    
    int LocateVNode(ALGraph g, int index) {
    	int flag = 0;
    
    	for (int i = 0; i < g.vNum; i++) {
    		if (g.vertices[i].data==index) {
    			flag = 1;
    			return i;
    		}
    	}
    
    	if (flag == 0) {
    		return -1;//查找失败
    	}
    }
    
    int CreateUDG(ALGraph& g) {
    
    	cin >> g.vNum >> g.arcNum;
    	g.vertices = new VNode[g.vNum];
    
    	for (int i = 0; i < g.vNum; i++) {
    		cin >> g.vertices[i].data;
    		g.vertices[i].firstArc = NULL;
    	}
    
    	for (int i = 0; i < g.arcNum; i++) {
    
    		int v1, v2;
    		cin >> v1 >> v2;
    		v1 = LocateVNode(g, v1);
    		v2 = LocateVNode(g, v2);
    
    		ArcNode* p1 = new ArcNode;
    		p1->adjvex = v2 + 1;
    		p1->nextArc = g.vertices[v1].firstArc;
    		g.vertices[v1].firstArc = p1;
    		
    		ArcNode* p2 = new ArcNode;
    		p2->adjvex = v1 + 1;
    		p2->nextArc = g.vertices[v2].firstArc;
    		g.vertices[v2].firstArc = p2;
    		
    	}
    	return 1;
    }
    int CreateDG(ALGraph& g) {
    
    	cin >> g.vNum >> g.arcNum;
    	g.vertices = new VNode[g.vNum];
    
    	for (int i = 0; i < g.vNum; i++) {
    		cin >> g.vertices[i].data;
    		g.vertices[i].firstArc = NULL;
    		g.vertices[i].inDegree = 0;
    		g.vertices[i].outDegree = 0;
    	}
    
    	for (int i = 0; i < g.arcNum; i++) {
    
    		int v1, v2;
    		cin >> v1 >> v2;
    		v1 = LocateVNode(g, v1);
    		v2 = LocateVNode(g, v2);
    		g.vertices[v2].inDegree++;
    		g.vertices[v1].outDegree++;
    		ArcNode* p1 = new ArcNode;
    		p1->adjvex = v2 + 1;
    		p1->nextArc = g.vertices[v1].firstArc;
    		g.vertices[v1].firstArc = p1;
    		
    		
    	}
    	return 1;
    }
    
    void OutputDegree(ALGraph g) {
    
    	for (int i = 0; i < g.vNum; i++) {
    
    		cout << g.vertices[i].data << ":";
    		cout << g.vertices[i].inDegree << " ";
    		cout << g.vertices[i].outDegree << " ";
    		cout << g.vertices[i].outDegree + g.vertices[i].inDegree << "\n";
    
    	}
    }
    
    void OutputDGraph(ALGraph g) {
    
    	for (int i = 0; i < g.vNum; i++) {
    
    		cout << g.vertices[i].data << ":";
    		ArcNode* p = g.vertices[i].firstArc;
    		while (p) {
    			cout << p->adjvex << " ";
    			p = p->nextArc;
    		}
    		cout << endl;
    
    	}
    
    }
    
    void WidthTraverseGraph(ALGraph g) {
    
    	queue<int> TraverseList;
    	int visited[1000];
    	memset(visited, 0, sizeof(visited));
    
    	cout << "v" << g.vertices->data << " ";
    	visited[0] = true;
    	TraverseList.push(g.vertices->data);
    
    	while (!TraverseList.empty()) {
    
    		int u = TraverseList.front();
    		TraverseList.pop();
    
    		ArcNode* p = g.vertices[LocateVNode(g,u)].firstArc;
    
    		while (p != NULL) {
    			if (!visited[LocateVNode(g, p->adjvex)]) {
    
    				cout << "v" << p->adjvex << " ";
    				visited[LocateVNode(g, p->adjvex)] = true;
    				TraverseList.push(p->adjvex);
    
    			}
    			p = p->nextArc;
    		}
    	}
    }
    int visited[1000];
    void Depth_TG(ALGraph g, int v);
    
    void DepthTraverseGraph(ALGraph g) {
    	
    	memset(visited, 0, sizeof(visited));
    	for (int i = 0; i < g.vNum; i++) {
    		if (visited[i] == 0) {
    			Depth_TG(g, i);
    		}
    	}
    	
    }
    
    void Depth_TG(ALGraph g,int v) {
    	cout << g.vertices[v].data << " ";
    	visited[v] = true;
    	ArcNode* p = g.vertices[v].firstArc;
    	while (p) {
    		int w = LocateVNode(g, p->adjvex);
    		if (!visited[w]) {
    			Depth_TG(g, w);
    		}
    		p = p->nextArc;
    	}
    }
    
    int main() {
    
    	ALGraph g;
    	CreateDG(g);
    
    	OutputDegree(g);
    
    	return 0;
    }
    
    展开全文
  • Kahn算法出入度一般指是在有向图(DAG)中,某个顶点,箭头指向它入度,从这个顶点出发,指向别顶点边就是出度。有几条这样边,度就是多大。可以参考【1】中生成出入度代码。不过【1】中是认为无向图...
  • 2.求有向图的入度,出度,度 3.输出图(图遍历) (注:图创建时,直接输入字符和定点之间关系) #include &amp;amp;amp;lt;iostream&amp;amp;amp;gt; #include &amp;amp;amp;lt;stdio.h&amp;amp;...
  • 首先我们回想一下邻接表,对于有向图的邻接表,由于对于顶点出度的入度分别储存在邻接表和逆邻接表中,对于频繁访问出度的入度的算法很不方便,于是前辈们将邻接表和逆邻接表结合在一起,组成了十字链表,就可以方便...
  • 邻接表

    2019-01-26 19:58:00
    邻接表存储有向图,并输出各顶点的出度入度 题目来源图论算法 例1.3 首先我们需要定义一些结构体,其用法在注释中使用# define maxn 100 struct ArcNode{ int adjvex; //有向边的另一个邻接点的序号 ArcNode *...
  • 15. 假设不带权有向图采用邻接表G存储,设计实现以下功能的算法。 (1) 求出图中每个顶点的入度。 (2)求出图中每个顶点的出度。 (3)求出图中出度为0的顶点数。 #include #include #de
  • 十字链表是邻接表和逆邻接表的组合,是对有向图的优化存储结构,容易求得顶点的出度入度。除了结构复杂外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图的应用中,十字链表也是非常好的数据结构...
  • 实验内容 1、假设不带权有向图采用邻接矩阵g存储,设计实现以下功能的算法: (1)求出图中每个顶点的入度。 (2)求出图中每个顶点的出度。...3、假设一个连通图采用邻接表作为存储结构,试设计一个算法,判断其...
  • 1、首先生成入度表flag,因为(u,v)u表示终点,prerequisites[0]是u,需要找到入度为0那个顶点,将这个flag推入队列queue。 2、当queue非空时候,不断转这个队列弹出元素cur作为当前顶点,课程numCourses–,...
  • 对于有向图来说,邻接表是有缺陷,关心了出度问题,想了解入度就必须要遍历整个图才能知道,反之,逆邻接表解决了入度的情况。 把邻接表与逆邻接表结合起来,即有向图一种存储方法十字链表(Orthogonal List)。 ...
  • 反之,逆邻接表解决了入度,却不了解出度的情况。有没有可能把邻接表和逆邻接表结合起来呢? 答案是肯定,就是把它们整合在一起。这种存储有向图方法是:十字链表(Orthogonal List). 我们重新定义顶点表结点...
  • 常见算法

    2018-11-06 22:46:53
    图是由一系列点和边集合构成,一般有邻接矩阵和邻接表两种表示方式,c/c++可以看我这篇文章:搜索(1) 这篇文章主要讲java语言中图相关算法。首先看一下图结构代码: class Node {//点集 public int value...
  • 算法导论复习笔记 Chapter22 基本图算法 22.1-1 有向图邻接链表计算节点出度入度的时间复杂度 O(V+E) 开一个 degree[] 数组大小为结点个数复杂度 O(V; 遍历邻接链表经过边 uv 时计算出度 degree[u]+=1, 计算入度 ...
  • 算法导论复习笔记 Chapter22 基本图算法 22.1-1 有向图邻接链表计算节点出度入度的时间复杂度 O(V+E) 开一个 degree[] 数组大小为结点个数复杂度 O(V; 遍历邻接链表经过边 uv 时计算出度 degree[u]+=1, 计算入度 ...
  • 算法导论复习笔记 Chapter22 基本图算法 -1 有向图邻接链表计算节点出度入度的时间复杂度 O(V+E) 开一个 degree[] 数组大小为结点个数复杂度 O(V; 遍历邻接链表经过边 uv 时计算出度 degree[u]+=1, 计算入度 ...
  • 22.1-1给定一个有向图的邻接表表示,计算该图中每个顶点的出度需要多少时间?计算每个顶点的入度需要多少时间? 计算出度和入度的时间都为O(v+e),计算出度和入度的过程相当于将邻接链表的顶点和边遍历一遍。 ...
  •   说通俗点,十字链表也就是邻接表的改进,顶点集包含两个指针,firstIn和firstOut, firstIn指向入边表(逆邻接表), firstOut表示出边表(也就是邻接表)。(需要先理解上面代码中顶点集...
  • PTA算法 图练习题改错

    2021-05-21 11:04:17
    原因:有向图邻接表出度必定有入度 定点必然守恒 ,定点数一定相等 有n-1条边图肯定都是生成树。 T OR F 答案:错误 原因:非连通图无法构成树 无向图邻接矩阵可用一维数组存储。 T OR F 答案:正确 原因: 二维...
  • 给定有向图的邻接链表,多少时间才能算出每个结点的出度入度? 计算出度: ①为了计算一个结点的出度,我们需要枚举v结点所有的边,O(出度(v))。②然后遍历每个结点计算出度,耗费时间为O(|E| + |V|),这里的|...
  • 存储结构相邻矩阵有向图相邻矩阵无向图相邻矩阵邻接表无向图的邻接表表示带权图的邻接表表示有向图的邻接表(出边表)有向图邻接表(入边表)十字链表3. 图遍历深度优先遍历(depth-first search)...
  • day07 图 特点 一组顶点V(vertex) 一组边E(edge):顶点之间的连线,可以无向,有向。a—b 无 ,a->b有向。 简单路径:不包含重复顶点。...邻接表的出度:指向别人的数量;入度:别人指向自己的数量。 ...
  • 尽管邻接表的存储方式比较节省存储空间,但链表不方便查找,所以查询效率没有邻接矩阵存储方式高。针对这个问题,邻接表还有改进升级版,即将链表换成更加高效的动态数据结构,比如平衡二叉查找树、跳表、散列表等。
  • 2.图存储(邻接矩阵和邻接表) 3.图遍历(DFS和BFD) 4.最短路径算法 5.拓扑排序 非重点考点: 1.关键路径 2.最短路径中Bellman-Ford和SPFA 甲级考纲以外考点: 最小生成树算法 一、图定义和相关术语 只列...
  • 这题比较裸,根据牛膜拜情况建图,然后强连通分量处理,处理后再建新图,记录出度入度,找出所有出度为0,如果有2个及以上,则输出(0),很简单,不可能有被所有牛膜拜牛了(因为这几个结点互相不可达)。...
  • 算法导论22.1图表示 练习总结

    千次阅读 2015-11-03 18:36:04
    22.1-1 给定有向图的邻接链表,需要多长时间才能计算出每个结点的出度(发出的边的条数)?多长时间才能计算出每个结点的入度(进入的边的条数)? ANSWER:① 出度:O(V+E),因为计算 n 个结点的链表长度为 O(n),...
  • 《数据结构与算法A》实验4:二叉树基本操作实现 ...说明:有向图中顶点度数为该顶点入度出度之和。 Input 本题目包含多组测试数据。 输入数据第一行是一个正整数Y(Y=1表示接下来输入...

空空如也

空空如也

1 2 3 4
收藏数 79
精华内容 31
关键字:

邻接表的出度入度算法