文档章节

【算法与数据结构】图 -- 邻接表

cuihao
 cuihao
发布于 2014/12/01 15:06
字数 648
阅读 10
收藏 0
/************************************************************************ 边(弧)结点 -------------------------- |adjvex | info | nextarc | -------------------------- adjvex:邻接点域,该点在图中的位置 info :相关信息,比如可以保存从某顶点到该点的权值 nextac:指向下一个与该点有相同邻接点的顶点 顶点结点 ------------------ |data | firstarc | ------------------ data :该顶点的数据 firstarc:第一个与该顶点邻接的顶点 e.g. 顶点1,2,3,4 --------- -------- --------- 0 | 1 | |--->| 2 | |--->| 1 | ^ | --------- 1 | 2 | ^ | --------- --------- 2 | 3 | |--->| 3 | ^ | --------- --------- 3 | 4 | |--->| 0 | ^ | --------- --------- PS:画上面这个图 容易么我 ************************************************************************/

 

 

 

//最大顶点个数
const int MAX_VERTEX = 100; //最大值
const int MAX_VALUE = (1 << 31) - 1; //边(弧)结点
typedef struct _tagArcNode { int                 adjvex;  //该边(弧)所指向的顶点在图中的位置
    struct _tagArcNode* nextarc; //下一个与该顶点有相同邻接点的边(弧)结点
    char                info;    //相关信息,比如可以保存该边(弧)的权值
}ArcNode; //顶点节点
typedef struct _tagVNode { char data;          //顶点信息
    ArcNode* firstArc;  //该顶点的第一条边(弧)所指向的顶点
}VNode, AdjList[MAX_VERTEX]; typedef struct _tagGraph { AdjList vertices; //该图的所有顶点
    int vexnum;        //顶点个数
    int arcnum;        //边(弧)的条数
}Graph;

 

 

 

定位顶点在图中的位置,其位置也就是在一维数组中的下标

int Locate(Graph& graph, char ch) { for (int i = 0; i < graph.vexnum; ++ i) { if (ch == graph.vertices[i].data) return i; } return -1; }

 

 

构造图

void CreateGraph(Graph& graph) { int num = 0; cout << "请输入图的顶点个数:"; cin >> num; graph.vexnum = num; cout << "请输入图的边(弧)的条数:"; cin >> num; graph.arcnum = num; cout<<endl<<endl; cout<<"开始输入每个顶点"<<endl; for (int i = 0; i < graph.vexnum; ++ i) { cout << "请输入顶点:"; char ch = 0; cin >> ch; graph.vertices[i].data = ch; graph.vertices[i].firstArc = NULL; } cout<<endl<<"结束输入顶点"<<endl<<endl; cout<<"开始构造邻接表"<<endl; for (int i = 0; i < graph.vexnum; ++ i) { int nCount = 1; while(1) { cout << "请输入顶点 "<<graph.vertices[i].data<<" 的第 " << nCount++<<" 个邻接点, 输入#结束:"; char ch = 0; cin >> ch; if (ch == '#') break; ArcNode* pArcNode = new ArcNode(); pArcNode->adjvex = Locate(graph, ch); pArcNode->nextarc = NULL; //如果该顶点还没有设置第一条边(弧),则将该输入顶点确定的边(弧) //作为该顶点的第一条边(弧)
            if (NULL == graph.vertices[i].firstArc) { graph.vertices[i].firstArc = pArcNode; } //否则,遍历该顶点所在链表,找到最后一个节点,将其nextarc指针域 //设置为由当前输入的顶点确定的边(弧)
            else { ArcNode* pTemp = graph.vertices[i].firstArc; //直到找到顶点所在链表的最后一个边(弧)结点为止
                while(pTemp->nextarc != NULL) pTemp = pTemp->nextarc; //找到最后一个边(弧)结点后,将其nextarc指针域设置为当前输入的顶点所确定的边(弧)
                pTemp->nextarc = pArcNode; } } //while(1)
    } //for
 cout << endl<<"结束构造邻接表"<<endl<<endl; }

 

 

 

int _tmain(int argc, _TCHAR* argv[]) { Graph graph; CreateGraph(graph); return 0; }

 

 

 

 

 

© 著作权归作者所有

cuihao

cuihao

粉丝 10
博文 103
码字总数 106528
作品 0
海淀
私信 提问
数据结构之图(存储结构、遍历)

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

graylee
2015/03/10
0
0
数据结构探险之图篇(上)理论篇

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

天涯明月笙
2017/09/11
0
0
图结构(Graph)

定义:图可以理解由顶点集合V和边的集合E构成的一种数据结构 G=(V,E)。图的边可用括号括住两个顶点来表示,通常用圆括号 表示无向图的边,尖括号表示有向图的边。 定义:与一个顶点...

RapidBird
2010/03/25
393
0
图数据结构入门

在这篇文章中,我们将探索像图这样的非线性数据结构。我们将介绍其核心概念和典型应用。 你可能正在使用使用图(和树)数据结构的程序。比方说,你想知道你工作的地方和家之间的最短路径,你...

祖冲之
2018/08/28
3.9K
0
【译】Swift算法俱乐部-图

本文是对 Swift Algorithm Club 翻译的一篇文章。 Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下...

Andy_Ron
07/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Replugin借助“UI进程”来快速释放Dex

public static boolean preload(PluginInfo pi) { if (pi == null) { return false; } // 借助“UI进程”来快速释放Dex(见PluginFastInstallProviderProxy的说明) return PluginFastInsta......

Gemini-Lin
今天
4
0
Hibernate 5 的模块/包(modules/artifacts)

Hibernate 的功能被拆分成一系列的模块/包(modules/artifacts),其目的是为了对依赖进行独立(模块化)。 模块名称 说明 hibernate-core 这个是 Hibernate 的主要(main (core))模块。定义...

honeymoose
今天
4
0
CSS--属性

一、溢出 当内容多,元素区域小的时候,就会产生溢出效果,默认是纵向溢出 横向溢出:在内容和容器之间再套一层容器,并且内部容器要比外部容器宽 属性:overflow/overflow-x/overflow-y 取值...

wytao1995
今天
4
0
精华帖

第一章 jQuery简介 jQuery是一个JavaScript库 jQuery具备简洁的语法和跨平台的兼容性 简化了JavaScript的操作。 在页面中引入jQuery jQuery是一个JavaScript脚本库,不需要特别的安装,只需要...

流川偑
今天
7
0
语音对话英语翻译在线翻译成中文哪个方法好用

想要进行将中文翻译成英文,或者将英文翻译成中文的操作,其实有一个非常简单的工具就能够帮助完成将语音进行翻译转换的软件。 在应用市场或者百度手机助手等各大应用渠道里面就能够找到一款...

401恶户
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部