邻接表的表示法 图的邻接矩阵表示法和图的邻接表的表示法区别
注意：
n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。(换句话说，每条边（i,j）在邻接表 中出现两次：一次在关于i的邻接表中，另一次在关于j的邻接表中) 对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。
【例】有向图G6如下图所示，其中顶点v1的邻接表上两个表结点中的顶点序号分别为0和4，它们分别表示从v1射出的两条边(简称为v1的出边)：<v1，v0>和<v1，v4>。
注意：
n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。（因为有向图是单向的） 在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。
入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。
【例】G6的逆邻表如上面(b)图所示，其中v0的入边表上两个表结点1和3分别表示射人v0的两条边(简称为v0的入边)：<v1，v0>和<v3，v0>。
注意：
n个顶点e条边的有向图，它的逆邻接表表示中有n个顶点表结点和e个边表结点。
3．邻接表的形式说明。
邻接表是一个二维容器，第一维描述某个点，第二维描述这个点所对应的边集们。
实现邻接表的方法绝对有100种以上。即使是前向星这种东西也是邻接表，因为它还是描述某个点和这个点所对应的边集们.
我们说说常用的邻接表存图法（静态的array就不说了.）必须有开O1以及以上编译的条件，不然没有测试的效率无任何意义。
第一维是描述点的。可以用vector,list,forward_list,deque,map,multimap,unordered_map,unordered_multimap等（一般不能用set,mutiset,unordered_set,unordered_multiset）.
按照你的要求去选择。一般来讲存完图以后不涉及点的加入与删除优先使用vector.map,multimap,unordered_map,unordered_multimap.
第二维是描述这个点的边集，可以用全部的容器。也是的一般来讲存完图以后,不涉及点的加入与删除优先使用vector,空间充足可以考虑deque.涉及点的删除用forward_list或者是list,map,multimap,unordered_map,unordered_multimap.
对于这个图存储的方法举例(对于上面的图):
第一种: #include <vector>#include <iostream>using namespace std;int main(){ vector<vector<size_t>> graph(5); graph[0].push_back(1);//V0->V1. graph[1].push_back(4);//V1->V4. graph[1].push_back(0);//V1->V0. graph[2].push_back(1);//V2->V1. graph[2].push_back(3);//V2->V3. graph[3].push_back(0);//V3->V0. graph[4].push_back(3);//V4->V3. //假定要访问点1. for(const auto &ele:graph[1])//对于全部属于graph[1]这个容器的元素 std::cout<<ele<<''; std::cout<<std::endl; //程序运行后输出40，表示点1连接了4点和0点。 return 0;}对第一种方法有种优化就是对每个点所对应的边的向量进行预估。例如有m条有向边，n个点，那么每个向量需要reserve(6*(m/n)/5);一般这样存储效率会有显著提高。
第二种(使用map,set): #include<map>#include<set>#include<iostream>#include<cstddef>#include<map>#include<set>intmain(){std::map<std::size_t,std::set<std::size_t>>graph;graph[0].insert(1);//V0->V1.graph[1].insert(4);//V1->V4.graph[1].insert(0);//V1->V0.graph[2].insert(1);//V2->V1.graph[2].insert(3);//V2->V3.graph[3].insert(0);//V3->V0.graph[4].insert(3);//V4->V3.//假定要访问点1.for(constauto&ele:graph[1])//对于全部属于graph[1]这个容器的元素std::cout<<ele<<'';std::cout<<std::endl;//程序运行后输出04，表示点1连接了0点和4点。对map,set里的元素进行遍历是有序的return0;}方法太多，不再举例了。
然而我们这样存图是不够的，对于无向图而言，可能存在一条边需要知道自己的反向边的位置。例如欧拉回路，例如网络流都是需要的。
第二种方法由于std::map<std::size_t,std::set<std::size_t>> graph;只是离散化后的邻接矩阵。对于这种存图方法，访问反向边则非常简单，例如我访问的是a->b这样一条边。那么只需要graph[b].count(a);就可以访问其反向边b->a。
然而对于第一种方法，我们没有办法解决反向边的互相访问题。
所以我们对于这种图需要存图修正。代码如下: #include<vector>#include<iostream>#include<utility>#include<cstddef>intmain(){std::vector<std::vector<std::pair<std::size_t,std::size_t>>>graph(5);//每条边的第二个元素不能是迭代器！！会失效！！！！必须是下标!!!//比如有一条a-b的边，我们得让它实现互访。我们这里假定a=2,b=4;std::size_ta(2),b(4);graph[a].push_back(std::make_pair(b,graph[b].size()+(a==b)));//Va->Vb.需要判定a是否等于b.graph[b].push_back(std::make_pair(a,graph[a].size()-1));//Vb->Va,这个不需要判定a是否等于b.//访问反向边的方法.for(constauto&ele:graph[a])//访问点agraph[ele.first][ele.second];//这就是边ele的反向边了return0;}对于list容器可以直接存迭代器的，但是存图时也得考虑a是否等于b.forward_list存反向边的图就不好，因为用链表存图就是需要存完图后插入删除，假定一个元素前面的元素被删除了，那么根本无法访问反向边!!!!
感觉存图没问题了？NO!!!!还有一种图更奇葩，那就是对于每个点中的边得排序又得知道反向边的那种图。USACO上有个题目叫做骑马修栅栏，那个题要求字典序输出。数据量很小，以至于可以直接矩阵存图，但是我们考虑如何数据量大，这种方法就不行了。如果用第二种方法(std::map<std::size_t,std::set<std::size_t>>)存图，绝对可可以，但是相对常数较大。如果我们考虑顺序容器去存储则比较快一些。
方法就是先用边集表存图，然后每条边a,b得优先以std::min(a,b)为第一关键字再按std::max(a,b)为第二关键字排序，再按照修正后的存图方法存图即可。具体代码见nocow上骑马修栅栏那题lgeecn发的题解和代码。
如果使用list存图可以先存图再用list.sort()函数进行排序，不过似乎效率会差一些,毕竟相对于vector,list常数太大了，达到6倍以上。
存图真心不简单，因为真正用的时候你可能会遇到各种问题，但是你可以加以思考，进行容器搭配使用，即可解决。
邻接表：顺序分配和链式分配的存储结构
图的邻接矩阵表示法和图的邻接表的表示法区别~
不知道
邻接表：顺序分配和链式分配的存储结构
相关要点总结：
17377982504：邻接表的表示法
姬钓答：（因为有向图是单向的） 在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。【例】G6的逆邻表如上面(b)图所示，其中v0的入边表上两个表结点1和3分别表示射人v0的两条边(简称为v0的入边)：<v1，v0>和<...
17377982504：图- 图的存储结构 - 邻接表表示法(一)
姬钓答：在有向图中 为图中每个顶点v i 建立一个入边表的方法称逆邻接表表示法 入边表中的每个表结点均对应一条以v i 为终点(即射入v i )的边 【例】G 的逆邻表如上面(b)图所示 其中v 的人边表上两个表结点 和 分别表示射人v 的两条边(简称为v 的入边) <v p=""> </v> 1 ，v 0 ...
17377982504：邻接表怎么画
姬钓答：邻接表是一种图的存储结构，通常用于表示稀疏图。画邻接表时，可以按照以下步骤进行：1.确定节点的个数和边的个数，以及节点和边的对应关系。2.按照边的顺序，画出每个节点及其相邻的节点。这里的节点可以是数字、字母或其它符号，具体表示根据需求而定。3.对于每个节点，只需画出与其相邻的节点，不需...
17377982504：有向图用邻接表如何表示,不是程序表示,求其详细的过程,
姬钓答：最后没有边的，指向就是空指针。第三步：依次按照A点的方法，写出BCDE点的指向的边的编号，没有就用空表示。理解的关键。邻接表数据的那个顶点和后面指向的编号的结点，这两个点的意思和写法不同，数组的表示的存储的具体的结点信息，后边的表示它发出的邻近结点的编号，没有其他的结点信息。
17377982504：有向图用邻接表如何表示,不是程序表示,求其详细的过程,
姬钓答：最后没有边的，指向就是空指针。第三步：依次按照A点的方法，写出BCDE点的指向的边的编号，没有就用空表示。理解的关键。邻接表数据的那个顶点和后面指向的编号的结点，这两个点的意思和写法不同，数组的表示的存储的具体的结点信息，后边的表示它发出的邻近结点的编号，没有其他的结点信息。
17377982504：如何用邻接表表示一个图?
姬钓答：使用栈来实现算法。用邻接表表示图进行深度优先遍历时，通常采用栈来实现算法，广度遍历使用队列。扩展材料：深度优先遍历：类似与树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到 注：优先访问外层节点，访问到无新...
17377982504：有向图的邻接表怎么画
姬钓答：1，观察有向图；2，画出矩阵框，并表示邻接点；3，从第一行开始画矩阵；4，通则写上路径长度，不同写上无穷大；5，依次画完剩余行，就画好了有向图的邻接矩阵。有向图的度：有向图入度是以顶点v为终点的有向边的数目，记为ID(v)；出度是以顶点v为起点的有向边的数目1，记为OD(v).顶点v...
17377982504：关于图的邻接表表示法的C语言描述
姬钓答：首先，我们来看一下整个定义的这个数据结构，它的名称是“vex”，它包含了2个量---字符型的“data”和“vex”型的指针*firstarc，因此箭头所标出来的那句中的“vex”的意思是*firstarc这个指针可以指向“vex”这种数据结构型的变量，所以如果表结点的数据结构类型也是“vex”的话，那么指针同样可以指向...
17377982504：c++中带权图的邻接表用stl怎么表示
姬钓答：struct Node { //定义表结点 int adjvex; //该边所指向的顶点的位置 int weight;// 边的权值 Node *next; //下一条边的指针 };struct HeadNode{ // 定义头结点 int nodeName; // 顶点信息 int inDegree; // 入度 Node *link; //指向第一条依附该顶点的边的指针 };//G表示指向头...
17377982504：邻接表的表示(运行代码要用c++的)急!!!
姬钓答：给你一个邻接表的完整程序:#include <iostream.h>struct node{ int data; node *next;};class list{ public: list(){head=NULL;}; void MakeEmpty(); int Length(); void Insert(int x,int i);//将x插入到第i个结点(不含头结点)的之后 void Insertlist(int a,int b);//将节点b插入a之前 int ...