邻接表 订阅
邻接表,存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点。 [1] 展开全文
邻接表,存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点。 [1]
信息
外文名
adjacency list
作    用
存储图
分    类
顺序分配和链式分配
中文名
邻接表
性    质
存储结构
邻接表简介
图的邻接表存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。如词条概念图所示,表结点存放的是邻接顶点在数组中的索引。对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点。 [1]  邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器(n个顶点建立n个容器),第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。在有向图中,描述每个点向别的节点连的边(点a->点b这种情况)。在无向图中,描述每个点所有的边(点a-点b这种情况)与邻接表相对应的存图方式叫做边集表,这种方法用一个容器存储所有的边。工业上有很多非常好的图库的实现,例如C++的boost graph库.如果可以,尽量用这些库,这样可以大大提高你的效率。
收起全文
精华内容
下载资源
问答
  • 邻接表
    万次阅读
    2021-05-17 10:02:56

    邻接表(顺序+链式存储)

    当一个图为稀疏图时,使用邻接矩阵表示显然要浪费大量的存储空间,而图的邻接表法结合了顺序存储和链式存储方法,大大减少了这种不必要的浪费。
    在这里插入图片描述

    #define MaxVertexNum 100; //图中顶点数目的最大值
    //"边/弧"
    typedef struct ArcNode{
        int adjvex; //边/弧指向哪个结点
        struct ArcNode *next; //指向下一条弧的指针
        //InfoType info; //边权值
    }ArcNode;
    //"顶点"
    typedef struct VNode{
        VertexType data; //顶点信息
        ArcNode *first; //第一条边/弧
    }VNode, AdjList[MaxVertexNum];
    //用邻接表存储的图
    typedef struct{
        AdjList vertices; //邻接表
        int vexnum, arcnum; //图的顶点数和弧数
    }ALGraph; //ALGraph是以邻接表存储图类型
    

    在这里插入图片描述

    邻接表

    邻接表,是指对图G中的每一个顶点vi建立一个单链表,第 i 个单链表中的结点表示依附于顶点 vi 的边(对于有向图则是以顶点vi为尾的弧),这个单链表就称为顶点vi的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(成为顶点表),所以在邻接表中存在两种:顶点表结点和边表结点。

    顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc)构成,边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc)构成。
    在这里插入图片描述
    ① 若G为无向图,则所需的存储空间为O(|V|+2|E|);若G为有向图,则所需的存储空间为O(|V|+|E|)。前者的倍数2是由于无向图中,每条边在邻接表中出现了两次。
    ② 对于稀疏图,采用邻接表表示将极大地节省存储空间。
    ③ 在邻接表中,给定一顶点,能很容易地找出它的所有邻边,因为只需要读取它的邻接表。在邻接表矩阵中,相同的操作则需要扫描一行,话费花费的时间为O(n)。但是,若要确定给定的两个顶点间是否存在边,则在邻接矩阵中立刻查到,而在邻接表中则需要在相应结点对应的边表中查找另一个结点,效率较低。
    ④ 在有向图的邻接表表示中,求一个给定顶点的出度只需要计算其邻接表中的结点个数;但求其顶点的入度则需要遍历全部的邻接表。因此,也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然,这实际上与邻接表存储方式是类似的。
    ⑤ 图的邻接表表示并不唯一,因为在每个顶点对应的单链表中,各边结点的链表次序可以是任意的,它取决于建立邻接表的算法及边的输入次序。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    更多相关内容
  • 本文实例为大家分享了C++实现邻接表顶点的删除代码,供大家参考,具体内容如下 这里的边是无向边 删除顶点v时,要找到顶点v的邻接顶点w,把w中指向v的边删除掉,再删除边(v,w)。循环这个过程,直到把和顶点v有关的...
  • 本文实例为大家分享了C++有向图的邻接表表示,供大家参考,具体内容如下 一、思路: 有向图的插入有向边、删除边、删除顶点和无向图的有区别。其他的和无向图的类似。 1.插入有向边 只需要插入边就行,不需要插入...
  • 领会图的两种主要存储结构、图基本运算算法和两种遍历算法设计内容:编写一个程序,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序完成如下功能:(1)建立如图所示的有向图G的邻接矩阵...
  • 头歌数据结构图的邻接表存储及遍历操作 第1关图的邻接表存储及求邻接点操作 第2关图的深度遍历 第3关图的广度遍历 稳过
  • 主要介绍了java实现图的邻接表存储结构的两种方式及实例应用详解,邻接表构建图是必须需要一个Graph对象,也就是图对象!该对象包含属性有:顶点数、边数以及图的顶点集合,需要的朋友可以参考下
  • 学习数据结构和离散数学的同学, 这是我的理解和相关代码
  • 主要为大家详细介绍了C++实现有向图邻接表的构建,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 图的邻接表实现.rar

    2020-05-25 22:22:26
    C++实现图的邻接表,利用了类模板,可以构建有向图和无向图,包含链表、图的ADT,里面附有说明文档,详细说明了主程序的测试方式。
  • 本文实例为大家分享了C++数据结构之实现邻接表的具体代码,供大家参考,具体内容如下 一、图的邻接表实现 1.实现了以顶点顺序表、边链表为存储结构的邻接表; 2.实现了图的创建(有向/无向/图/网)、边的增删操作、...
  • 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历 数据结构图的邻接矩阵,邻接表存储表示,图的深度优先搜索遍历,广度优先搜索遍历.rar
  • 自行实现图的邻接矩阵和邻接表存储结构 邻接矩阵类和邻接表类的实现及测试函数 功能全 代码易理解 可直接运行
  • 将一个无向图的邻接表转换为邻接矩阵算法.doc.doc
  • 邻接矩阵存储的结构体中,包括一个存储边的结构体,存储每条边的信息(权值)将这个边的结构体的二维数组作为图的基本存储结构,放到单个图的结构体中每个图又包含总节点数、总边数、图的类型等信息
  • 图的邻接矩阵和邻接表实现, 深度搜索, 广度搜索, Dijstra最短路径
  • 采用邻接表来实现图的存储,并输入输出邻接表的信息,并用邻接表来实现图的广度优先遍历。
  • 图的邻接表 邻接矩阵表示的迪杰斯特拉算法 普里姆算法 克鲁斯卡尔算法 用c++实现 codeblocks编译通过
  • C语言采用邻接表结构实现克鲁斯卡尔算法。 也可以在相应github上下载,https://github.com/Sunnk/Data-Structure,其中Kruskal文件夹中即为克鲁斯卡尔算法,可用vs打开
  • 数据结构 c++ 图的最短路径问题 (邻接表) 数据结构 c++ 图的最短路径问题 (邻接表)
  • 代码如下://———图的邻接表存储表示——- #include<stdio>#include #define MAX_VERTEXT_NUM 20 typedef int InfoType;typedef char VertextType; typedef struct ArcNode{ int adjvex; struct ArcNode *nextArc...
  • 邻接表存储的图

    2019-08-25 14:20:25
    1、 定义邻接表存储的图类。 2、 实验验证如下算法的正确性、各种功能及指标: 1)创建一个邻接表存储的图; 2)返回图中指定边的权值; 3)返回图中某顶点的第一个邻接顶点; 4)返回图中某顶点关于另一个顶点的下...
  • 一个完整的有向图课程设计,一共含有20个方法。分享给大家一起学习。
  • 邻接表的介绍以及邻接表的代码实现

    邻接表 

    邻接矩阵的实现请看这里

    是不错的一种图存储结构,但是,对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费。因此,找到一种数组与链表相结合的存储方法称为邻接表
    邻接表的处理方法是这样的:

    • (1)图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过,数组可以较容易的读取顶点的信息,更加方便。
    • (2)图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以,用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表。
      例如,下图就是一个无向图的邻接表的结构。

    从图中可以看出,顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针。
    对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可。如下图所示。 

    代码实现邻接表(有向邻接表图) 基于C++

    /**
     * C++: 邻接表图
     *
     * @author lph
     * 
     */
    
    #include <iomanip>
    #include <iostream>
    #include <vector>
    using namespace std;
    
    #define MAX 100
    // 邻接表
    class ListDG {
    private: // 内部类
    	// 邻接表中表对应的链表顶点
    	class ENode {
    	public:
    		int ivex;			// 该边所指向的顶点的位置
    		ENode* nextEdge;	// 指向下一条弧的指针
    	};
    
    	// 邻接表中表的顶点
    	class VNode {
    	public:
    		char data;			//顶点信息
    		ENode* firstEdge;	//指向第一条依赖该顶点的弧
    	};
    
    private: // 私有成员
    	int mVexNum;			//图的顶点的数目
    	int mEdgNum;			//图的边的数目
    	VNode mVexs[MAX];		//用一维数组来存储邻接表的顶点
    
    public:
    	// 创建邻接表对应的图(自己输入)
    	ListDG();
    	// 创建邻接表对应的图(用已经提供的数据)
    	ListDG(char vexs[], int vlen, char edges[][2], int elen);
    	~ListDG();
    
    	// 打印邻接表图
    	void print();
    
    private:
    	// 读取一个输入字符
    	char readChar();
    	// 返回ch的位置
    	int getPosition(char ch);
    	// 将node节点链接到List的最后
    	void linkLast(ENode* list, ENode* node);
    };
    
    /*
    * 创建邻接表对应的图(自己输入)
    */
    ListDG::ListDG() {
    	char c1, c2;
    	int v, e;
    	int i, p1, p2;
    	ENode* node1, * node2;
    
    	// 输入顶点数和边数
    	cout << "input vertex number: ";
    	cin >> mVexNum;
    	cout << "input edge number: ";
    	cin >> mEdgNum;
    	if (mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum - 1)))) {
    		cout << "input error: invalid parameters! " << endl;
    		return;
    	}
    
    	// 初始化邻接表的顶点
    	for (i = 0; i < mVexNum; ++i) {
    		cout << "vertex(" << i << "):";
    		mVexs[i].data = readChar();
    		mVexs[i].firstEdge = nullptr;
    	}
    
    	// 初始化邻接表的边
    	for (i = 0; i < mEdgNum; ++i) {
    		// 读取边的起始点和结束顶点
    		cout << "edge(" << i << "):";
    		c1 = readChar();
    		c2 = readChar();
    
    		p1 = getPosition(c1);
    		p2 = getPosition(c2);
    		// 初始化node1
    		node1 = new ENode();
    		node1->ivex = p2;
    		// 将node1链接到p1所在链表的末尾
    		if (mVexs[p1].firstEdge == nullptr)
    			mVexs[p1].firstEdge = node1;
    		else
    			linkLast(mVexs[p1].firstEdge, node1);
    	}
    }
    
    /*
    	创建邻接表对应的图(用已经提供的数据)
    */
    ListDG::ListDG(char vexs[], int vlen, char edges[][2], int elen) {
    	char c1, c2;
    	int i, p1, p2;
    	ENode* node1, * node2;
    
    	// 初始化顶点数和边数
    	mVexNum = vlen;
    	mEdgNum = elen;
    	// 初始化"邻接表"的顶点
    	for (i = 0; i < mVexNum; i++)
    	{
    		mVexs[i].data = vexs[i];
    		mVexs[i].firstEdge = NULL;
    	}
    	// 初始化邻接表的边
    	for (i = 0; i < mEdgNum; ++i) {
    		// 读取边的起始顶点和结束顶点
    		c1 = edges[i][0];
    		c2 = edges[i][1];
    
    		p1 = getPosition(c1);
    		p2 = getPosition(c2);
    		// 初始化node1
    		node1 = new ENode();
    		node1->ivex = p2;
    		// 将node1链接到p1所在链表的末尾
    		if (mVexs[p1].firstEdge == nullptr)
    			mVexs[p1].firstEdge = node1;
    		else
    			linkLast(mVexs[p1].firstEdge, node1);
    	}
    }
    
    /*
    	析构函数
    */
    ListDG::~ListDG() {
    	
    }
    /*
    	将node节点连接到List最后
    */ 
    void ListDG::linkLast(ENode* list, ENode* node) {
    	ENode* p = list;
    
    	while (p->nextEdge)
    		p = p->nextEdge;
    	p->nextEdge = node;
    }
    
    /*
    	返回ch的位置
    */
    int ListDG::getPosition(char ch) {
    	int i;
    	for (i = 0; i < mVexNum; ++i) 
    		if (mVexs[i].data == ch)
    			return i;
    		return -1; // 失败返回-1
    	
    }
    
    /*
    	读取一个输入字符
    */
    char ListDG::readChar() {
    	char ch;
    	do {
    		cin >> ch;
    	} while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));
    	return ch;
    }
    
    /*
    	打印邻接表图
    */
    void ListDG::print() {
    	int i, j;
    	ENode* node;
    	cout << "List Graph: " << endl;
    	for (i = 0; i < mVexNum; ++i) {
    		cout << i << "(" << mVexs[i].data << "):";
    		node = mVexs[i].firstEdge;
    		while (node != nullptr) {
    			cout << node->ivex << "(" << mVexs[node->ivex].data << ") ";
    			node = node->nextEdge;
    		}
    		cout << endl;
    	}
    }
    int 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;
    
    	// 自定义图(输入矩阵队列)
    	// pG = new ListDG();
    	// 采用已经有的图
    	pG = new ListDG(vexs, vlen, edges, elen);
    
    	pG->print();
    	return 0;
    	
    }

    用已经有的数据运行代码后的结果(有向邻接表图)为:

    用自己手动输入数据的结果(有向邻接表图)

    邻接表的实现(无向邻接表图 :

    /*
    	C++: 邻接表表示的"无向图(List Undirected Graph)"
    	@author lph
    	
    */
    #include <iomanip>
    #include <iostream>
    #include <vector>
    using namespace std;
    
    constexpr auto MAX = 100;
    // 邻接表;
    class ListUDG {
    private:
    	// 内部类
    	// 邻接表中表对应的链表的顶点
    	class ENode {
    	public:
    		int ivex;		// 该边所指向的顶点的位置
    		ENode* nextEdge;// 指向下一条弧的指针
    	};
    	// 邻接表中表对应的顶点
    	class VNode {
    	public:
    		char data;		// 顶点信息
    		ENode* firstEdge;// 指向第一条依赖该顶点的弧
    	};
    private:
    	int mVexNum;		// 图的顶点个数
    	int mEdgNum;		// 图的边的数目
    	VNode mVexs[MAX];  // 一维数组存储图的顶点,也就是邻接表第一列的顶点
    public:
    	// 创建邻接表对应的图(自己输入)
    	ListUDG();
    	// 创建邻接表对应的图(用已经提供的数据)
    	ListUDG(char vexs[], int vlen, char edges[][2], int elen);
    	// 析构函数
    	~ListUDG();
    	// 打印邻接表图
    	void print();
    private:
    	// 读取一个输入字符
    	char readChar();
    	// 返回ch的位置
    	int getPosition(char ch);
    	// 将node节点链接到list的最后
    	void linkLast(ENode* list, ENode* node);
    };
    /*
    	创建邻接表对应的图(自己输入)
    */
    ListUDG::ListUDG() {
    	char c1, c2;
    	// int v, e;
    	int i, p1, p2;
    	ENode* node1, * node2;
    	// 输入顶点数和边数
    	cout << "input vertex number: ";
    	cin >> mVexNum;
    	cout << "input edge number: ";
    	cin >> mEdgNum;
    	if (mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum - 1)))) {
    	cout << "input error: invalid parameters!" << endl;
    	return;
    }
    	// 初始化邻接表的顶点
    	for (i = 0; i < mVexNum; ++i) {
    		cout << "vertex(" << i << "):";
    		mVexs[i].data = readChar(); // 如果mVexs在之前用的是VNode* mVexs[MAX],那么这里需要用指针mVexs[i]->data
    		mVexs[i].firstEdge = nullptr;
    	}
    	// 初始化邻接表的边
    	for (i = 0; i < mEdgNum; ++i) {
    		// 读取边的起点和结束顶点
    		cout << "edge(" << i << "):";
    		c1 = readChar();
    		c2 = readChar();
    
    		p1 = getPosition(c1);
    		p2 = getPosition(c2);
    		// 初始化node1
    		node1 = new ENode();
    		node1->ivex = p2;
    		// 将node1链接到p1所在链表的末尾
    		if (mVexs[p1].firstEdge == nullptr)
    			mVexs[p1].firstEdge = node1;
    		else
    			linkLast(mVexs[p1].firstEdge, node1);
    		// 初始化node2
    		node2 = new ENode();
    		node2->ivex = p1;
    		// 将node2链接到p2所在链表的末尾
    		if (mVexs[p2].firstEdge == nullptr)
    			mVexs[p2].firstEdge = node2;
    		else
    			linkLast(mVexs[p2].firstEdge, node2);
    	}
    }
    /*
    	创建邻接表对应的图(用已提供的数据)
    */
    ListUDG::ListUDG(char vexs[], int vlen, char edges[][2], int elen) {
    	char c1, c2;
    	int i, p1, p2;
    	ENode* node1, * node2;
    	// 初始化顶点数和边数
    	mVexNum = vlen;
    	mEdgNum = elen;
    	// 初始化邻接表的顶点
    	for (i = 0; i < mVexNum; ++i) {
    		mVexs[i].data = vexs[i];
    		mVexs[i].firstEdge = nullptr;
    	}
    	// 初始化邻接表的边
    	for (i = 0; i < mEdgNum; ++i) {
    		// 读取边的起始顶点和结束顶点
    		c1 = edges[i][0];
    		c2 = edges[i][1];
    
    		p1 = getPosition(c1);
    		p2 = getPosition(c2);
    		// 初始化node1
    		node1 = new ENode();
    		node1->ivex = p2;
    		// 将node1链接到p1所在的末尾
    		if (mVexs[p1].firstEdge == nullptr)
    			mVexs[p1].firstEdge = node1;
    		else
    			linkLast(mVexs[p1].firstEdge, node1);
    		// 初始化node2
    		node2 = new ENode();
    		node2->ivex = p1;
    		// 将node2链接到p2所在链表的末尾
    		if (mVexs[p2].firstEdge == nullptr)
    			mVexs[p2].firstEdge = node2;
    		else
    			linkLast(mVexs[p2].firstEdge, node2);
    	}
    }
    /*
    	析构函数
    */
    ListUDG::~ListUDG() {
    
    }
    /*
    	将node节点连接到list最后
    */
    void ListUDG::linkLast(ENode* list, ENode* node) {
    	ENode* p = list;
    	while (p->nextEdge)
    		p = p->nextEdge;
    	p->nextEdge = node;
    }
    /*
    	返回ch的位置
    */
    int ListUDG::getPosition(char ch) {
    	int i;
    	for (i = 0; i < mVexNum; ++i) 
    		if (mVexs[i].data == ch)
    			return i;
    	return -1;
    }
    /*
    	读取一个输入字符
    */
    char ListUDG::readChar() {
    	char ch;
    	do {
    		cin >> ch;
    	} while  (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));
    	return ch;
    }
    
    /*
    	打印邻接表图
    */
    void ListUDG::print() {
    	int i, j;
    	ENode* node;
    	cout << "List Graph:" << endl;
    	for (i = 0; i < mVexNum; ++i) {
    		cout << i << "(" << mVexs[i].data << ")";
    		node = mVexs[i].firstEdge;
    		while (node != nullptr) {
    			cout << node->ivex << "(" << mVexs[node->ivex].data << ")";
    			node = node->nextEdge;
    		}
    		cout << endl;
    	}
    }
    int 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;
    
    	// 自定义"图"(输入矩阵队列)
    	//pG = new ListUDG();
    	// 采用已有的"图"
    	pG = new ListUDG(vexs, vlen, edges, elen);
    
    	pG->print();   // 打印图
    	
    	return 0;
    }

    打印已提供邻接表(无向邻接表图)数据的结果: 

     打印自己输入的邻接表(无向邻接表图)的数据:

     

    邻接矩阵的实现请看这里

    展开全文
  • 1.生成一个100个点,3000条边的有向随机图,任选一点作为源点,计算S到其他节点的距离。(注:图用邻接链表存储) 2.将实验一中的有向图变为DAG图。(从中去掉一些边,不允许用递归) 计算上述DAG图中的最长路径。
  • 在Windows7 64位+VS2015上运行求解AOE网关键路径的算法,邻接表表示的AOE网提示网中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?
  • NULL 博文链接:https://128kj.iteye.com/blog/1694918

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 93,967
精华内容 37,586
关键字:

邻接表

友情链接: 2.zip