文档章节

邻接表-无向图

cyleft
 cyleft
发布于 2017/05/16 11:52
字数 321
阅读 7
收藏 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
数据结构探险之图篇(上)理论篇

数据结构探险之图篇 什么是图? 如下图:无向图 & 有向图 箭头分方向。 无向图中每条认为有来有回两条线 图中的概念: 结点称为顶点。 之间的线称为弧。 弧尾和弧头(箭头)。 从顶点发出去和...

天涯明月笙
2017/09/11
0
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

没有更多内容

加载失败,请刷新页面

加载更多

js 操作cookie

var cookie = {// 设置cookie方法 set:function(key,val,time){ var date = new Date(); //获取当前时间 var expiresDays = time; //将date设置为n天以后的时间...

小丶二
2分钟前
0
0
限制root远程登录 su和sudo命令

9月21日任务 3.7 su命令 3.8 sudo命令 3.9 限制root远程登录 对于Linux而言,权限的重要性毋庸置疑!对于普通用户而言无法执行那些只有root用户才能有效的命令,导致工作无法有效进行; 系统...

robertt15
4分钟前
0
0
MQTT协议的初浅认识之通讯级别和持久会话

背景 这是我最近了解MQTT协议的最后一部分内容了,MQTT协议里面的QOS和Keep Alive是两个比较重要的内容。QOS的设置,直接影响了订阅客户端与中间件之间的消息交互行为。而Keep Alive直接影响...

亚林瓜子
6分钟前
0
0
calc

width: calc(100% - 30px); 特别注意:减号左右空格,均不能去掉。 width: calc(100% - 30px);

柴高八斗之父
14分钟前
0
0
Spring Cloud Gateway全局过滤器GlobalFilter:返回消息和重定向

Spring Cloud Gateway的全局过滤器GlobalFilter,顾名思义,声明后会对所有的请求生效,可以用来做权限控制,这里简单记录一下拦截到非法请求后如何返回自定义信息和将请求重定向到指定URL。...

夜雨寄北09
17分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部