文档章节

邻接表-无向图

cyleft
 cyleft
发布于 2017/05/16 11:52
字数 321
阅读 7
收藏 0
点赞 0
评论 0
#include <iostream>

using namespace std;
#define MVNum 10
typedef char OtherInfo;
typedef char VerTexype;
typedef int Status;

string str[10] = {"th","st","nd","th","th","th","th","th","th","th"};

typedef struct ArcNode{
    int adjvex;
    struct ArcNode * nextarc;
    OtherInfo info;
}ArcNode;

typedef struct VNode{
    VerTexype data;
    ArcNode *firststarc;
}VNode,AdjList[MVNum];

typedef struct {
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;

int LocateVex(ALGraph G,VerTexype v);

void init(ALGraph &G,int vexnum,int arcnum){
    G.arcnum = arcnum;
    G.vexnum = vexnum;
    for(int i=0;i<vexnum;i++){
        G.vertices[i].firststarc = NULL;
    }
}

Status CreateUDG(ALGraph &G){
    VerTexype v1,v2;
    cout<<"Please enter vexnum and arcnum:"<<endl;
    cin>>G.vexnum>>G.arcnum;
    cout<<"The vexnum and arcnum are "<<G.vexnum<<" and "<<G.arcnum<<" respectively"<<endl<<endl;
    init(G,G.vexnum,G.arcnum);
    for(int i=0;i<G.vexnum;i++){
        cout<<"Please enter the "<<i<<str[i]<<" vex is:"<<endl;
        cin>>G.vertices[i].data;
    }
    cout<<endl;
    for(int i=0;i<G.arcnum;i++){
        cout<<"Please enter the starting point and end point"<<endl;
        cin>>v1>>v2;

        int x = LocateVex(G,v1);
        int y = LocateVex(G,v2);
        while(x==-1||y==-1||x==y){
            cout<<"Maybe you typed the wrong one,please enter again"<<endl;
            cout<<"Please enter the starting point and end point"<<endl;
            cin>>v1>>v2;

            x = LocateVex(G,v1);
            y = LocateVex(G,v2);
        }
        cout<<"--------------------"<<endl;
        ArcNode *p1 = new ArcNode;
        p1->adjvex = y;
        p1->nextarc = G.vertices[x].firststarc;
        G.vertices[x].firststarc = p1;

        ArcNode *p2 = new ArcNode;
        p2->adjvex = x;
        p2->nextarc = G.vertices[y].firststarc;
        G.vertices[y].firststarc = p2;
    }
    return 1;
}

void ALGraphDisplay(ALGraph G){
    for(int i=0;i<G.vexnum;i++){
        cout<<G.vertices[i].data<<" ";
        while(G.vertices[i].firststarc!=NULL){
            cout<<G.vertices[i].firststarc->adjvex<<" ";

            G.vertices[i].firststarc = G.vertices[i].firststarc->nextarc;
        }
        cout<<endl;
    }
}

int main()
{
    ALGraph alg;
    CreateUDG(alg);
    ALGraphDisplay(alg);
    return 0;
}

int LocateVex(ALGraph G,VerTexype v){
    for(int i=0;i<G.vexnum;i++){
        if(G.vertices[i].data==v){
            return i;
        }
    }
    return -1;
}

 

© 著作权归作者所有

共有 人打赏支持
cyleft
粉丝 1
博文 31
码字总数 10068
作品 0
九江
程序员
图的基本概念

图的基本概念 1. 图的定义 定义:图(graph)是由一些点(vertex)和这些点之间的连线(edge)所组成的;其中,点通常被成为"顶点(vertex)",而点与点之间的连线则被成为"边或弧"(edege)。通常记为...

ShuyangZ
2016/10/22
11
0
小蚂蚁学习数据结构(29)——图的存储表示

图的数组(邻接矩阵)存储表示 方法:将图的顶点信息存储在一个一维数组中,并将它的邻接矩阵存储在一个二位数组中即构成图的数组(邻接矩阵)表示。 无向图的邻接矩阵具有如下特点: 1,它是...

嗜学如命的小蚂蚁
2016/02/04
37
0
图的基础知识(二、存储)

图需要存储的信息有以下这些 1、顶点信息 2、边或弧的信息,如果有权,也需要表示出来 3、顶点个数、边(弧)的个数 邻接矩阵及其实现 顶点数据存储: 一维数组 边(弧)信息存储 邻接矩阵 ...

大胖和二胖
2016/11/30
9
0
数据结构与算法(图)

基本概念: 顶点(Vertex):V表示顶点的集合 边(Edge):E表示边的集合 无向边:用圆括号(v,w)∈E,其中v,w∈V 有向边:用尖括号 带权重(例如边表示长度),带权的图通常称为网 抽象数据...

李文良
2016/05/24
69
0
【算法和数据结构】图(一)图的定义和封装(C++实现)

图,一种复杂的数据结构,在实际生活中起着举足轻重的作用。如路网(线路规划),社交网络描述等等。现在我们就以下面这个简单无向图(图1)为例,来说明使用邻接矩阵 实现图在计算机中的存储...

qq_28869927
2017/02/27
0
0
图基础知识

前言 图是非常重要的一种数据结构,它是一种多对多的关系,相比线性表、树等,它是最复杂的一种数据结构。 图由顶点和边组成,顶点之间由边连接,如果边有方向,则称为有向图,反之则为无向图...

某昆
2017/09/16
0
0
数据结构-08-集合(Set)-哈希表(Hash)-图(Map)

Set Set 是一种用于保存不重复元素的数据结构。常被用作测试归属性,故其查找的性能十分重要。 Set 是python自带的基本数据结构, 有多种初始化方式。 Python的set跟dict的Implementation方式...

Corwien
2016/06/17
53
0
数据结构之图(存储结构、遍历)

  新学期开始了,开始专心于技术上了,上学期的寒假总是那么短暂,飘飘乎就这样逝去,今天补补上学期还没学完的数据结构---图,希望能和大家一起探讨,共同进步~ 定义:   图是由顶点集合...

graylee
2015/03/10
0
0
图的JS实现

图的定义 图就是由若干个顶点和边连接起来的一种结构。很多东西都可以用图来说明,例如人际关系,或者地图。 其中图还分为有向图和无向图。 如下就是有向图 图的数据结构 对于图这种关系,可...

光哥很霸气
2017/10/12
0
0
图的基本算法实现(邻接矩阵与邻接表两种方法)

本博客前面文章已对图有过简单的介绍,本文主要是重点介绍有关图的一些具体操作与应用 阅读本文前,可以先参考本博客 各种基本算法实现小结(四)—— 图及其遍历 一、无向图 1 无向图——邻...

长平狐
2013/01/06
152
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JPA @MappedSuperclass 注解说明

基于代码复用和模型分离的思想,在项目开发中使用JPA的@MappedSuperclass注解将实体类的多个属性分别封装到不同的非实体类中。 1.@MappedSuperclass注解只能标准在类上:@Target({java.lang....

海博1600
16分钟前
0
0
Scala Configuration 相关API

Play使用了 Typesafe config library,但是也提供了一个有着更多Scala高级特性的的 Configuration 封装。不熟悉Typesafe配置的开发者可以移步 configuration文件的语法和特性文档。 读取配置...

Landas
今天
1
0
使用cookie技术 记住账号

1. 效果 2. 实现过程 2.1 前端 将用户的选中传递给后台 这个参数的获取是 参考:https://my.oschina.net/springMVCAndspring/blog/1860498 // var rememberLogin = $("#rememberLoginId").i...

Lucky_Me
今天
1
0
《趣谈网络协议》02之网络分层的真实含义

一、提出问题 1.提出问题 当你听到什么二层设备、三层设备、四层 LB 和七层 LB 中层的时候,是否有点一头雾水,不知道这些所谓的层,对应的各种协议具体要做什么“工作”? 2.这四个问题你弄...

aibinxiao
今天
2
0
Python3学习日志二 Python中的集合set和字典dict

1.集合set 定义一个集合set 我们可以看到定义集合set有两种不同的形式,如果要定义一个空的集合set不能用{}而是要用set();另外,集合是无序的,而且set中的元素是不可重复的,如果你定义了一...

Mr_bullshit
今天
0
0
adb 操作指令详解

ADB,即 Android Debug Bridge,它是 Android 开发/测试人员不可替代的强大工具,也是 Android 设备玩家的好玩具。 注:有部分命令的支持情况可能与 Android 系统版本及定制 ROM 的实现有关。...

孟飞阳
今天
0
0
nodejs安装以及环境配置(很好的node安装和配置文章,少走很多弯路)

一、安装环境 1、本机系统:Windows 10 Pro(64位) 2、Node.js:v6.9.2LTS(64位) 二、安装Node.js步骤 1、下载对应你系统的Node.js版本:https://nodejs.org/en/download/ 2、选安装目录进...

sprouting
今天
1
0
Redisson

了解了Redisson,发现使用挺简单的,接下来准备深入学习一下。 Redisson介绍 Redisson是架设于Redis基础之上的一个Java驻内存数据网格(In-Memory Data Grid) Redisson在基于NIO的Netty框架上...

to_ln
今天
0
0
python有哪些好玩的应用实现,用python爬虫做一个二维码生成器

python爬虫不止可以批量下载数据,还可以有很多有趣的应用,之前也发过很多,比如天气预报实时查询、cmd版的实时翻译、快速浏览论坛热门帖等等,这些都可以算是爬虫的另一个应用方向! 今天给...

python玩家
今天
0
0
python爬虫日志(3)-爬去异步加载网页

在浏览器检查元素页面中,选取Network中的XHR选项即可观察每次加载页面,网页发出的请求,观察url的规律即可利用封装的函数对每一页进行爬取。

茫羽行
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部