假设图G有n个顶点e条边,则存储该图需要O(n^2)
不适用稀疏图的存储
对于图的每个顶点vi,将所有邻接于vi的顶点链成一个单链表,称为顶点vi的边表(对于有向图则称为出边表),所有边表的头指针和存储顶点信息的一维数组构成了顶点表。
- struct ArcNode{
- int adjvex;
- struct ArcNode *next;
- };
-
- template <class T>
- struct VertexNode{
- T vertex;
- struct ArcNode *firstEdge;
- };

邻接表的空间复杂度为O(n+e)
更适用于有向图的存储
顶点i的边表中结点的个数
测试顶点vi的边表中是否有终点为j的结点
顶点i的边表中结点的个数
各顶点的出边表中以顶点i为终点的结点个数

- struct ArcNode{
- int adjvex;
- struct ArcNode *next;
- };
-
- template <class T>
- struct VertexNode{
- T vertex;
- struct ArcNode *firstEdge;
- };
- template <class T>
- class ALGraph{
- private:
- VertexNode
adjList[MAX_VERTEX]; - int vertexNum,arcNum;
- public:
- ALGraph(T v[],int n,int e);
- ~ALGraph();
- void DFSTraverse();
- void BFSTraverse();
- };
- template <class T>
- ALGraph
::ALGraph(T v[],int n,int e){ - int vi,vj;
- ArcNode *s;
- vertexNum=n;
- arcNum=e;
- for(int i=0;i
- adjList[i].vertex=v[i];
- adjList[i].firstEdge=NULL;
- }
- for(int i=0;i
- cin>>vi>>vj;
- s=new ArcNode;
- s->adjvex=vj;
- s->next=adjList[vi].firstEdge;
- adjList[vi].firstEdge=s;
- }
- }
- template <class T>
- ALGraph
::~ALGraph(){ - int i,j;
- ArcNode *p;
-
-
相关阅读:
VLAN实现二层流量隔离(mux-vlan)应用基础配置
SpringBoot 还用 if 校验参数?老司机都是这么玩的!
iptables 之 state模块(ftp服务练习)
JSP config对象
代码整洁之道
终于有人写出我想要的系统了
用于原发性进行性失语症分类的可解释性机器学习影像组学模型
好心情精神心理科:抑郁症,真的会让你变丑!
漏洞分析丨HEVD-11.DoubleFetch[win7x86]
农村生活污水处理设备壳体制造规范介绍
-
原文地址:https://blog.csdn.net/Hsianus/article/details/134475213