精华内容
下载资源
问答
  • G为采用邻接矩阵作为存储结构有向图。 裁判测试程序样例: #include <stdio.h> #define MVNum 100 //最大顶点数 typedef struct{ char vexs[MVNum]; //存放顶点的一维数组 int arcs[MVNu

    本题要求实现一个函数,输出有向图每个顶点的数据元素的值,以及每个顶点的出度的值。

    函数接口定义:
    函数接口为:

    void outdegree(MGraph G);
    

    G为采用邻接矩阵作为存储结构的有向图。

    裁判测试程序样例:

    #include <stdio.h>
    #define MVNum 100                 //最大顶点数 
    typedef struct{ 
      char vexs[MVNum];           //存放顶点的一维数组 
      int arcs[MVNum][MVNum];     //邻接矩阵 
      int vexnum,arcnum;          //图的当前顶点数和弧数 
    }MGraph; 
    void outdegree(MGraph G);
    void CreatMGraph(MGraph *G);/* 创建图 */
    int main()
    {
    	MGraph G;
    	CreatMGraph(&G);
    	outdegree(G);
    	return 0;
    }
    void CreatMGraph(MGraph *G)
    {
    	int i,j,k;
    	scanf("%d%d",&G->vexnum,&G->arcnum);
    	getchar();
    	for(i=0;i<G->vexnum;i++)
    	   scanf("%c",&G->vexs[i]);
    	for(i=0;i<G->vexnum;i++)
    	   for(j=0;j<G->vexnum;j++)
    		G->arcs[i][j]=0;
    	for(k=0;k<G->arcnum;k++)
    	{  
    	   scanf("%d%d",&i,&j);     
               G->arcs[i][j]=1;    
    	}
    }
    
    /* 请在这里填写答案 */
    

    输入样例:
    例如有向图

    有向图.png

    第一行给出图的顶点数n和弧数e。第二行给出n个字符,表示n个顶点的数据元素的值。后面是e行,给出每一条弧的两个顶点编号。

    4 5
    ABCD
    1 0
    2 0
    2 1
    3 2
    3 1
    

    输出样例:
    输出n个顶点的元素值,顶点的数据类型为字符型。以及各顶点的出度值

    A:0
    B:1
    C:2
    D:2
    

    我的答案

    void outdegree(MGraph G) 
    {
    	for(int i = 0; i < G.vexnum; i++) 
        {
    		int c = 0;
    		for(int j = 0; j < G.vexnum; j++)
    			if(G.arcs[i][j] == 1)
    				c++;
    		printf("%c:%d\n",G.vexs[i],c);
    	}
    }
    
    
    展开全文
  • 有向图存储

    千次阅读 2016-09-16 22:15:42
    数据结构有向图存储

    方法一:用邻接表的方法存储,

    先开辟一块大小为n的存储空间,每一块存储空间为一个链表的开头,一次将数据增加到相应的链表里。

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Node
    {
    	int data;
    	Node *next;
    }Node;
    void show(Node &LJB,int number);
    int main()
    {
    	printf("输入顶点数量\n");
    	int number;
    	scanf("%d",&number);
    	printf("请输入连着的顶点a.b,ab同时为0时输入结束\n");
    	int a,b;
    	scanf("%d %d",&a,&b);
    	
    	//创建邻接表
    	Node LJB;
    	LJB.next=(Node *)malloc((number+1)*sizeof(Node));
    	Node *p[number];
    	p[1]=LJB.next;
    	for(int i=1;i<=number;i++)
    	{
    		p[i]=LJB.next+i;
    		p[i]->next=NULL;
    		p[i]->data=i;
    	}
    	while(!(a==0&&b==0))
    	{
    		p[a]->next=(Node *)malloc(sizeof(Node));
    		p[a]=p[a]->next;
    		p[a]->data=b;
    		p[a]->next=NULL;
    		scanf("%d %d",&a,&b);
    	} 
    	for(int i=1;i<=number;i++)
    	{
    		p[i]=LJB.next+i;
    	}
    	int j=1;
    	printf("打印邻接表\n");
    	for(j=1;j<=number;j++)
    	{
    		while(p[j])
    		{
    			printf("%d->",p[j]->data);
    			p[j]=p[j]->next;
    		}
        	printf("\n");
        }
    	return 0;
    }
    
    


    方法二:用邻接矩阵的方法存储,

    开辟一个矩阵,在相接的两个点对应的序号的位置存储为1,其余为0,例如:矩阵a[100][100],1和2相连,则a[1][2]=0


    #include<stdio.h>
    #define size 100 //矩阵大小 
    void jz(int m[size][size],int a,int b);
    void show(int m[size][size],int number);
    int main()
    {
    	int m[size][size];
    	printf("输入顶点数量\n");
    	int number;
    	scanf("%d",&number);
    	int a,b;
    	printf("请输入连着的顶点a.b,ab同时为0时输入结束\n");
    	scanf("%d %d",&a,&b);
    	while(!(a==0&&b==0))
    	{
    		jz(m,a,b);
    		scanf("%d %d",&a,&b);
    	} 
    	show(m,number);
    	return 0;
    	
    }
    void jz(int m[size][size],int a,int b)
    {
    	m[a][b]=1;
    }
    
    void show(int m[size][size],int number)
    {
    	int i,j;
    	for(i=1;i<number;i++)
    	{
    		for(j=1;j<number;j++)
    		{
    			printf("%d ",m[i][j]);
    		}
    		printf("\n");
    	}
    }


    展开全文
  • 前面实现了链表和树,现在看看图。 链表是一对一的对应关系; 树是一对多的对应关系; 图是多对多的对应关系。 图一般有两种存储方式,邻接表和邻接矩阵。...因此,有向图邻接表的空间复杂度为O(v+e),无向图加倍。
    前面实现了链表和树,现在看看图。
    
    链表是一对一的对应关系;
    树是一对多的对应关系;
    图是多对多的对应关系。


    图一般有两种存储方式,邻接表和邻接矩阵。


    先看邻接表。
    邻接表就是将图中所有的点用一个数组存储起来,并将此作为一个链表的头,
    链表中保存跟这个点相邻的点(边点),如果有权值,则在边点中增加一权值字段。

    因此,有向图邻接表的空间复杂度为O(v+e),无向图加倍。


    C++实现代码如下:
    // GraphList.h
    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    // 边
    struct Edge{
    	int vName;
    	int weight;
    	struct Edge* next;
    };
    
    // 顶点(链表头)
    struct Vertex{
    	int vName;
    	struct Edge* next;
    };
    
    // 有向图
    class GraphList
    {
    public:
    	~GraphList();
    
    	void createGraph();
    	void printGraph();
    
    private:
    	// 1. 输入定点数
    	void inputVertexCount();
    	// 2. 生成定点数组
    	void makeVertexArray();
    	// 3. 输入边数
    	void inputEdgeCount();
    	// 4. 输入边的起始点
    	void inputEdgeInfo();
    	// 5. 添加边节点至对应的链表中
    	void addEdgeToList(int vFrom, int weight, int vTo);
    private:
    	int m_vCount;
    	int m_eCount;
    	Vertex* m_vVertex;
    };
    
    GraphList::~GraphList(){
    	for (int i = 0; i < m_vCount; ++i){
    		Edge* tmp = m_vVertex[i].next;
    		Edge* edge = NULL;
    		while(tmp){
    			edge = tmp;
    			tmp = tmp->next;
    			delete edge;
    			edge = NULL;
    		}
    	}
    	delete[] m_vVertex;
    }
    
    void GraphList::inputVertexCount()
    {
    	cout << "please input count of vertex:";
    	cin >> m_vCount;
    }
    
    void GraphList::makeVertexArray()
    {
    	m_vVertex = new Vertex[m_vCount];
    	// 初始化
    	for (int i = 0; i < m_vCount; ++i){
    		m_vVertex[i].vName = i;
    		m_vVertex[i].next = NULL;
    	}
    }
    
    void GraphList::inputEdgeCount()
    {
    	cout << "please input count of edge:";
    	cin >> m_eCount;
    }
    
    void GraphList::inputEdgeInfo()
    {
    	cout << "please input edge information:" << endl;
    	for (int i = 0; i < m_eCount; ++i){
    		cout << "the edge " << i << ":" << endl;
    
    		// 起点
    		int from = 0;
    		cout << "From: ";
    		cin >> from;
    		
    		// 权值
    		int weight = 0;
    		cout << "Weight:";
    		cin >> weight;
    
    		// 终点
    		int to = 0;
    		cout << "To: ";
    		cin >> to;
    		cout << endl;
    
    		addEdgeToList(from, weight, to);
    	}
    }
    
    void GraphList::addEdgeToList(int vFrom, int weight, int vTo)
    {
    	Edge* edge = new Edge();
    	edge->vName = vTo;
    	edge->weight = weight;
    	edge->next = NULL;
    	if (m_vVertex[vFrom].next){
    		Edge* tmp = m_vVertex[vFrom].next;
    		while(tmp->next){
    			tmp = tmp->next;
    		}
    		tmp->next = edge;
    	}else{
    		m_vVertex[vFrom].next = edge;
    	}
    }
    
    void GraphList::printGraph()
    {
    	for (int i = 0; i < m_vCount; ++i){
    		Edge* tmp = m_vVertex[i].next;
    		cout << "list:" << m_vVertex[i].vName << "->";
    		while(tmp){
    			cout << "(" << tmp->weight << ")";
    			cout << tmp->vName << "->";
    			tmp = tmp->next;
    		}
    		cout << "NULL" << endl;
    	}
    }
    
    // **************************************************************************
    // 流程控制
    // **************************************************************************
    void GraphList::createGraph()
    {
    	inputVertexCount();
    	makeVertexArray();
    	inputEdgeCount();
    	inputEdgeInfo();
    }



    // main.cpp

    // test for GraphList
    #include "GraphList.h"
    #include <cstdlib>
    
    int main()
    {
    	GraphList graph;
    	graph.createGraph();
    	graph.printGraph();
    
    	system("pause");
    
    	return 0;
    }


    假如有如下的图:



    运行结果:


    展开全文
  •  有向图:  连通图:  图的权:有些图的边或者狐剧有与他相关的数字,这种与图的边或者狐相关的数叫做权。  图的度:无向图顶点的边数叫度,有向图顶点的边数叫出度和入度 。  图的数据存储结构-邻接矩阵:  ...

    20171124

      图的概念:

      

      图的基本性质:

      

      无向图:

      

      有向图:

       

      连通图:

      

      图的权:有些图的边或者狐剧有与他相关的数字,这种与图的边或者狐相关的数叫做权。

      图的度:无向图顶点的边数叫度,有向图顶点的边数叫出度和入度 。


      图的数据存储结构-邻接矩阵:

      

      

       



      带权邻接矩阵表示法:

      

      图的存储结构-邻接表

      

      无向图的邻接表:

      

      有向图的邻接表:

      

      逆邻接表:

      

      带权邻接表:

      

      


    展开全文
  • 存储结构

    万次阅读 2016-07-14 14:50:57
    首先介绍了下图的抽象数据类型;...十字链表是结合邻接表和逆邻接表,是有向图的优化存储结构,方便求入度和出度;而邻接多重表是无向图的优化存储结构,方便对边进行操作;边集数组更偏向于边依次处理操作。
  • 存储结构的遍历。

    千次阅读 2019-06-07 18:27:10
    建立有向图的邻接表存储 遍历 深度优先搜索DFS 广度优先搜索BFS 图的存储方法 邻接矩阵存储法 定义存储结构类型 #define Max 20 ///先定义一个能储存足够大的顶点个数 typedef struct { char ...
  • * 以邻接表的作为存储方式,分别以广度优先和深度优先的算法判别有向图G是否存在顶点Vi到定点Vj的路径 */ public class AdjacencyList { public static void main ( String [ ] args ) { ...
  • 假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点到自己的弧)
  • 邻接矩阵作为无向图存储结构,实现起来是最简易的。实际上很多时候,并不会直接采用邻接矩阵去做什么,但是在后面学习其它存储结构的时候就会发现,因为邻接矩阵的简洁明快,更多地是用它去作为一个初始化的工具,...
  • 图解存储结构

    千次阅读 2017-10-19 23:14:26
    刚开始接触图形结构的时候,觉得它很烧脑子,因为像线性表它仅线性关系,树形结构清晰...要清楚地理解存储结构,首先要明白存储结构里要存储些什么东西。要存储图形结构的信息,无非就是存储的顶点(vec
  • 如果两个点m,n之间边,将数组matrix[]m[m]设为1,否则设为0。 如果有权,则将matrix[m]n[]设为权值,定义一个很大或者很小的数(只要不跟权值冲突即可),表示不相连。 空间复杂度为O(V^2),适合比较稠密的。 ...
  • 用邻接链表存储无向图和有向图

    千次阅读 2017-04-08 09:48:44
    上一篇文章我们说到用邻接矩阵存储有向图和无向图,这种方法的有点是很直观的知道点与点之间的关系,查找的复杂度是为O(1)。但是这种存储方式同时存在着占用较多存储空间的问题, 邻接矩阵存储很好理解,但是,有...
  • 【数据结构——存储结构

    千次阅读 多人点赞 2020-11-10 15:29:27
    目录一、图的定义和基本术语(一)图的定义(二)图的基本术语三级目录一、...有向图:每条边都是有方向的,边也称作弧 (二)图的基本术语 三级目录 一、图的存储结构 (一)邻接矩阵 三级目录 (二)邻接表 三级目录
  • 【数据结构】存储结构

    千次阅读 2017-05-01 13:51:08
    是否可以采用顺序存储结构存储?的特点:顶点之间的关系是m:n,即任何两个顶点之间都可能存在关系(边),无法通过存储位置表示这种任意的逻辑关系,所以,无法采用顺序存储结构。如何存储?考虑的定义,...
  • 数据结构:存储结构之邻接表

    万次阅读 多人点赞 2013-04-30 00:05:05
    对于图来说,邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式:邻接表(Adjacency List),即数组与链表相...
  • 数据结构之无向图存储

    千次阅读 2014-04-10 14:18:29
    一、存储结构 1.1 邻接矩阵  的邻接矩阵存储方式是用两个数组来表示。一个一维数组存储中顶点信息,一个二维数组(邻接矩阵)存储中的边或弧的信息。  设Gn个顶点,则邻接矩阵是一个n*...
  • 【图结构专题】有向图

    万次阅读 2018-03-19 22:00:26
    有向图 一. 有向图的相关术语 在有向图中,边是单向的:每条边连接的两个顶点都是一个有序对,它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图:比如任务調度的依赖关系,社交网络的任务关系等等...
  • 本文是[数据结构基础系列(7):]中第4课时[的邻接矩阵存储结构及算法]的例程。#include #include #define MAXV 100 /*最大顶点数设为100*/ #define LIMITLESS 9999 typedef struct { int no; //顶点编号 char...
  • 存储结构由于的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系,即没有顺序映像的存储结构,但可以借助数组的数据类型表示元素之间的关系。...
  • 数据结构~16.的基本概念和存储结构

    万次阅读 多人点赞 2020-08-14 20:47:13
    线性化二叉树 ...前言        在上一篇文章里面,我们使用了自定义的栈来代替了系统栈,通过循环实现了二叉树的遍历,提升了效率。...对于二叉链表的存储结构,n个结点的二叉树 n + 1
  • (一) 什么是图存储结构

    千次阅读 2019-03-18 11:36:52
    阅读:1,220 作者:解学武 (数据结构)图的存储结构完全攻略 ...逻辑关系数据的结构——图存储结构。 图 1 图存储结构示意图 图 1 所示为存储 V1、V2、V3、V4 的图结构,从图中可以清楚的看...
  • 数据结构:存储结构之邻接矩阵

    万次阅读 多人点赞 2013-04-30 00:03:26
    图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组...我们再来看一个有向图样例,如图7-4-3所示的左图。 在图的术语中,我们提到了网的概念,也就
  • 以十字链表作为有向图存储结构,将邻接表和逆邻接表结合起来,对统计结点的出入度很方便, 这是之前的一篇日志,也是说图的存储的,有兴趣的也可以看看 图的几种存储结构 下面是代码: //graph.h #include ...
  • ——基本的算法(一)存储结构

    万次阅读 多人点赞 2018-10-19 20:39:25
    图——基本的图算法(一)图的存储结构 1. 图的表示方法 对于图G=(V, E)来说,可以有两种标准的表示方法,这两种方法都可以表示有向图和无向图: (1)邻接矩阵 (2)邻接链表 ...
  • 有向图的邻接矩阵存储顶点删除

    千次阅读 2018-06-14 17:56:47
    假设有向图G采用邻接矩阵存储,要求删除某一个顶点i(包括与其相关连的边)。输入第一行第一个整数n表示顶点的个数(顶点编号为0到n-1),第二个数表示被删除的顶点编号,接下来是为一个n*n大小的整数矩阵,表示图的...
  •  图的存储结构主要包括邻接矩阵和邻接表,本算法库提供存储结构的定义,以及用于构造图存储结构、不同结构的转换及显示的代码。算法库采用程序的多文件组织形式,包括两个文件:    1.头文件:graph.h,包含定义...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 505,278
精华内容 202,111
关键字:

有向图的存储结构有等方法