数据结构之图的创建(邻接表)

数据结构之图的基本概念中了解了图的基本概念,接下来对图的代码实现进行详解。邻接无向图1.邻接表无向图介绍邻接表无向图是指通过邻接表表示的无向图。上面的图G1包含了"A,B,C,D,

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

数据结构之图的创建(邻接表)此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

  数据结构之图的基本概念中了解了图的基本概念,接下来对图的代码实现进行详解。

邻接无向图

1. 邻接表无向图介绍

  邻接表无向图是指通过邻接表表示的无向图。

数据结构之图的创建(邻接表)

  上面的图G1包含了”A,B,C,D,E,F,G”共7个顶点,而且包含了”(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)”共7条边。

  上图右边的矩阵是G1在内存中的邻接表示意图。每一个顶点都包含一条链表,该链表记录了”该顶点的邻接点的序号”。例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是”0,1,3″;而这”0,1,3″分别对应”A,B,D”的序号,”A,B,D”都是C的邻接点。就是通过这种方式记录图的信息的。

2. 邻接表无向图代码实现

(1)数据结构

struct ENode
{
    int nVindex;  // 该边所指的顶点的位置
    ENode *pNext; // 指向下一个边的指针
};

struct VNode
{
    char data;  // 顶点信息
    ENode *pFirstEdge; // 指向第一条依附该顶点的边
};

(2)图的创建

listUDG(char *vexs, int vlen, char edges[][2], int elen)
{
    m_nVexNum = vlen;
    m_nEdgNum = elen;

    // 初始化"邻接表"的顶点
    for (int i = 0; i < vlen; i ++)
    {
        m_mVexs[i].data = vexs[i];
        m_mVexs[i].pFirstEdge = NULL;
    }

    char c1,c2;
    int p1,p2;
    ENode *node1, *node2;
    // 初始化"邻接表"的边
    for (int j = 0; j < elen; j ++)
    {
        // 读取边的起始顶点和结束顶点
        c1 = edges[j][0];
        c2 = edges[j][1];
        p1 = GetVIndex(c1);
        p2 = GetVIndex(c2);

        node1 = new ENode();
        node1->nVindex = p2;
        if (m_mVexs[p1].pFirstEdge == NULL)
        {
            m_mVexs[p1].pFirstEdge = node1;
        }
        else
        {
            LinkLast(m_mVexs[p1].pFirstEdge, node1);
        }

        node2 = new ENode();
        node2->nVindex = p1;
        if (m_mVexs[p2].pFirstEdge == NULL)
        {
            m_mVexs[p2].pFirstEdge = node2;
        }
        else
        {
            LinkLast(m_mVexs[p2].pFirstEdge, node2);
        }
    }

}

(3)完整代码

数据结构之图的创建(邻接表)
数据结构之图的创建(邻接表)

#include "stdio.h" #include <iostream> using namespace std; #define MAX 100 // struct ENode { int nVindex; // 该边所指的顶点的位置 ENode *pNext; // 指向下一个边的指针 }; struct VNode { char data; // 顶点信息 ENode *pFirstEdge; // 指向第一条依附该顶点的边 }; // 无向邻接表 class listUDG { public: listUDG(){}; listUDG(char *vexs, int vlen, char edges[][2], int elen) { m_nVexNum = vlen; m_nEdgNum = elen; // 初始化"邻接表"的顶点 for (int i = 0; i < vlen; i ++) { m_mVexs[i].data = vexs[i]; m_mVexs[i].pFirstEdge = NULL; } char c1,c2; int p1,p2; ENode *node1, *node2; // 初始化"邻接表"的边 for (int j = 0; j < elen; j ++) { // 读取边的起始顶点和结束顶点 c1 = edges[j][0]; c2 = edges[j][1]; p1 = GetVIndex(c1); p2 = GetVIndex(c2); node1 = new ENode(); node1->nVindex = p2; if (m_mVexs[p1].pFirstEdge == NULL) { m_mVexs[p1].pFirstEdge = node1; } else { LinkLast(m_mVexs[p1].pFirstEdge, node1); } node2 = new ENode(); node2->nVindex = p1; if (m_mVexs[p2].pFirstEdge == NULL) { m_mVexs[p2].pFirstEdge = node2; } else { LinkLast(m_mVexs[p2].pFirstEdge, node2); } } } ~listUDG() { ENode *pENode = NULL; ENode *pTemp = NULL; for (int i = 0; i < m_nVexNum; i ++) { pENode = m_mVexs[i].pFirstEdge; if (pENode != NULL) { pTemp = pENode; pENode = pENode->pNext; delete pTemp; } delete pENode; } } void PrintUDG() { ENode *pTempNode = NULL; cout << "邻接无向表:" << endl; for (int i = 0; i < m_nVexNum; i ++) { cout << "顶点:" << GetVIndex(m_mVexs[i].data)<< "-" << m_mVexs[i].data<< "->"; pTempNode = m_mVexs[i].pFirstEdge; while (pTempNode) { cout <<pTempNode->nVindex << "->"; pTempNode = pTempNode->pNext; } cout << endl; } } private: // 返回顶点的索引 int GetVIndex(char ch) { int i = 0; for (; i < m_nVexNum; i ++) { if (m_mVexs[i].data == ch) { return i; } } return -1; } void LinkLast(ENode *pFirstNode, ENode *pNode) { if (pFirstNode == NULL || pNode == NULL) { return; } ENode *pTempNode = pFirstNode; while (pTempNode->pNext != NULL) { pTempNode = pTempNode->pNext; } pTempNode->pNext = pNode; } private: int m_nVexNum; // 顶点数目 int m_nEdgNum; // 边数目  VNode m_mVexs[MAX]; }; void main() { char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}}; int vlen = sizeof(vexs)/sizeof(vexs[0]); int elen = sizeof(edges)/sizeof(edges[0]); listUDG* pG = new listUDG(vexs, vlen, edges, elen); pG->PrintUDG(); // 打印图  return; }

View Code

数据结构之图的创建(邻接表)

邻接有向图

1. 邻接表有向图介绍

  邻接表有向图是指通过邻接表表示的有向图。

数据结构之图的创建(邻接表)

  上面的图G2包含了”A,B,C,D,E,F,G”共7个顶点,而且包含了”<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>”共9条边。

上  图右边的矩阵是G2在内存中的邻接表示意图。每一个顶点都包含一条链表,该链表记录了”该顶点所对应的出边的另一个顶点的序号”。例如,第1个顶点(顶点B)包含的链表所包含的节点的数据分别是”2,4,5″;而这”2,4,5″分别对应”C,E,F”的序号,”C,E,F”都属于B的出边的另一个顶点。

2. 邻接表有向图代码实现

(1)数据结构

struct ENode
{
    int nVindex;  // 该边所指的顶点的位置
    ENode *pNext; // 指向下一个边的指针
};

struct VNode
{
    char data;  // 顶点信息
    ENode *pFirstEdge; // 指向第一条依附该顶点的边
};

(2)邻接表有向图创建

listDG(char *vexs, int vlen, char edges[][2], int elen) { m_nVexNum = vlen; m_nEdgNum = elen; // 初始化"邻接表"的顶点 for (int i = 0; i < vlen; i ++) { m_mVexs[i].data = vexs[i]; m_mVexs[i].pFirstEdge = NULL; } char c1,c2; int p1,p2; ENode *node1; // 初始化"邻接表"的边 for (int j = 0; j < elen; j ++) { // 读取边的起始顶点和结束顶点 c1 = edges[j][0]; c2 = edges[j][1]; p1 = GetVIndex(c1); p2 = GetVIndex(c2); node1 = new ENode(); node1->nVindex = p2; if (m_mVexs[p1].pFirstEdge == NULL) { m_mVexs[p1].pFirstEdge = node1; } else { LinkLast(m_mVexs[p1].pFirstEdge, node1); } } }

(3)完整代码实现

数据结构之图的创建(邻接表)
数据结构之图的创建(邻接表)

#include "stdio.h" #include <iostream> using namespace std; #define MAX 100 // struct ENode { int nVindex; // 该边所指的顶点的位置 ENode *pNext; // 指向下一个边的指针 }; struct VNode { char data; // 顶点信息 ENode *pFirstEdge; // 指向第一条依附该顶点的边 }; // 有向邻接表 class listDG { public: listDG(){}; listDG(char *vexs, int vlen, char edges[][2], int elen) { m_nVexNum = vlen; m_nEdgNum = elen; // 初始化"邻接表"的顶点 for (int i = 0; i < vlen; i ++) { m_mVexs[i].data = vexs[i]; m_mVexs[i].pFirstEdge = NULL; } char c1,c2; int p1,p2; ENode *node1; // 初始化"邻接表"的边 for (int j = 0; j < elen; j ++) { // 读取边的起始顶点和结束顶点 c1 = edges[j][0]; c2 = edges[j][1]; p1 = GetVIndex(c1); p2 = GetVIndex(c2); node1 = new ENode(); node1->nVindex = p2; if (m_mVexs[p1].pFirstEdge == NULL) { m_mVexs[p1].pFirstEdge = node1; } else { LinkLast(m_mVexs[p1].pFirstEdge, node1); } } } ~listDG() { ENode *pENode = NULL; ENode *pTemp = NULL; for (int i = 0; i < m_nVexNum; i ++) { pENode = m_mVexs[i].pFirstEdge; if (pENode != NULL) { pTemp = pENode; pENode = pENode->pNext; delete pTemp; } delete pENode; } } void PrintDG() { ENode *pTempNode = NULL; cout << "邻接有向表:" << endl; for (int i = 0; i < m_nVexNum; i ++) { cout << "顶点:" << GetVIndex(m_mVexs[i].data)<< "-" << m_mVexs[i].data<< "->"; pTempNode = m_mVexs[i].pFirstEdge; while (pTempNode) { cout <<pTempNode->nVindex << "->"; pTempNode = pTempNode->pNext; } cout << endl; } } private: // 返回顶点的索引 int GetVIndex(char ch) { int i = 0; for (; i < m_nVexNum; i ++) { if (m_mVexs[i].data == ch) { return i; } } return -1; } void LinkLast(ENode *pFirstNode, ENode *pNode) { if (pFirstNode == NULL || pNode == NULL) { return; } ENode *pTempNode = pFirstNode; while (pTempNode->pNext != NULL) { pTempNode = pTempNode->pNext; } pTempNode->pNext = pNode; } private: int m_nVexNum; // 顶点数目 int m_nEdgNum; // 边数目  VNode m_mVexs[MAX]; }; void main() { char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'B'}, {'B', 'C'}, {'B', 'E'}, {'B', 'F'}, {'C', 'E'}, {'D', 'C'}, {'E', 'B'}, {'E', 'D'}, {'F', 'G'}}; int vlen = sizeof(vexs)/sizeof(vexs[0]); int elen = sizeof(edges)/sizeof(edges[0]); listDG *pG = new listDG(vexs, vlen, edges, elen); pG->PrintDG(); // 打印图  return; }

View Code

数据结构之图的创建(邻接表)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/120150.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • css半透明层

    css半透明层首次登录弹出提示层,主要有两个层:半透明层,遮住下面的内容;提示层(主要内容),下面为这两个层的css样式。针对IE透明使用的是filter:alpha(opacity=35),针对FF透明的相关代码是opacity:0.35,这样至少在IE和FF下是兼容的,通过测试。.mask{ border:0px; background:#000; width:100%; …

  • 〖教程〗Ladon 0day通用执行命令DLL生成器-MS17010演示[通俗易懂]

    〖教程〗Ladon 0day通用执行命令DLL生成器-MS17010演示[通俗易懂]Ladon8.9更新功能20210920[+]CmdDllWindows0day漏洞通用DLL注入生成器,生成的DLL仅5KB,非常适合0day加载2021.9.15[u]webscanCS保留[u]CmdDll去除黑框2021.9.14[+]CVE-2021-40444MicrosoftMSHTML远程代码执行漏洞,Office文档利用模块影响版本:包括Windows7/8/8.1/10,WindowsServer2008/2008R2/2012/2012R2/2016

  • java关于日期的运算等处理方法

    java关于日期的运算等处理方法

  • 【用户画像】从0到1掌握用户画像知识体系

    【用户画像】从0到1掌握用户画像知识体系一、初始用户画像1.1用户画像随着用户的一切行为数据可以被企业追踪到,企业的关注点日益聚焦在如何利用大数据为经营分析和精准营销服务,而要做精细化运营,首先要建立本企业的用户画像。提到用户画像的概念,我们区分下用户角色(Persona)和用户画像(Profile):1.1.1用户角色用户角色本质是一个用以沟通的工具,当我们讨论产品、需求、场景、用户体验的时候,为了避免在目标用户理解上的分歧,用户角色应运而生。用户角色建立在对真实用户深刻理解,及高精准相关数据的概括之上,虚构的包含典型用

  • Opencv学习笔记(九)光流法

    Opencv学习笔记(九)光流法原创文章,转贴请注明:http://blog.csdn.net/crzy_sparrow/article/details/7407604   本文目录:     一.基于特征点的目标跟踪的一般方法     二.光流法     三.opencv中的光流法函数    四.用类封装基于光流法的目标跟踪方法     五.完整代码     六.参考文献

  • 搭建自己的云计算平台

    1.Enomalism(http://www.enomaly.com/)云计算平台。Enomalism是一个开放源代码项目,它提供了一个功能类似于EC2的云计算框架。Enomalism基于Linux,同时支持Xen和KernelVirtualMachine(KVM)。Enomalism提供了一个基于TurboGearsWeb应用程序框架和Python的软件栈。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号