文档章节

邻接表-无向图

cyleft
 cyleft
发布于 2017/05/16 11:52
字数 321
阅读 9
收藏 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
数据结构与算法(图)

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

李文良
2016/05/24
69
0
图的基础知识(二、存储)

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

大胖和二胖
2016/11/30
9
0

没有更多内容

加载失败,请刷新页面

加载更多

10分钟读懂阿里巴巴高级专家在Flutter Live2018的分享

作者:闲鱼技术-宗心 12月4日,google flutter团队宣布第一个flutter正式版本发布。次日,Flutter Live Beijing 会议上,google flutter团队邀请了在这一技术方案中重要的合作伙伴闲鱼团队分...

阿里云官方博客
14分钟前
1
0
RxJava window操作符

原文:https://github.com/Froussios/Intro-To-RxJava/blob/master/Part%204%20-%20Concurrency/3.%20Sequences%20of%20coincidence.md Sequences of coincidence Rx试图避免管道(pipeline)外......

woshixin
21分钟前
1
0
05.Beetl标签函数以及定界符、占位符介绍---《Beetl视频课程》

本期视频实现了博客的详情页面; 内容简介:使用了标签函数layout完成详情功能 一起学beetl目录:https://my.oschina.net/u/1590490?tab=newest&catalogId=6214598 作者:GK #标签函数 layo...

Gavin-King
22分钟前
1
0
谷歌浏览器的打印功能

var OpenWindow = window.open(""); OpenWindow.document.write("<HTML>"); OpenWindow.document.write("<HEAD>"); OpenWindow.document.write("<meta http-equiv=......

卖星星的小矮人
23分钟前
1
0
曼哈顿距离(Manhattan Distance )详解

概念 曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离,即d(i,j)=|xi-xj|+|yi-yj|。对于一个具有正南正北、正东正西方向规则布局的城镇街道,从一点到达另一点的距离正是在南...

hejunbinlan
28分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部