图的邻接表存储及遍历

Ⅰ 采用邻接表存储的图的深度优先遍历算法类似于二叉树的先序遍历，为什么是先序呢

这是因为图的深度优先遍历算法先访问所在结点，再访问它的邻接点。与二叉树的先序遍历先访问子树的根结点，再访问它的孩子结点（邻接点）类似。图的广度优先遍历算法类似于二叉树的按层次遍历。

先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。

首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

例如，下图所示二叉树的遍历结果是：ABDECF。

(1)图的邻接表存储及遍历扩展阅读：

遍历种类：

一、NLR：前序遍历(Preorder Traversal 亦称（先序遍历）），访问根结点的操作发生在遍历其左右子树之前。

二、LNR：中序遍历(Inorder Traversal)，访问根结点的操作发生在遍历其左右子树之中（间）。

三、LRN：后序遍历(Postorder Traversal)，访问根结点的操作发生在遍历其左右子树之后。

注意：

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为 先根遍历、中根遍历和后根遍历。

Ⅱ n个顶点e条边的图G用邻接表存储，则求每个顶点入度的时间复杂度为查了好几个地方的答案，答案大部分

O(n+e)是对的，O(n*n)是用邻接矩阵存储时的时间复杂度。
算法就是遍历每一条边，然后把每条边的终点的入度+1.
在邻接表中，就是要依次访问每个顶点，然后在每个顶点中依次访问每条边，把这些边的终点的入度+1。也就是每个顶点和每条边依次要各访问一遍，所以时间复杂度是O(n+e)。
在邻接矩阵中，算法需要遍历邻接矩阵的每一个点，而邻接矩阵有n*n个点，所以时间复杂度是O(n*n)。
有什么不懂的可以追问。

Ⅲ 如下图表示的是用邻接表存储的图，画出此图，并写出从A点开始按广度优先算法遍历该图的结果（附上过程）

广度优先遍历：ABDFEC
1、A的邻接点B和D
2、B的邻接点D和F，D已经遍历，只访问F
3、D的邻接点E
4、F的邻接点E，已经遍历
5、E无邻接点
6、最后扫描所有头结点C未访问，再从C开始遍历，C的邻接点DA都已遍历。

Ⅳ 在用邻接表表示图时,对图进行深度优先搜索遍历的算法的时间复杂度为()

因为当相邻矩阵的大部分被破坏时，矩阵中的所有元素都需要扫并追踪到，且元素个数为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点的情况）

邻接表对应的图存储方法称为边集表。此方法将所有边存储在容器中。

Ⅳ 邻接表存储时，空间复杂度O( n+e)，还是O(n)

O(n+e)，取n次最小权，每次取完会进行n次更新。如果能达到o（n+e），就不需要O(n)。

在有向图中，描述每个点向别的节点连的边（点a->点b这种情况）。在无向图中，描述每个点所有的边。与邻接表相对应的存图方式叫做边集表，这种方法用一个容器存储所有的边。

对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。

(5)图的邻接表存储及遍历扩展阅读：

n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。（因为有向图是单向的）

在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。

n个顶点e条边的有向图，它的逆邻接表表示中有n个顶点表结点和e个边表结点。

Ⅵ 图的邻接表的时间复杂度问题

其实是O(n + e)，顶点加上边数
那个O(n*e)的意思是每次插入一条边，都需要重新查找边所包含两个顶点信息对应的下标，正常的算法没这么弱智吧，不需要顶点信息即为顶点的下标，用散列等方法可以不用这样的
用邻接矩阵构造图时，若存储的是一个无向图，则时间复杂度为O(n^2 + n*e)，其中，对邻接矩阵的初始化耗费的时间为O(n^2);
对于DFS,BFS遍历来说，时间复杂度和存储结构有关：
n表示有n个顶点，e表示有e条边。
1.若采用邻接矩阵存储，
时间复杂度为O(n^2);
2.若采用邻接链表存储，建立邻接表或逆邻接表时，

若输入的顶点信息即为顶点的编号，则时间复杂度为O(n+e);
若输入的顶点信息不是顶点的编号，需要通过查找才能得到顶点在图中的位置，则时间复杂度为O(n*e);

Ⅶ c语言图的遍历，邻接表存储，深度，广度优先遍历

（1） 图的建立，按采用邻接表作为存储结构。
（2） 从指定顶点出发进行深度优先搜索遍历。
（3） 从指定顶点出发进行广度优先搜索遍历。

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"

#define MAX_INT 1000
#define MAX_VERTEX_NUM 20
#define MAX_QUEUE_NUMBER 20

typedef struct ArcNode
{
int adjvex;
double adj;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VexNode
{
char szName[40];
ArcNode *firstarc;
}VexNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vexs;
int vexnum,arcnum;
}Net;
//定义队列
typedef struct{
int *elem;
int front, rear;
}Queue;
void InitQueue(Queue &Q)
{
Q.elem = new int[MAX_QUEUE_NUMBER];
Q.front = Q.rear = 0;
}
int EmptyQueue(Queue Q)
{
if(Q.front==Q.rear)
return 0;
else
return 1;
}
void DestroyQueue(Queue &Q){
delete []Q.elem;
Q.front = Q.rear = 0;
}

void EnterQueue(Queue &Q, int e)
{
if((Q.rear + 1)%MAX_QUEUE_NUMBER != Q.front)
Q.elem[Q.rear ] = e;
else
printf("队列满!\n");
Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;
}
void LeaveQueue(Queue &Q, int &e)
{
if(Q.rear != Q.front)
e = Q.elem[Q.front];
else
printf("队列空!\n");
Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;
}
int LocateVex(Net ga,char *name)
{
int i;
for(i=0;i<ga.vexnum;i++)
if(strcmp(name,ga.vexs[i].szName)==0)
return i;
return -1;

}
void crt_net(Net &ga)
{
ArcNode *p;
char name1[40],name2[40];
int i,j,k;
double w;
printf("请输入顶点数和弧数：");
scanf("%d%d",&ga.vexnum,&ga.arcnum);
printf("请依次输入顶点名：\n");
for(i=0;i<ga.vexnum;i++)
{
scanf("%s",ga.vexs[i].szName);
ga.vexs[i].firstarc=NULL;
}
for(k=0;k<ga.arcnum;k++)
{
printf("请输入相邻的两个定点和权值：");
scanf("%s%s%lf",name1,name2,&w);
i=LocateVex(ga,name1);
j=LocateVex(ga,name2);
p=new ArcNode;
p->adjvex=j;
p->adj=w;
p->nextarc=ga.vexs[i].firstarc;
ga.vexs[i].firstarc=p;
}
}

void DFS(Net ga,char *name,int *visited)
{
int v,w;
ArcNode *p;
v=LocateVex(ga,name);
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
p=ga.vexs[v].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
DFS(ga,ga.vexs[w].szName,visited);
p=p->nextarc;
}

}
void DFSTravel(Net ga,char *name)
{
int v,k=0;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
DFS(ga,ga.vexs[v].szName,visited);

}
}

void BFSTravel(Net ga,char *name)
{
ArcNode *p;
int v,w,u,k=0;
Queue Q;
int visited[20];
for(v=0;v<ga.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1))
{
if(v+1==LocateVex(ga,name))
k++;
if(visited[v]==0)
{
visited[v]=1;
printf("%s ",ga.vexs[v].szName);
EnterQueue(Q,v);
while(EmptyQueue(Q)!=0)
{
LeaveQueue(Q,u);
p=ga.vexs[u].firstarc;
while(p!=NULL)
{
w=p->adjvex;
if(visited[w]==0)
{
printf("%s ",ga.vexs[w].szName);
visited[w]=1;
EnterQueue(Q,w);
}
p=p->nextarc;
}
}
}

}
}

void main()
{
char name[40];
Net ga;
crt_net(ga);
printf("请输入深度优先遍历开始点的名：");
scanf("%s",name);
printf("深度优先遍历：");
DFSTravel(ga,name);
printf("\n");
printf("请输入广度优先遍历开始点的名：");
scanf("%s",name);
printf("广度优先遍历：");
BFSTravel(ga,name);
printf("\n");

}