数据结构中邻接矩阵邻接表的时间复杂度

对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一 种遍历时，其时间复杂度为——。（ O（n^2） O(e) ）
用邻接表来表示图，有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度不应该是O（n+e）吗

邻接矩阵是将图中所有边和点的关系用二维数组表示，其矩阵大小为n*n，其中n为顶点数，可以跟据顶点之间是否相连填0/1或者权重值。遍历时需要扫描整个矩阵，因此时间复杂度为O(n^2)。而邻接表是将每个顶点与其相邻的点记录在链表中，整个图由若干条链表表示。遍历时只需要访问链表中的n个头结点和e个表结点，总的时间复杂度为O(n+e)。因此，对于边稠密的图，邻接矩阵的时间复杂度更佳，而对于边稀疏的图，邻接表更加适合。

举个例子，假设有一个无向图，有n个顶点，边为e条。可以考虑一个图来描述人与人之间的交往关系，每个顶点代表一个人，边表示两人之间有交往关系。如果这个社交网络很大，每个人的朋友较少，那么邻接表会更加高效。但如果每个人都有大量的朋友，那么用邻接矩阵来存储会更加节省空间。

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/385619
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且不能用非基于比较的排序
• 除此之外, 这篇博客: 数据结构之单链表的插入删除操作中的 2.2.1 第一种时间复杂度为O(n) 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• #include<stdio.h>
  #include<stdlib.h>
  
  typedef struct LNode{
  	int data;
  	struct LNode *next;
  }LNode,*LinkList;
  
  bool ListDelete(LinkList &L,LNode *q, int &e){
  	if(L == NULL)
  		return false;
  	if(q == NULL)
  		return false;
  	LNode *p = L; 
  	do{
  		p = p->next;
  	}while(p->next != q);
  	
  	e = q->data;
  	p->next = q->next;
  	free(q);
  	return true;
  }