精华内容
下载资源
问答
  • 数据结构 有向图
    万次阅读 多人点赞
    2018-12-24 00:33:27

    一、邻接矩阵实现

    假设不带权有向图采用邻接矩阵 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;
    
    }

     

    更多相关内容
  • 数据结构 有向图与邻接矩阵

    千次阅读 2019-12-18 11:44:13
    数据结构 有向图与邻接矩阵 在邻接矩阵中,每一个元素表示行对应的顶点与列对应的定点之间是否有弧(1有,0没有)

    数据结构 有向图与邻接矩阵

     

    在邻接矩阵中,每一个元素表示行对应的顶点与列对应的定点之间是否有弧(1有,0没有)

    展开全文
  • 对任意一个有向图完成如下操作: 建立邻接链表 计算任意顶点的出度和入度 根据邻接表建立逆邻接表 遍历并输出经过的边。
  • 数据结构——(邻接链表)

    万次阅读 多人点赞 2019-07-21 21:20:44
    比如说,如果我们要处理下图这样的稀疏有向图,邻接矩阵中除了arc[1][0]有权值外,没有其他弧,其实这些存储空间都浪费掉了。 因此选择一种新的数据结构来存储这种稀疏图则尤为重要了。此时则使用链表结构来存储...

    邻接链表

    邻接矩阵是不错的⼀种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构是存在对存储空间的极大浪费的。比如说,如果我们要处理下图这样的稀疏有向图,邻接矩阵中除了arc[1][0]有权值外,没有其他弧,其实这些存储空间都浪费掉了。
    在这里插入图片描述
    因此选择一种新的数据结构来存储这种稀疏图则尤为重要了。此时则使用链表结构来存储原来的连接信息。
    在这里插入图片描述

    定义如下数据结构

    //图的邻接链表存储结构
    
    //边表节点结构,一个adjvex用来存储邻接点的位置,一个next指针用来指向下一个节点
    typedef struct EdgeNode
    {
    	int adjvex;  //存储顶点下标信息
    	struct EdgeNode *next;
    } EdgeNode;
    
    //顶点表节点结构
    typedef struct
    {
    	string Vexs;  //用来存储顶点信息
    	EdgeNode *firstedge;  //用来存储当前顶点的下一个顶点
    } VexList;
    
    //这里用动态数组存储顶点表,然后numVertex,numEdge是一个图的顶点数和边数
    typedef struct
    {
    	vector<VexList> VexList;
    	int Vertexs, Edges;
    } GraphList;
    

    创建图

    此处创建边表使用的方法是尾插法,《大话数据结构》中使用的是头插法,个人感觉尾插法比较容易理解。其他的方面和邻接矩阵创建图时的思路基本一样。

    void CreateGraph(GraphList * G)
    {
    	string v1, v2;
    	EdgeNode * e, *p, *q;
    	cout << "请输入顶点数和边数:" << endl;
    	cin >> G->Vertexs >> G->Edges;
    	cout << "请输入顶点的信息:" << endl;
    	for (int i = 0; i < G->Vertexs; ++i){
    		VexList tmp;
    		cin >> tmp.Vexs;
    		tmp.firstedge = NULL;
    		G->VexList.push_back(tmp);
    	}
    	for (int k = 0; k < G->Edges; ++k){
    		int i, j;//(Vi,Vj)
    		cout << "请输入边(Vi,Vj):" << endl;
    		cin >> i >> j;
    		if (G->VexList[i].firstedge == NULL){//当前顶点i后面没有顶点
    			e = new EdgeNode;
    			e->adjvex = j;
    			e->next = NULL;
    			G->VexList[i].firstedge = e;
    		}
    		else{  //当前i后面有顶点
    			EdgeNode *p = G->VexList[i].firstedge;
    			while (p->next){
    				p = p->next;
    			}
    			e = new EdgeNode;
    			e->adjvex = j;
    			e->next = NULL;
    			p->next = e;
    		}
    		//因为是无向图,所以(Vi,Vj)与(Vj,Vi)都要连接起来
    		if (G->VexList[j].firstedge == NULL){ //当前顶点j后面没有顶点
    			e = new EdgeNode;
    			e->adjvex = i;
    			e->next = NULL;
    			G->VexList[j].firstedge = e;
    		}
    		else{  //当前j后面有顶点
    			EdgeNode *p = G->VexList[j].firstedge;
    			while (p->next){
    				p = p->next;
    			}
    			e = new EdgeNode;
    			e->adjvex = i;
    			e->next = NULL;
    			p->next = e;
    		}
    	}
    }
    

    同样也写了一个打印图的函数。

    //打印连接链表
    void PrintGraph(GraphList *G)
    {
    	cout << "所建立的邻接表如以下所示:" << endl;
    	for (int i = 0; i<G->Vertexs; i++){
    		cout << G->VexList[i].Vexs;             //先输出顶点信息
    		EdgeNode * e = G->VexList[i].firstedge;
    		while (e){                           //然后就开始遍历输出每个边表所存储的邻接点的下标
    			cout << "-->" << e->adjvex;
    			e = e->next;
    		}
    		cout << endl;
    	}
    }
    

    此时也需要一个全局访问数组

    bool Visited_List[100];
    

    深度优先遍历(DFS)

    与基于邻接矩阵的DFS基本无差别,废话不都说,直接上代码。

    //DFS
    void DFS(GraphList *G, int i)
    {
    
    	EdgeNode * p;
    	Visited_List[i] = true;
    	cout << G->VexList[i].Vexs << "  ";
    	p = G->VexList[i].firstedge;
    	while (p){
    		if (!Visited_List[p->adjvex])
    			DFS(G, p->adjvex);
    		p = p->next;
    	}	
    }
    
    void DFSTraver(GraphList *G)
    {
    	cout << "深度优先遍历顺序:" << endl;
    	for (int i = 0; i<G->Vertexs; ++i)
    		Visited_List[i] = false;
    	for (int i = 0; i<G->Vertexs; ++i){
    		if (!Visited_List[i])
    			DFS(G, i);
    	}
    	cout << endl;
    }
    

    广度优先遍历(BFS)

    此处的思路和邻接矩阵的基本一样,就是边表的遍历此时是用链表的方式遍历。

    //BFS  特点要使用队列,很像树的层序遍历
    void BFSTraver(GraphList *G)
    {
    	cout << "广度优先遍历顺序:" << endl;
    	EdgeNode * p;
    	queue<int> Q;
    	for (int i = 0; i<G->Vertexs; ++i)
    		Visited_List[i] = false;
    	for (int i = 0; i<G->Vertexs; ++i){
    		if (!Visited_List[i]){
    			Visited_List[i] = true;
    			cout << G->VexList[i].Vexs << "  ";
    			Q.push(i);
    			while (!Q.empty()){
    				i = Q.front();
    				Q.pop();
    				p = G->VexList[i].firstedge;
    				while (p){//把当前顶点下相连接的点找完
    					if (!Visited_List[p->adjvex]){
    						Visited_List[p->adjvex] = true;
    						cout << G->VexList[p->adjvex].Vexs << "  ";
    						Q.push(p->adjvex);
    					}
    					p = p->next;
    				}
    			}
    		}
    	}
    }
    

    测试一下

    emmmm ,又到了测试的时候了。。。采取同样的测试数据,输入如下图的数据。
    在这里插入图片描述
    结果:
    在这里插入图片描述
    over!!!
    参考了一下前人的工作

    展开全文
  • 二:有向图 1.定义 2.图形化解释 3.结合​表达式介绍 有向图和无向图区别: 三:简单图 1.定义 2.图形化解释 四:完全无向图 1.定义 2.图形化解释 五:有向完全图 1.定义 2.图形化解释 一:无向图 1....

    目录:

    一:无向图

    1.定义

    2.图形化解释

    3.结合​表达式介绍

    二:有向图

    1.定义

    2.图形化解释

    3.结合​表达式介绍

    有向图和无向图区别: 

    三:简单图

    1.定义

    2.图形化解释

    四:完全无向图

    1.定义

    2.图形化解释

    五: 有向完全图

    1.定义

    2.图形化解释


    一:无向图

    1.定义

    若顶点 之间的边没有方向,则称这条边为 无向边(Edge)

    用无序偶对 表示

    如果图中任意两个顶点之间的边都是无向边,则称该图为 无向图

     

    无向图顶点的边数叫做 度

    2.图形化解释

    下图所示即为无向图:

    3.结合表达式介绍

    由于无向图是无方向的,连接顶点的边

    可以表示成无序对

    也可以写成

    对于上图中的无向图 来说

    其中顶点集合

    边集合

     

    二:有向图

    1.定义

    若从顶点  到  的边有方向,则称这条边为 有向边,也称为 弧(Arc)

    用有序偶 来表示称为弧尾(Tail),称为弧头(Head)

    如果图中任意两个顶点之间的边都是有向边,则称该图为 有向图(Directed graphs)

     

    有向图顶点分为 入度(箭头朝自己) 和 出度(箭头朝外)

    2.图形化解释

    如下图所示即为一个有向图:

    3.结合表达式介绍

    连接到顶点的有向边就是

    弧尾

     是弧头

    表示弧,注意不能写成

     

    对于上图的有向图

    其中顶点集合 

    弧集合 

    有向图和无向图区别: 

    :看清楚了,无向边用小括号表示

    有向边则是使用尖括号表示

     

    三:简单图

    1.定义

    在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图

    2.图形化解释

    如下所示的两个图就不属于简单图:

     

    四:完全无向图

    1.定义

    在无向图中,如果任意两个顶点之间都存在边,则称该图为 无向完全图

    2.图形化解释

    如下图所示即为一个无向完全图:

     

    五: 有向完全图

    1.定义

    在有向图中,如果任意两个顶点之间都存在 方向互为相反 的两条弧,则称该图为 有向完全图

    2.图形化解释

    如下图所示即为一个有向完全图:

     

    展开全文
  • 本题要求实现一个函数,输出有向图每个顶点的数据元素的值,以及每个顶点的出度的值。 函数接口定义: 函数接口为: void outdegree(MGraph G); G为采用邻接矩阵作为存储结构有向图。 裁判测试程序样例: #...
  • 有向图

    千次阅读 2018-10-30 11:25:35
    有向图 1、术语 在有向图中,边是单向的。每条边所连接的两个顶点都是一个有序对,他们的邻接性是单向的。 出度:该顶点指出的边的总数 入度:指向该顶点的边的总数 一条有向边的第一个顶点称为它的头,第二个...
  • 前面我们把树的知识全部学完了,今天我们学习,如果不算算法,是是我们最后一种要学的“数据结构”,是一种非线性数据结构,它比树状结构更复杂,前面我们学习的知识都是一对一或者一对多的关系,今天要学的是...
  • 数据结构的基本概念

    千次阅读 2022-03-16 17:32:55
    有向图2.1 有向完全图2.2 强连通图(有向图)2.3 有向图的度2. 稀疏图和稠密图3. 有环图和无环图4. 加权图和无权图三、图的存储结构1. 邻接矩阵2. 邻接表参考链接 一、什么是图? 图是一种非线性的数据结构,表示多...
  • 数据结构——的概述

    万次阅读 多人点赞 2019-05-15 11:43:25
    基本术语 图G=(V,E)G=(V,E)G=(V,E)由顶点(vertex)的集V和边(edge)的集E组成。 边:每一条边就是一副点对(v,w),有时也称为弧 有向图:边是有方向的图
  • Java数据结构与算法——

    千次阅读 2022-03-21 17:53:19
    1.关于这种数据结构 为什么要有图? 前面我们学了线性表和树,线性表局限于一个直接前驱和一个直接后继的关系,树也只能一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了...
  • 数据结构-无向图

    万次阅读 多人点赞 2018-08-05 16:51:41
    1.的定义  (Graph)是由顶点(vertex)的有穷非空集合和顶点之间边(edge)的集合组成,通常表示为:G(V,E),其中,G表示一个,...若顶点之间 Vi 和 Vj 之间有方向,则为有向边(也称弧),用有序偶对&lt; Vi ,...
  • 的定义:是由顶点的穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E)。 其中:G表示一个,V是G中顶点的集合,E是G中边的集合。 注意:1、线性表中我们把数据元素称为元素;树中将数据元素称为...
  • 文章目录有向无环图拓扑排序AOV-网AOE-网关键路径的概念事件的最早/晚...将这些子工程之间的先后关系用有向图表示,其中顶点表示活动,有向边表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网。
  • 数据结构)连通

    千次阅读 2022-04-02 21:20:32
    图存储结构分类之连通图 连通:图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的 图 1 顶点之间的连通状态示意图 ...连通分量:若无向图不是连通图,但图中存储某...
  • 数据结构(Graph)【详解】

    万次阅读 多人点赞 2021-02-26 17:03:48
    【知识框架】 【考纲内容】 的基本概念 的存储及基本操作 邻接矩阵法;邻接表法;邻接多重表;...的遍历 ...的基本应用 ...的基本概念 在线性表中,数据元素之间是被串...是一种较线性表和树更加复杂的数据结构
  • 来个小例子(无向图): 图1 上图邻接表的结构: 邻接表用链表来存储邻接点(分两个域,一个存顶点下标,一个存下一个邻接点的引用),通过一个类(我用了内部类,所以是private)定义邻接点: private class ...
  • Dijkstra从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题 时间复杂度o(n^2) 用Dijkstra算法找出以A为起点的单源最短路径步骤如下,从最短路径开始找,而不是当前路径开始找。 ...
  • 有向图和无向图的相关概念

    万次阅读 2020-04-29 15:44:42
    图的定义:  图在数据结构中是中一对多的关系,一般分为无向图与无向图  常用 邻接矩阵 或者 邻接链表 来...对于图7-1所示的无向图G1和有向图G2,它们的数据结构可以描述为:  G1=(V1,E1), 其中 V1={a,b,c,d...
  • 【图结构专题】有向图

    万次阅读 2018-03-19 22:00:26
    有向图 一. 有向图的相关术语 在有向图中,边是单向的:每条边连接的两个顶点都是一个有序对,它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图:比如任务調度的依赖关系,社交网络的任务关系等等...
  • 数据结构有向无环的表示

    千次阅读 2017-02-10 11:22:31
    数据结构有向无环的表示最近在做workflow的时候有用到怎么去存储一个有向无环,在百度上看到一个答复感觉很棒 http://blog.chinaunix.net/uid-24774106-id-3505579.html文中使用先是 malloc 一个内存然后每当...
  • 数据结构---的详细介绍

    万次阅读 多人点赞 2017-02-27 15:55:30
    前言: In order to change we ...(Graph)是由顶点的穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个,V是G中顶点的集合,E是G中边的集合。在中的数据元素,我们称之为顶
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    常用的数据结构有:数组,栈,链表,队列,树,,堆,散列表等,如所示: 每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。 1、数组 数组是可以再内存中连续存储多个元素的...
  • 图5——判断有向图中是否存在回路

    万次阅读 多人点赞 2019-06-22 09:32:13
    假设以邻接矩阵作为图的结构,编写算法,判别在给定的有向图中是否存在一个简单的有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)(注意:图中不存在顶点到自身的弧) 这是清华大学的考研试题。...
  • 有向图和无向图以及拓扑的复习

    万次阅读 2018-10-14 17:43:36
    1)关于有向图,百科中是这样描述的:一个有向图D是指一个有序三元组(V(D),A(D),ψD),其中ψD为关联函数,它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。 理解:如图D,...
  • 数据结构的基本介绍

    万次阅读 2020-06-29 14:37:32
    图的基本介绍 线性表局限于一个直接前驱和一个直接后继的关系,树也只能一个直接前驱也就是父节点。当我们需要表示多对多的关系时,就需要用到图...比如下面的无向图中,从顶点D到顶点C的路径: D->B->C D-&
  • 数据结构:八种数据结构大全

    万次阅读 多人点赞 2021-07-29 12:36:10
    常用的数据结构有:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、(Graph)、堆(Heap)、散列表(Hash)等; 1.2 数据结构的分类 1.2.1 排列方式 1)集合 集合:数据结构中的...
  • 数据结构结构的实现

    万次阅读 多人点赞 2018-02-07 19:44:45
    是一种很重要的数据结构,不解释。
  • 有向无环图是一个无环的有向图, 是描述一项工程或系统的进行过程的有效工具。几乎所有的工程都可分为若干个称做活动的子工程。 有两种常用的活动网络  1. AOV网(Activity On Vertices)——用顶点表示活动的...
  • 数据结构 简要 的结构类似与树,都是一个又一个结点(顶点)连接而成,如下: 因此树其实也是一种特殊的结构,树的每个节点只能一个入度,而可以多个,的知识点在这里解不讲解了,例如弧,入度,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 955,499
精华内容 382,199
关键字:

数据结构 有向图

数据结构 订阅
友情链接: ex_read_nc1.zip