精华内容
下载资源
问答
  • 逆邻接表
    千次阅读
    2019-12-09 11:17:18

    逆序存储

    把出边当作入边存储:A->B变成B->A,每一个顶点的单链表存储指向他的顶点;

    建立逆序邻接表

    void create(int u,int v){	
    	for(int i=0;i<e;i++){
    		cin>>u>>v;//u->v
    		arcnode *q=new arcnode();
    		q->next=a[v].first->next;//头插法,把u插到v的单链表的头节点后面
    		q->data=s[u];//s为数据字符串
    		q->p=u;
    		a[v].first->next=q;
    	}
    }
    

    实例

    逆邻接表
    Time Limit: 1000/2000 MS (C/Others)   Memory Limit: 32768/32768 K (C/Others)

    Problem Description:
    对每个顶点vi将所有以顶点vi为弧头的弧链接起来,形成入边表,可以建立有向图的逆邻接表,从而便于求顶点的入度。设有一有向图G,其顶点值为字符型并假设各值互不相等,要求采用逆邻接表表示法存储。设计一个算法,存储该有向图并输出各顶点的入边信息。

    Input:
    有多组测试数据,每组数据的第一行为两个整数n和e,表示n个顶点和e条边(0<n<20);第二行为其n个顶点的值,按输入顺序进行存储;后面有e行,表示e条边的信息,每条边信息占一行,包括边所依附的顶点下标i和j,数据之间用空格隔开(注:要求采用头插法建立边表)。

    Output:
    输出该有向图中所有顶点的入边信息(空表不输出任何信息),每行最后均无空格,每两组数据之间有一空行,具体格式见样例。

    Sample Input:
    4 4
    ABCD
    0 1
    0 3
    1 2
    1 3

    4 4
    ABCD
    0 1
    0 2
    2 3
    3 0
    Sample Output:
    1->0
    2->1
    3->1->0

    0->3
    1->0
    2->0
    3->2
    Hint:

    Source:

    代码

    #include<iostream>
    using namespace std;
    struct arcnode{
    	int p; 
    	char data;
    	arcnode *next;
    };
    struct lianode{
    	arcnode *first;
    };
    int main(){
    	int n,e;
    	char s[55];//20条边多少结点? 
    	int c=0;
    	while(cin>>n>>e){
    		lianode a[55];
    		for(int i=0;i<n;i++){
    			a[i].first=new arcnode();
    			a[i].first->data=s[i];
    			a[i].first->p=i;
    			a[i].first->next=NULL;
    		}
    		int u,v;
    		cin>>s;
    		for(int i=0;i<e;i++){
    			cin>>u>>v;
    			arcnode *q=new arcnode();
    			q->next=a[v].first->next;
    			q->data=s[u];
    			q->p=u;
    			a[v].first->next=q;
    		}
    		if(c)
    			cout<<endl;
    		for(int i=0;i<n;i++){
    			if(a[i].first->next){
    				cout<<a[i].first->p;
    			arcnode *p=a[i].first->next;
    			while(p){
    				cout<<"->"<<p->p;
    				p=p->next;
    			}
    			cout<<endl;
    			}
    			
    		}
    		c++;
    	} 
    	return 0;
    }
    
    更多相关内容
  • 在图中任何两个顶点之间都可能存在联系,所以图的存储结构应该需要...常用的存储结构有邻接矩阵、邻接表(逆邻接表)、十字链表、邻接多重表、 边集数组。那么本博文将带你就 “邻接表(逆邻接表)” 来窥探一二。。。

    零、读前说明

    • 本文中所有设计的代码均通过测试,并且在功能性方面均实现应有的功能。
    • 设计的代码并非全部公开,部分无关紧要代码并没有贴出来。
    • 如果你也对此感兴趣、也想测试源码的话,可以私聊我,非常欢迎一起探讨学习。
    • 由于时间、水平、精力有限,文中难免会出现不准确、甚至错误的地方,也很欢迎大佬看见的话批评指正。
    • 嘻嘻。。。。 。。。。。。。。收!
        
         这一篇因项目上线中间忙拖了很久了才发出来,虽说也不是很复杂的内容,但是在学习的过程总结还是有很缓慢的,不过万幸坚持做完了,累并快乐着! 下一篇就不知道何年月能更新了(虽然看的人很少,但是还是要坚持做完),有事情回家一段时间,但愿所有事情能够顺利完成!!!

    一、概 述

      在图中任何两个顶点之间都可能存在联系,所以图的存储结构应该需要根据具体问题的要求来进行设计。从图的逻辑结构定义来看,图中任何一个顶点都可以看成是第一个顶点。常用的存储结构有邻接矩阵邻接表(逆邻接表)、十字链表邻接多重表边集数组。那么本博文将带你就 “邻接表(逆邻接表)” 来窥探一二。。。

    二、邻接表说明

      我们已经说明,对于稀疏图(边比较少的的图),邻接矩阵 占用空间大,空间浪费严重 。我们已经知道,使用链表形式可以明显的降低空间的浪费,那么是否可以将前面的数组形式的 邻接矩阵 用链表来表示呢。那么下面我们来看图的另外一种存储结构 — 邻接表 (Adjacency List)

      对于图中每个 顶点 v i v_i vi,将所有与 v i v_i vi 邻接的 顶点 连成一个 单链表,称为顶点 v i v_i vi边表(对于有向图则分别称为 出边表,反之为 入边表)。

      也就是说:

      1、将图中 所有的顶点 用一个数组来存储(也可以使用单链表存储,但数组容易读取顶点信息, vertex ),同时还需要保存指向此顶点的第一个邻接点信息的指针( firstEdge ),方便查找邻接点的信息;
      2、图中每一个顶点 v i v_i vi 的所有邻接点组成一个 线性表,由于邻接点的个数不确定,所以选择用单链表来存储;
      像这样把 数组链表 相结合的存储方式成为 邻接表

      邻接表 有两种结构:顶点表节点边表节点

      顶点表节点主要用于表示顶点的信息,主要需要记录顶点的信息指向此顶点的顶一个邻接点的指针,同样可以添加其他需要的元素,比如节点的个数等。

      边表节点主要用于表示顶点的邻接点,以及下一个邻接点。当然同样可以添加其他的需要的元素,比如边的权值等。

      本博文中所使用的边表结构和顶点表结构如下图所示。

    图2.1 结构示意图

    2.1、无向图的邻接表

      首先创造一个数组用来保存顶点的信息,以及一个指针指向顶点的第一个邻接点的指针,那么这个 first 指针域则成为了边表的头指针了。

      边表中的节点:表示的是节点在数组中的下标

      对于边 ( v 0 , v 1 ) (v_0,v_1) (v0,v1) 在邻接表中,可以理解为:顶点表中的第 0 个顶点( v 0 v_0 v0)到第 1 个顶点( v 1 v_1 v1)有一条边。

      无向图邻接表如下图所示。

    图2.2 无向图邻接表示意图
      

      顶点的度:与顶点 v i v_i vi 连接的边的个数,也就是在 firstEdge 链表的节点的个数。

      如何去判断两个顶点 i, j 是否存在边:测试顶点 i 的边表中是否存在终点为 j 的节点。

    2.2、有向图的邻接表

      有向图的邻接表是将顶点当作弧尾(默认是以弧尾)建立的邻接表,这样很容易的得到每个顶点的出度:顶点 i出边表的节点的个数

      但是求入度则变得困难:依次查找各个顶点的出边表中以顶点 v i v_i vi终点的节点的个数,所以需要将所有顶点及其边表扫描一遍。

      顶点 v i v_i vi 的所有的邻接点:该边表中所有顶点都是顶点 v i v_i vi 的邻接点。

      有向图邻接表如下图所示。

    图2.3 有向图邻接表示意图
      

    2.3、代码实现

    2.3.1、数据类型及操作函数定义

      一、数据类型定义

      根据图的定义,定义图的数据结构类型中,需要包含两个重要的信息,一为 顶点的集合,二为 边的集合,本测试中加入一个 顶点的个数 的元素。测试代码中定义图的数据结构如下所示。

    typedef void LGraph;
    typedef void LVertex;
    
    typedef struct _tag_LGraph
    {
        int count;        // 顶点的个数
        LVertex **vertex; // 顶点的信息
        LinkList **first; // 边集
    } TLGraph;
    
    typedef struct _tag_ListNode
    {
        LinkListNode next; //指向下一个边的指针
        int adjvex;        // 边的另一个顶点的下标
        int weight;        // 权值
    } TListNode;
    

      二、图的操作函数定义

      图的操作,本博文中主要涉及三部分,创建销毁等操作边的集合的操作顶点的集合的操作。为了方便后续的添加其他的操作等,定义如下面代码所示。

    #define UNDIRECTED_GRAPH 0               // 无向图定义
    #define DIRECTED_GRAPH !UNDIRECTED_GRAPH // 有向图定义
    
    /***
     *  边的操作集合
     **/
    typedef struct __func_Edge
    {
        int (*add)(LGraph *, int, int, int, int);
        int (*remove)(LGraph *, int, int, int);
        int (*get)(LGraph *, int, int);
        int (*count)(LGraph *, int);
    } funcEdge;
    
    /***
     *  顶点的操作集合
     **/
    typedef struct __func_vertex
    {
        int (*dgree)(LGraph *, int, int);
        int (*count)(LGraph *);
    } funcVertex;
    
    /***
     *  图的操作集合
     **/
    typedef struct __func_Graph
    {
        LGraph *(*create)(LVertex **, int);
        void (*destroy)(LGraph *);
        void (*clear)(LGraph *);
        void (*display)(LGraph *, int);
        funcEdge edge;     // 边的集合
        funcVertex vertex; //顶点的集合
    } funcGraph;
    
    extern funcGraph funGraph;
    
    

    2.3.2、主要操作函数的代码实现

      图的操作主要实现代码,方便起见,文件名称类型为 .cpp ,注释比较详细,此处不在赘述,代码如下所示。

    /**
     * 功 能:
     *      创建并返回有n个顶点的图
     * 参 数:
     *      v:与顶点相关的数据的指针
     *      n:顶点的个数
     * 返回值:
     *      成功:
     *      失败:NULL
     **/
    LGraph *LGraph_Create(LVertex **v, int n) // O(n)
    {
        TLGraph *ret = NULL;
    
        if ((v == NULL) || (n < 1))
            goto END;
    
        // 申请一个图结构内存
        ret = (TLGraph *)malloc(sizeof(TLGraph));
        if (ret == NULL)
            goto END;
    
        ret->count = n;                                          //  图的节点个数赋值
        ret->vertex = (LVertex **)calloc(n, sizeof(LVertex *));  // 申请节点的空间
        ret->first = (LinkList **)calloc(n, sizeof(LinkList *)); // 申请节点的邻接表的内存
    
        if ((ret->vertex == NULL) || (ret->first == NULL))
        {
            free(ret);
            free(ret->vertex);
            free(ret->first);
            ret = NULL;
            goto END;
        }
    
        // 顶点赋值
        for (int i = 0; i < n; i++)
        {
            ret->vertex[i] = v[i];
        }
    
        // 边集创建并赋值
        for (int i = 0; (i < n); i++)
        {
            // 创建链表
            ret->first[i] = funLinkList.create();
            if (ret->first[i] == NULL) // 创建失败
            {
                for (int j = 0; j < i; j++)
                {
                    funLinkList.destory(ret->first[j]); // 销毁链表
                }
                // 内存释放
                free(ret->first);
                free(ret->vertex);
                free(ret);
                ret = NULL; // 返回值重定向
                break;
            }
        }
    
    END:
        return ret;
    }
    
    /**
     * 功 能:
     *      添加顶点与顶点的关系 - 边
     *      在graph所指图中的v1和v2之间加上边,且边的权为w
     * 参 数:
     *      graph:要操作的图
     *      v1   :顶点(尾)的编号(位置)
     *      v2   :顶点(头)的编号(位置)
     *      w    :权值,如果为0,表示边不存在
     *      flag :表示是无向图还是有向图,如果为非0,表示为有向图
     * 返回值:
     *      0 :添加成功
     *      -1:添加失败,参数异常
     **/
    int LGraph_AddEdge(LGraph *graph, int v1, int v2, int w, int flag) // O(1)
    {
        TLGraph *tGraph = (TLGraph *)graph;
        TListNode *node = NULL, *node1 = NULL;
        int ret = -1;
    
        if (graph == NULL || w < 0 || //  w即可表示存在边(=1)也可表示边的权值(>=1),在表示边的权值的时候,一定是边存在(>0)
            ((v1 < 0) && (v1 >= tGraph->count)) ||
            ((v2 < 0) && (v2 >= tGraph->count)))
            goto RET;
    
        node = (TListNode *)malloc(sizeof(TListNode));
        if (node == NULL)
            goto RET;
    
        node->adjvex = v2;
        node->weight = w;
        funLinkList.insert(tGraph->first[v1], (LinkListNode *)node,
                           funLinkList.length(tGraph->first[v1])); // 采用尾插入,方便在打印的时候比较
    
        if (!flag) // 如果是无向边,则再进行一次反向插入
        {
            node1 = (TListNode *)malloc(sizeof(TListNode));
            if (node == NULL)
                goto RET;
    
            node1->adjvex = v1;
            node1->weight = w;
            funLinkList.insert(tGraph->first[v2], (LinkListNode *)node1,
                               funLinkList.length(tGraph->first[v2])); // 采用尾插入,方便在打印的时候比较
        }
        ret = 0;
    RET:
        return ret;
    }
    
    /**
     * 功 能:
     *      将graph所指图中v1和v2之间的边删除,返回权值
     * 参 数:
     *      graph:要操作的图
     *      v1   :顶点(尾)的位置(编号)
     *      v2   :顶点(头)的位置(编号)
     *      flag :表示是无向图还是有向图,如果为非0,表示为有向图
     * 返回值:
     *      删除成功 :非0值 -- 权值
     *      删除失败:0
     **/
    int LGraph_RemoveEdge(LGraph *graph, int v1, int v2, int falg) // O(n*n)
    {
        TLGraph *tGraph = (TLGraph *)graph;
        int ret = 0;
        TListNode *node = NULL;
    
        if ((tGraph == NULL) ||
            ((v1 < 0) && (v1 >= tGraph->count)) ||
            ((v2 < 0) && (v2 >= tGraph->count)))
            goto RET;
    
        for (int i = 0; i < funLinkList.length(tGraph->first[v1]); i++)
        {
            node = (TListNode *)funLinkList.get(tGraph->first[v1], i);
            if (node->adjvex == v2)
            {
                ret = node->weight;
                funLinkList.delet(tGraph->first[v1], i);
                break;
            }
        }
        if (!falg) // 如果是无线图的话,则删除反向的边
        {
            for (int i = 0; i < funLinkList.length(tGraph->first[v2]); i++)
            {
                node = (TListNode *)funLinkList.get(tGraph->first[v2], i);
                if (node->adjvex == v1)
                {
                    funLinkList.delet(tGraph->first[v2], i);
                    break;
                }
            }
        }
    
        free(node);
    RET:
        return ret;
    }
    
    /**
     * 功 能:
     *      将graph所指图中v1和v2之间的边的权值返回
     * 参 数:
     *      graph:要操作的图
     *      v1   :顶点(尾)的位置(编号)
     *      v2   :顶点(头)的位置(编号)
     * 返回值:
     *      0  :边 不存在
     *      -1 :参数异常
     *      其他:边存在或者权值
     **/
    int LGraph_GetEdge(LGraph *graph, int v1, int v2) // O(n*n)
    {
        TLGraph *tGraph = (TLGraph *)graph;
        int ret = -1;
        TListNode *node = NULL;
    
        if ((tGraph == NULL) ||
            ((v1 < 0) && (v1 >= tGraph->count)) ||
            ((v2 < 0) && (v2 >= tGraph->count)))
            goto RET;
    
        for (int i = 0; i < funLinkList.length(tGraph->first[v1]); i++)
        {
            node = (TListNode *)funLinkList.get(tGraph->first[v1], i);
            if (node->adjvex == v2)
            {
                ret = node->weight;
                break;
            }
            else
                ret = 0;
        }
    
    RET:
        return ret;
    }
    /**
     * 功 能:
     *      graph所指图中v顶点的度数
     * 参 数:
     *      graph:要操作的图
     *      v    :顶点 的位置(编号)
     *      flag :表示是无向图还是有向图,如果为非0,表示为有向图
     * 返回值:
     *      0  :参数异常
     *      其他:顶点的度
     **/
    int LGraph_VertexDgree(LGraph *graph, int v, int flag) // O(n*n*n)
    {
        TLGraph *tGraph = (TLGraph *)graph;
        int ret = 0;
    
        if ((tGraph == NULL) ||
            ((v < 0) && (v >= tGraph->count)))
            goto RET;
        /**
         *  对于有向图 ,顶点的度为出度加上入度
         *      出度 :等于邻接链表的长度
         *      入度 :其他的在邻接链表中存在此节点的每一个顶点
         *  对于无线图,顶点的度等于邻接链表的长度
         **/
        // 此节点的邻接链表的长度
        ret += funLinkList.length(tGraph->first[v]);
    
        if (flag) // 如果是有向图,则需要判断其他顶点与此顶点的关系
        {
            // 遍历图中的每一个顶点
            for (int i = 0; i < tGraph->count; i++)
            {
                // 遍历顶点的邻接链表
                for (int j = 0; j < funLinkList.length(tGraph->first[i]); j++)
                {
                    TListNode *node = (TListNode *)funLinkList.get(tGraph->first[i], j);
                    if (node->adjvex == v) // 如果邻接链表中存在此节点
                        ret++;
                }
            }
        }
    RET:
    
        return ret;
    }
    
    funcGraph funGraph = {
        LGraph_Create,
        LGraph_Destroy,
        LGraph_Clear,
        LGraph_Display_matrix,
        {
            LGraph_AddEdge,
            LGraph_RemoveEdge,
            LGraph_GetEdge,
            LGraph_EdgeCount,
        },
        {
            LGraph_VertexDgree,
            LGraph_VertexCount,
        }};
    

    2.3.3、测试案例的实现源码

      主要进行相关代码的测试,方便起见,测试案例的名称为 main.cpp ,注释比较详细,此处不在赘述说明,代码如下所示。

    #include "../src/graph/graph.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(int argc, char *argv[])
    {
        system("color "); // 颜色设置,用于在windows下终端显示的时候不明原因换行的问题
    
        printf("\n\e[1;31mLet's start with an example of an undirected graph:\e[0m\n");
    
        LVertex const *v[] = {"A", "B", "C", "D", "E", "F"};
        LGraph *ungraph = funGraph.create((LVertex **)v, 6);
    
        // 添加边
        funGraph.edge.add(ungraph, 0, 1, 1, UNDIRECTED_GRAPH); // (A, B)
        funGraph.edge.add(ungraph, 0, 2, 1, UNDIRECTED_GRAPH); // (A, C)
        funGraph.edge.add(ungraph, 0, 3, 1, UNDIRECTED_GRAPH); // (A, D)
        funGraph.edge.add(ungraph, 1, 4, 1, UNDIRECTED_GRAPH); // (B, E)
        funGraph.edge.add(ungraph, 1, 5, 1, UNDIRECTED_GRAPH); // (B, F)
        funGraph.edge.add(ungraph, 2, 1, 1, UNDIRECTED_GRAPH); // (C, B)
        funGraph.edge.add(ungraph, 3, 4, 1, UNDIRECTED_GRAPH); // (D, E)
    
        // 顶点的个数
        printf("\nThe number of vertices in the graph is : %d\n", funGraph.vertex.count(ungraph));
    
        // 显示邻接表
        printf("\nThe Adjacency List of the graph is :\n");
        funGraph.display(ungraph, 1);
    
        // 边的个数
        printf("\nThe number of Edge in the graph is : %d\n", funGraph.edge.count(ungraph, UNDIRECTED_GRAPH));
        // 顶点的度,参数为顶点在数组的下标
        printf("\nThe Degree of vertex 'B' is : %d\n", funGraph.vertex.dgree(ungraph, 1, UNDIRECTED_GRAPH));
    
        // 添加边,带有权值
        funGraph.edge.add(ungraph, 4, 2, 9, UNDIRECTED_GRAPH); // (E, C)  9
    
        // 边的权值
        printf("\nThe Weight of Edge (E, C) is : %d\n", funGraph.edge.get(ungraph, 4, 2));
    
        printf("\nThe Adjacency List of the graph is :\n");
        funGraph.display(ungraph, 0);
    
        // 添加边,带有权值  (E, C)
        funGraph.edge.remove(ungraph, 4, 2, 0);
    
        // 显示邻接表
        printf("\nThe Adjacency List of the graph is :\n");
        funGraph.display(ungraph, 0);
    
        // 边的个数
        printf("\nThe number of Edge in the graph is : %d\n", funGraph.edge.count(ungraph, UNDIRECTED_GRAPH));
        // 顶点的度,参数为顶点在数组的下标
        printf("\nThe Degree of vertex 'B' is : %d\n", funGraph.vertex.dgree(ungraph, 1, UNDIRECTED_GRAPH));
    	// fixed 2020.08.29 : 原本测试时(下图中显示效果)写的是“undirected”,为错误的,现已经改正!
        printf("\n\e[1;31mLet's start with an example of directed graph:\e[0m\n");
    
        LGraph *graph = funGraph.create((LVertex **)v, 6);
    
        // 添加边
        funGraph.edge.add(graph, 0, 1, 1, DIRECTED_GRAPH); // <A, B>
        funGraph.edge.add(graph, 0, 2, 1, DIRECTED_GRAPH); // <A, C>
        funGraph.edge.add(graph, 0, 3, 1, DIRECTED_GRAPH); // <A, D>
        funGraph.edge.add(graph, 1, 4, 1, DIRECTED_GRAPH); // <B, E>
        funGraph.edge.add(graph, 1, 5, 1, DIRECTED_GRAPH); // <B, F>
        funGraph.edge.add(graph, 2, 1, 1, DIRECTED_GRAPH); // <C, B>
        funGraph.edge.add(graph, 3, 4, 8, DIRECTED_GRAPH); // <D, E>
    
        // 显示邻接表
        printf("\nThe Adjacency List of the graph is :\n");
        funGraph.display(graph, 0);
    
        // 边的个数
        printf("\nThe number of Edge in the graph is : %d\n", funGraph.edge.count(graph, DIRECTED_GRAPH));
        // 顶点的度,参数为顶点在数组的下标
        printf("\nThe Degree of vertex 'B' is : %d\n", funGraph.vertex.dgree(graph, 1, DIRECTED_GRAPH));
        // 权值
        printf("\nThe Weight of Edge <D, E> is : %d\n", funGraph.edge.get(graph, 3, 4));
    
        funGraph.destroy(ungraph);
        funGraph.destroy(graph);
    
        printf("\n\e[1;32msystem exited with return code %d\e[0m\n\n", 0);
    
        return 0;
    }
    
    

      方便后续的测试与对照,上面测试案例中创建的图的显示效果如下图所示。

    2.4 测试案例中图的示意图

    2.4、测试效果

      本次测试是在 windows 环境下进行,也可以在 linux 环境下操作,详细说明在README.md中查看。

      使用 Cmake 编译,使用下面指令:

    mkdir build ; cd build
    在windows下使用    : cmake -G "MinGW Makefiles" .. # 注意 .. ,表示上级目录
    在linux下使用      : cmake -G "Unix Makefiles" .. # 注意 .. ,表示上级目录
    在linux下也可以使用 : cmake .. # 注意 .. ,表示上级目录
    make
    

      经过cmake编译之后,可以使用在当前目录下使用指令 ./../runtime/graph来运行可执行程序,也可以进入到目录runtime中,然后使用指令 ./graph ,即可运行测试程序。实际测试的结果如下图所示。

    2.5 测试案例显示的示意图

      
      至此,代码全部运行完成。

    三、逆邻接表

      一、逆邻接表

      逆邻接表指的是将顶点当弧头建立的邻接表,这样便于得到每个顶点的 入度 或者以此顶点为弧头的弧。

      有向图邻接表如下图所示。

    图3.1 逆邻接表示意图
      

      二、带权值的图(网)

      前面已经提到了,对于带有权值的边,只需要在边表节点的定义在增加一个数据域来存储权值即可。

      带权值的图如下图所示。

    图3.2 带权值的图示意图
      

    四、简单对比总结

       比较邻接矩阵、邻接点表的有确定,如下表所示。

    表4.1 对比表
    优点缺点
    邻接矩阵1、通用性强
    2、方便计算任意顶点的度(有向图中出度、入度)
    3、容易判断任意两个顶点之间是否存在边
    4、方便计算任意顶点的所有“邻接点”
    1、占用空间大
    2、对于稀疏图,空间利用率低
    3、对于有向图,空间利用率低
    邻 接 表1、方便查找任意顶点的所有“邻接点”
    2、对于稀疏图,节约空间
    3、对于无向图,方便计算任意顶点的度
    4、对于有向图,方便计算任意顶点的“出度”
    1、不易判断任意两个顶点之间是否存在边
    2、需要 N N N个头指针 + 2 E +2E +2E 个节点
    3、对于无向图,每条边都存储两次
    4、对于有向图,不易计算顶点的“入度”

      好啦,废话不多说,总结写作不易,如果你喜欢这篇文章或者对你有用,请动动你发财的小手手帮忙点个赞,当然 关注一波 那就更好了,好啦,就到这儿了,么么哒(*  ̄3)(ε ̄ *)。

    上一篇:数据结构(廿二) – C语言版 – 图 - 图的存储结构 – 邻接矩阵
    下一篇:数据结构(廿四) – C语言版 – 图 - 图的存储结构 – 十字链表、邻接多重表、 边集数组

    展开全文
  • 图的逆邻接表及由邻接表导出逆邻接表代码

    千次阅读 多人点赞 2018-12-14 10:48:57
    1.图的邻接表与逆邻接表直接看下图理解: 2.由邻接表导出逆邻接表代码: void Reverse(ALGraph A,ALGraph &amp;B) { int i,k; ArcNode *p1,*p2; B.vn=A.vn; B.en=A.en; for(i=1; i&lt;=A.vn; i++)...

     

    1.图的邻接表与逆邻接表直接看下图理解:

    2.由邻接表导出逆邻接表代码:

    void Reverse(ALGraph A,ALGraph &B)
    {
        int i,k;
        ArcNode *p1,*p2;
        B.vn=A.vn;
        B.en=A.en;
        for(i=1; i<=A.vn; i++)
        {
            scanf("%c",&B.adjlist[i].data);
            B.adjlist[i].firstarc=NULL;
        }
    
        for(i=1; i<=A.vn; i++)
        {
            p1=A.adjlist[i].firstarc;
            while(p1)
            {
                k=p1->adjvex;
                p2=(ArcNode *)malloc(sizeof(ArcNode));
                p2->adjvex=i;
                p2->nextarc=B.adjlist[k].firstarc;
                B.adjlist[k].firstarc=p2;
                p1=p1->nextarc;
            }
        }
    }
    

     

    展开全文
  • 邻接表和逆邻接表

    万次阅读 多人点赞 2019-09-16 14:39:31
    邻接表作为图的一种存储方式,在存储稀疏图上相对于邻接矩阵有相当大的空间节省。如一个稀疏图的顶点个个数为n,边数为e。用邻接矩阵存储需要n^2空间,而真正进行存储的只有2e个空间, 剩下的n^2-2e都浪费了。但是...

    邻接表作为图的一种存储方式,在存储稀疏图上相对于邻接矩阵有相当大的空间节省。如一个稀疏图的顶点个个数为n,边数为e。用邻接矩阵存储需要n^2空间,而真正进行存储的只有2e个空间, 剩下的n^2-2e都浪费了。但是对于邻接表来讲,存储空间只需要n+2e个,相对于邻接矩阵减少了很多。邻接表虽然在空间上有很大的优势,但是对于一个有向图,如果需要查找每个顶点的入度就需要遍历整个邻接表,在效率上很低下的。因此才有了逆邻接表的诞生。

    邻接表:反映的是顶点出度的情况。
    逆邻接表:反映的是顶点的入度情况。

    下面举一个例子:
    在这里插入图片描述
    邻接表:
    在这里插入图片描述
    逆邻接表:
    在这里插入图片描述

    展开全文
  • 图的链式结构主要有四类:邻接表、逆邻接表、十字链表、邻接多重表。 前两个算比较好理解的,后两个更复杂一点。 目录邻接表无向图的邻接表有向图的邻接表逆邻接表十字链表存储结构构造十字链表十字链表结构性质邻接...
  • C++邻接表,逆邻接表

    2021-03-20 15:50:20
    邻接表的创建与打印操作。
  • 数据结构:邻接表与逆邻接表

    千次阅读 2020-06-12 17:16:17
    邻接表是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表。比如有v1,v2,v3,v4,v5节点,就有5个单链表。单链表存储什么呢?存储头结点和紧跟着头结点的多个普通表结点。 图例: 好了现在知道...
  • 邻接表(逆邻接表)创建

    千次阅读 2020-08-29 09:01:52
    #include<cstdio> #include<iostream> #include<malloc.h> #define max_sum 30 using namespace std; typedef struct Arcnode{ int adjvex; struct Arcnode *nextarc;...}Vnod.
  • 有向图的邻接表转逆邻接表的算法

    千次阅读 2019-10-09 07:37:35
    //初始化逆邻接表顶点数目 gIn.arcnum = gOut.arcnum; //初始化逆邻接表边数目 for(int i = 0; i ; i++){ gIn.adjlist[i].vertex = gOut.adjlist[i].vertex;//构造逆邻接表顶点向量 gIn.adjlist[i]....
  • 邻接表的逆邻接表

    万次阅读 多人点赞 2017-11-13 21:30:00
    /*已知有向图采用邻接表存储,设计算法,求其逆邻接表。*/ #include #include #define max 20 typedef struct ArcNode{ int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧的指针 }...
  • 有向图的邻接矩阵、邻接表和逆邻接表

    万次阅读 多人点赞 2018-12-24 14:18:05
    1、如何根据有向图画出邻接矩阵?...画有向图的邻接表时,要看出边,即自身指向别人的边。 如图所示: 第一排的v1,指向v2和v3,因此两个黄色方框内的数字分别代表v2和v3的下标,即1和2; 第二排的v...
  • //初始化逆邻接表顶点数目 gIn.arcnum = gOut.arcnum; //初始化逆邻接表边数目 for(int i = 0; i ; i++){ gIn.adjlist[i].vertex = gOut.adjlist[i].vertex;//构造逆邻接表顶点向量 gIn.adjlist[i]....
  • 逆邻接表求有向图的度 邻接表,存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。图的...
  • 逆邻接表实现拓扑排序,能够更快速直接的计算顶点的入度,即终点指向结点,有几个边表,则代表入度是几
  • 使用邻接表和逆邻接表表示有向图,带权值表示。 #include #include #include #define MAXVEX 50 #define MAXWEIGHT 100 typedef int DataType ; typedef struct arc{/*边表结点类型*/ int adjvex;/*顶点序号*/ int ...
  • 邻接表和逆邻接表教程 讲述邻接表的详细知识
  • 邻接表与逆邻接表(数组实现)

    千次阅读 2013-05-10 09:41:19
    逆邻接表就是同时加两条边, 用一个pre数组记录逆边序号 #include #include #include #include #include #define CLR(a, val) memset(a, val, sizeof(a)) #pragma warning(disable:4996) using ...
  • 邻接表、逆邻接表

    2016-03-10 14:38:00
    邻接表(Adjacency List)是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个...可得到上图中的邻接表(可算出度)和逆邻接表(可算入度)。 转载于:https://www.cnblogs.com/xh0102/p/5261833.html...
  • 求单源最短路到其余各点,然后返回源点的总最短路长,以构造邻接表的方法不同分为两种解法。 POJ1511(ZOJ2008)-Invitation Cards  改变构造邻接表的方法后,分为两种解法 解法一: 1 //POJ1511-...
  • } } //将逆邻接表的各个节点链接 void Link_2(AdjList* G, VertexType v1, VertexType v2, int weight)//v1为弧尾,v2为弧头 { ArcNode* s = (ArcNode*)malloc(sizeof(ArcNode)); s->adjvex = v1; s->weight = ...
  • 已知有n个顶点的有向图G的邻接表,设计算法求邻接表G的逆邻接表
  • 图:邻接表、逆邻接表和十字链表

    千次阅读 2019-04-16 23:28:05
    文章目录邻接表数据结构建图、删图图的基本操作DFS遍历BFS遍历逆邻接表 邻接表 数据结构 邻接表由表头顶点表和顶点单链表构成: 表头节点表(顺序存储) 数据域 指针域 data firstarc data firstarc … ...
  • 邻接表使用邻接表存储图时,对于图中的每一个顶点和它相关的邻接点,都存储到一个链表中。每个链表都配有头结点,头结点的数据域不为NULL,而是用于存储顶点本身的数据;后续链表中的各个结点存储的是当前顶点的所有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,190
精华内容 2,476
关键字:

逆邻接表