免费制作广州网站,网站建设推广好处,爱给网素材官网app,高唐做网站建设的公司一.邻接矩阵的空间复杂度
假设图G有n个顶点e条边#xff0c;则存储该图需要O#xff08;n^2)
不适用稀疏图的存储 二.邻接表
1.邻接表的存储思想#xff1a;
对于图的每个顶点vi#xff0c;将所有邻接于vi的顶点链成一个单链表#xff0c;称为顶点vi的边表#xff08…一.邻接矩阵的空间复杂度
假设图G有n个顶点e条边则存储该图需要On^2)
不适用稀疏图的存储 二.邻接表
1.邻接表的存储思想
对于图的每个顶点vi将所有邻接于vi的顶点链成一个单链表称为顶点vi的边表对于有向图则称为出边表所有边表的头指针和存储顶点信息的一维数组构成了顶点表。 2.邻接表的结构定义
struct ArcNode{int adjvex;struct ArcNode *next;
};template class T
struct VertexNode{T vertex;struct ArcNode *firstEdge;
}; 邻接表的空间复杂度为O(ne)
更适用于有向图的存储 3.无向图的邻接表 1.如何求顶点i的度
顶点i的边表中结点的个数 2.如何判断顶点vi和vj之间是否有边
测试顶点vi的边表中是否有终点为j的结点 4.有向图的邻接表
1.如何求顶点i的出度
顶点i的边表中结点的个数 2.如何求顶点i的入度
各顶点的出边表中以顶点i为终点的结点个数 5.网图的邻接表 三.邻接表存储有向图的类
struct ArcNode{int adjvex;struct ArcNode *next;
};template class T
struct VertexNode{T vertex;struct ArcNode *firstEdge;
};
template class T
class ALGraph{
private:VertexNodeT adjList[MAX_VERTEX];int vertexNum,arcNum;
public:ALGraph(T v[],int n,int e);~ALGraph();void DFSTraverse();void BFSTraverse();
}; template class T
ALGraphT::ALGraph(T v[],int n,int e){int vi,vj;ArcNode *s;vertexNumn;arcNume;for(int i0;in;i){adjList[i].vertexv[i];adjList[i].firstEdgeNULL;}for(int i0;iarcNum;i){cinvivj;snew ArcNode;s-adjvexvj;s-nextadjList[vi].firstEdge;adjList[vi].firstEdges;}
}template class T
ALGraphT::~ALGraph(){int i,j;ArcNode *p;for(i0;ivertexNum;i){padjList[i].firstEdge;if(p){while(p){adjList[i].firstEdgep-next;delete p;padjList[i].firstEdge;}}}
} 四.逆邻接表
对于邻接表来说查找入度非常困难。
所以引入了逆邻接表。 五.十字链表
十字链表的结点结构 六.图的存储结构的比较
