图的邻接表存储的表示
❶ 邻接表的简介
图的邻接矩阵存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如词条概念图所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。
邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。
在有向图中，描述每个点向别的节点连的边（点a->点b这种情况）。
在无向图中，描述每个点所有的边(点a-点b这种情况)
与邻接表相对应的存图方式叫做边集表，这种方法用一个容器存储所有的边。
工业上有很多非常好的图库的实现,例如C++的boost graph库.如果可以，尽量用这些库，这样可以大大提高你的效率。
❷ 如何用邻接表存储图结构
我看不太懂这个程序，不过我有些过图的邻接表表示，看对你有没有帮助吧。
#include <iostream>
#include <fstream>
#include <vector>
typedef int QElemTyep;
#include "queue.h"
using namespace std;
typedef int Status;
#define MAX_VERTEX_NUM 30 //图的最大顶点数
enum BOOL {False,True};
BOOL visited[MAX_VERTEX_NUM]; //全局变量--访问标志数组
typedef struct ArcNode{
//弧结点
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
InfoType *info; //保存边的信息，可以简单的改为 int w;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
class Graph{
public: AdjList vertices; //记录顶点信息，指向第一条依附该顶点的弧的指针
int vexnum,arcnum; //图的当前顶点和弧数
int GraphKind; //图的种类，0---无向图，1---有向图
Graph(int vexnum,int arcnum,int kind)
{
this->vexnum=vexnum;
this->arcnum=arcnum;
this->GraphKind=kind;
}
};
void CreateGraph(Graph &G,VertexType *V,ArcType *VR){
//构造邻接表结构的图G
int i;
ArcNode *s;
for(i=1;i<=G.vexnum;i++) //初始化指针数组
{
G.vertices[i].data=V[i];
G.vertices[i].firstarc=NULL;
}
for(i=1;i<=G.arcnum;i++)
{
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个弧结点
s->nextarc=G.vertices[VR[i].start].firstarc; //插入到邻接表中
s->adjvex=VR[i].end;
G.vertices[VR[i].start].firstarc=s;
if(G.GraphKind==0) {
//若是无向图，再插入到终点的弧链中
s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.vertices[VR[i].end].firstarc;
s->adjvex=VR[i].start;
G.vertices[VR[i].end].firstarc=s;
}
}
}
❸ 用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法
使用栈来实现算法。
用邻接表表示图进行深度优先遍历时，通常采用栈来实现算法，广度遍历使用队列。
扩展材料：
深度优先遍历：类似与树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到
注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点。
广度优先遍历：类似于树的层序遍历。从图中的某个顶点w出发，让顶点w入队，然后顶点w再出队，并让所有和顶点w相连的顶点入队，然后再出队一个顶点t，并让所有和t相连但未被访问过的顶点入队……由此循环，指定图中所有元素都出队。
参考资料来源：
知网论文-数据结构中图的遍历算法研究
❹ 在用邻接表表示图时,对图进行深度优先搜索遍历的算法的时间复杂度为()
因为当相邻矩阵的大部分被破坏时，矩阵中的所有元素都需要扫并追踪到，且元素个数为n＾2，自然算法为O（n＾2）。
所以邻接表只存储边或弧，如果扫描邻接表，当然会得到O（n＋e）其中n是顶点的数量，e的边或弧的数量。
设有n个点，e条边
邻接矩阵：矩阵包含n＾2个元素，在算法中共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O（n＾2）。
邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为O（n+e）顺便，对于广度优先算法的时间复杂度，也是这样。
(4)图的邻接表存储的表示扩展阅读：
邻接表是图的最重要的存储结构之一，描述了图上的每个点。创建一个容器对于每一个图的顶点（n顶点n容器）和节点在第i个容器包含所有相邻顶点的顶点Vi。事实上，我们经常使用的邻接矩阵是一个邻接表的边集不离散化每一个点。
在有向图中，描述每个点与另一个节点连接的边(在a点->点B)。
在无向图中，描述每个点上的所有边（A点和B点的情况）
邻接表对应的图存储方法称为边集表。此方法将所有边存储在容器中。
❺ 图的存储结构——所存储的信息有哪些
一、邻接矩阵存储方法
邻接矩阵是表示顶点之间相邻关系的矩阵。
设G=(V，E)是具有n（n＞0）个顶点的图，顶点的顺序依次为0～n-1，则G的邻接矩阵A是n阶方阵，其定义如下：
（1）如果G是无向图，则：
A[i][j]=1：若(i,j)∈E(G) 0:其他
（2）如果G是有向图，则：
A[i][j]=1：若<i,j>∈E(G) 0:其他
（3）如果G是带权无向图，则：
A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他
（4）如果G是带权有向图，则：
A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他
注意：带权图和不带权图表示的元素类型不同。
带权图（不论有向还是无向图）A[i][j]用double表示，不带权图（不论有向还是无向图）A[i][j]用int表示。
用一维数组G[ ]存储有4个顶点的无向图如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
则顶点2和顶点0之间是有边的。
如：
邻接矩阵的特点如下：
（1）图的邻接矩阵表示是唯一的。
（2）无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上（或下）三角形阵的元素即可。
（3）不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵。因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。
（4）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。
（5）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。
（6）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。
邻接矩阵的数据类型定义如下：
#define MAXV <最大顶点个数>
typedef struct
{ int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct //图的定义
{ int edges[MAXV][MAXV]; //邻接矩阵
int n，e; //顶点数，弧数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵表示类型
二、 邻接表存储方法
图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。
在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。
其中，表节点由三个域组成，adjvex指示与顶点i邻接的点在图中的位置，nextarc指示下一条边或弧的节点，info存储与边或弧相关的信息，如权值等。
表头节点由两个域组成，data存储顶点i的名称或其他信息，firstarc指向链表中第一个节点。
typedef struct ANode
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
InfoType info; //该边的相关信息
} ArcNode; //边表节点类型
typedef struct Vnode
{ Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode; //邻接表头节点类型
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //完整的图邻接表类型
邻接表的特点如下：
（1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。
（2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。
（3）对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。
（4）对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。
例， 给定一个具有n个节点的无向图的邻接矩阵和邻接表。
（1）设计一个将邻接矩阵转换为邻接表的算法；
（2）设计一个将邻接表转换为邻接矩阵的算法；
（3）分析上述两个算法的时间复杂度。
解：
（1）在邻接矩阵上查找值不为0的元素，找到这样的元素后创建一个表节点并在邻接表对应的单链表中采用前插法插入该节点。
void MatToList(MGraph g，ALGraph *&G)
//将邻接矩阵g转换成邻接表G
{ int i，j，n=g.n; ArcNode *p; //n为顶点数
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<n;i++) //给所有头节点的指针域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //检查邻接矩阵中每个元素
for (j=n-1;j>=0;j--)
if (g.edges[i][j]!=0)
{ p=(ArcNode *)malloc(sizeof(ArcNode));
//创建节点*p
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
//将*p链到链表头
G->adjlist[i].firstarc=p;
}
G->n=n;G->e=g.e;
}
（2）在邻接表上查找相邻节点，找到后修改相应邻接矩阵元素的值。
void ListToMat(ALGraph *G，MGraph &g)
{ int i，j，n=G->n;ArcNode *p;
for (i=0;i<n;i++)
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ g.edges[i][p->adjvex]=1;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
（3）算法1的时间复杂度均为O(n2)。算法2的时间复杂度为O(n+e)，其中e为图的边数。
❻ 有向图的邻接表存储如图所示，请画出其邻接矩阵存储结构
有向图的邻接表存储如图所示，其邻接矩阵存储如图：
❼ 邻接表的表示法
注意：
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>usingnamespacestd;intmain(){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(constauto&ele:graph[1])//对于全部属于graph[1]这个容器的元素std::cout<<ele<<'';std::cout<<std::endl;//程序运行后输出40，表示点1连接了4点和0点。return0;}对第一种方法有种优化就是对每个点所对应的边的向量进行预估。例如有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倍以上。
存图真心不简单，因为真正用的时候你可能会遇到各种问题，但是你可以加以思考，进行容器搭配使用，即可解决。