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

数据结构之图的基本概念中了解了图的基本概念,接下来对图的代码实现进行详解。邻接无向图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)


相关推荐

  • 如何清理电脑中c盘的垃圾_计算机基本组成

    如何清理电脑中c盘的垃圾_计算机基本组成系统盘,也就是我们常说的C盘!必须要保持足够的存储空间,才能够确保电脑不会运行卡顿,或者出现一些系统性的问题。其实,我们安装系统的时候,C盘最多也就被占用20G左右的空间。但是C盘作为系统盘,电脑运行时所产生的系统缓存文件、垃圾文件以及程序运行文件等等,都会不断的占用C盘的空间,使得C盘越来越小,电脑越用越卡!今天大白菜就和大家分享4招c盘清理方法,让大家的C盘可以腾出更多的空间,保证电脑运行更加…

  • idea全局搜索文件名_linux 搜索文件名

    idea全局搜索文件名_linux 搜索文件名Ctrl+shift+F进行全局文本搜索,注意是搜索的文本shift+shift 全局搜索类

  • 网站留言板的功能_网页留言板源码

    网站留言板的功能_网页留言板源码本文描述如何在网页上实现一个简单的留言板功能,仅支持文字留言。开发环境:dreamweaverCChtml+jscirpt+php前置条件:1、一个简单的网站已经搭建完毕,支持用户登录网站。2、用户已登录网站。实现步骤:一、新建留言板网页1、新建网页:whiteboard.html留言板(js-div-whiteboard…

    2022年10月26日
  • JavaScript中的数组方法总结+详解「建议收藏」

    JavaScript中的数组方法总结+详解「建议收藏」在JS中,数组方法是非常重要且常用的的方法.在此整理总结一番.JavaScript数组的力量隐藏在数组方法中。1.js常用数组方法方法名功能返回值是否改变原数组版本push()在数组最后一位添加一或多个元素返回长度YES5-unshift()在数组前添加一或多个元素返回长度YES5-2.方法详解1.push……

  • IDEA使用ideaVim, 配置自定义vim快捷键[通俗易懂]

    IDEA使用ideaVim, 配置自定义vim快捷键[通俗易懂]C:\Users\Administrator文件夹下创建_ideavimrc,我这里用的是win系统需要安装ideaVim插件letmapleader=”sethlsearchsetincsearchsetignorecasesetsmartcasesetshowmodesetnumbersetrelativenumbersetscrolloff=…

  • 【Mongodb】sharding 集群Add/Remove 节点

    【Mongodb】sharding 集群Add/Remove 节点

发表回复

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

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