5-3图的存储结构

5-3图的存储结构及实现v第五章图图的存储结构图是否可以采用顺序存储结构？在图中，任何两个顶点之间都可能存在关系（边）无法通过存储位置表示这种任意的逻辑关系图无法采用顺序存储结构如何存储图呢？图是由顶点和边组成分别考虑如何存储顶点如何存储边图的邻接表存储及实现图的邻接矩阵存储及实现学什么？5-3-1图的邻接矩阵存储结构及实现v第五章图存储思想edge[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它邻接矩阵也称数组表示法，基本思想是：一维数组：存储图中顶点的信息二维数组（邻接矩阵）：存储图中各顶点之间的邻接关系设G＝(V,E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：存储示意图v0v3v2v1v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v3无向图的邻接矩阵有什么特点？对称矩阵如何求顶点v

的度？第v行（或第v列）非零元素的个数如何判断顶点i和

j之间是否存在边？if(edge[i][j]==1)0123v0v3v2v1如何求顶点i的所有邻接点？扫描第

i

行for(j=0;j<n;j++)if(edge[i][j]==1)

顶点j是顶点i的邻接点v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v30123存储示意图有向图的邻接矩阵一定不对称吗？顶点间存在方向相反的弧如何求顶点v

的出度？第v行非零元素的个数v0v3v2v1如何求顶点v

的入度？第v列非零元素的个数v0v1v2v3vertex=01011010

1

0000

000edge=v0

v1

v2

v3v0v1v2v30123存储示意图v0v1v2v3vertex=05

∞

2

508

7

∞

80∞2

7

∞0edge=v0

v1

v2

v3v0v1v2v3v0v3v2v12785网图的邻接矩阵可定义为：edge[i][j]＝

wij

若(vi,vj)∈E（或<vi,vj>∈E）0若i=j∞其他0123存储示意图存储结构定义constintMaxSize=10;template<typenameDataType>classMGraph{public:

MGraph(DataTypea[],intn,inte);

~MGraph();

voidDFTraverse(intv);

voidBFTraverse(intv);private:

DataTypevertex[MaxSize];

intedge[MaxSize][MaxSize];

intvertexNum,edgeNum;};图的抽象数据类型定义？ADTGraphDataModel…Operation

CreateGraph：图的建立DestroyGraph：图的销毁DFTraverse：深度优先遍历图BFTraverse：广度优先遍历图endADTv0v3v2v1v0v1v2v3a=输入v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v3结果44vertexNumedgeNum图的建立v0v1v2v3vertex=0101101101001100edge=v0

v1

v2

v3v0v1v2v3算法：CreateGraph(a[n],n,e)输入：顶点的数据a[n]，顶点个数n，边的个数e输出：图的邻接矩阵1.存储图的顶点个数和边的个数；2.将顶点信息存储在一维数组vertex中；3.初始化邻接矩阵edge；4.依次输入每条边并存储在邻接矩阵edge中：4.1输入边依附的两个顶点的编号i和j；4.2将edge[i][j]和edge[j][i]的值置为1；44vertexNumedgeNum图的建立template<typenameDataType>MGraph<DataType>::MGraph(DataTypea[],intn,inte){

inti,j,k;

vertexNum=n;edgeNum=e;

for(i=0;i<vertexNum;i++)//存储顶点

vertex[i]=a[i];

for(i=0;i<vertexNum;i++)//初始化邻接矩阵

for(j=0;j<vertexNum;j++)

edge[i][j]=0;

for(k=0;k<edgeNum;k++)//依次输入每一条边

{

cin>>i>>j;//输入边依附的两个顶点的编号

edge[i][j]=1;edge[j][i]=1;//置有边标志

}}图的建立深度优先遍历v0v1v2v30101101101001100v0

v1

v2

v3v0v1v2v3算法：DFTraverse输入：顶点的编号v输出：图的深度优先遍历序列1.访问顶点v;修改标志visited[v]=1;2.j=顶点v的第一个邻接点；3.while(j存在)3.1if(j未被访问)从顶点j出发递归执行该算法;3.2j=顶点v的下一个邻接点;0123template<typenameDataType>voidMGraph<DataType>::DFTraverse(intv){

cout<<vertex[v];visited[v]=1;

for(intj=0;j<vertexNum;j++)

if(edge[v][j]==1&&visited[j]==0)

DFTraverse(j);}算法：BFTraverse输入：顶点的编号v输出：图的广度优先遍历序列1.队列Q初始化;2.访问顶点v;修改标志visited[v]=1;顶点v入队列Q;3.while(队列Q非空)3.1i=队列Q的队头元素出队;3.2j=顶点v的第一个邻接点;3.3while(j存在)3.3.1如果j未被访问，则

访问顶点j;修改标志visited[j]=1;顶点j入队列Q；3.3.2j=顶点i的下一个邻接点；v0v1v3v2v4广度优先遍历template<typenameDataType>voidMGraph<DataType>::BFTraverse(intv){

intw,j,Q[MaxSize];

//采用顺序队列

intfront=-1,rear=-1;

//初始化队列

cout<<vertex[v];visited[v]=1;Q[++rear]=v;

//被访问顶点入队

while(front!=rear)

//当队列非空时

{

w=Q[++front];

//将队头元素出队并送到v中

for(j=0;j<vertexNum;j++)

if(edge[w][j]==1&&visited[j]==0){

cout<<vertex[j];visited[j]=1;Q[++rear]=j;

}

}}

广度优先遍历5-3-2图的邻接表存储结构v第五章图存储思想邻接矩阵存储结构的空间复杂度是多少？O(n2)如果采用邻接矩阵存储稀疏图，会出现什么情况？稀疏矩阵ACBGFEDH12∧345∧7∧68∧∧∧∧∧

01234567

ABCDEFGH

树的孩子表示法？邻接表存储的基本思想是：v0v1v2v3边表（邻接表）：顶点v

的所有邻接点链成的单链表顶点表：所有边表的头指针和存储顶点信息的一维数组13∧03∧

0123

v0

v1

v2

v3

3∧102∧adjvexnextvertexfirstEdge存储思想存储结构定义v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧structEdgeNode{

intadjvex;EdgeNode*next;};template<typenameDataType>structVertexNode{

DataTypevertex;

EdgeNode*firstEdge;};vertexfirstEdgeadjvexnext基本操作v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧边表中的结点表示什么？对应图中的一条边设图有n个顶点e条边，邻接表的空间复杂度是多少？O(n+e)vertexadjvexnextfirstEdgev0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧如何求顶点v的度？顶点v的边表中结点的个数p=adjList[v].firstEdge;count=0;while(p!=nullptr){count++;p=p->next;}vertexadjvexnextfirstEdge基本操作v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧如何求顶点v

的所有邻接点?顶点i

的边表中的所有结点p=adjList[v].firstEdge;while(p!=nullptr){j=p->adjvex;//j是v的邻接点p=p->next;}vertexadjvexnextfirstEdge基本操作v0v1v2v313∧03∧

0123

v0

v1

v2

v3

3∧102∧如何判断顶点i

和顶点j之间是否存在边?测试顶点i

的边表中是否存在数据域为j

的结点vertexadjvexnextfirstEdge基本操作13∧

0123

v0

v1

v2

v3

0∧02∧v0v1v2v3∧如何求顶点v的出度？顶点v的出边表中结点的个数如何求顶点v的入度？所有出边表中数据域为v

的结点个数vertexadjvexnextfirstEdge基本操作存储带权图邻接表如何存储带权图？权值存储在边表中v0v1v2v32785

0123

v0

v1

v2

v3

1235∧0

237∧38∧0

51

728∧adjvexweightnextvertexfirstEdgeconstintMaxSize=10;template<typenameDataType>classALGraph{public:

ALGraph(DataTypea[],intn,inte);

~ALGraph();

voidDFTraverse(intv);

voidBFTraverse(intv);private:

VertexNode<DataType>

adjList[MaxSize];

intvertexNum,edgeNum;};ADTGraphDataModel…Operation

CreateGraph：图的建立DestroyGraph：图的销毁DFTraverse：深度优先遍历图BFTraverse：广度优先遍历图endADT存储结构定义图的抽象数据类型定义？图的建立v0v1v2v3a=输入v0v1v2v3结果13∧

0123

v0

v1

v2

v3

0∧02∧∧44vertexNumedgeNum算法：CreateGraph(a[n],n,e)输入：顶点的数据信息a[n]，顶点个数n，边的个数e输出：图的邻接表1.存储图的顶点个数和边的个数；2.将顶点信息存储在顶点表中，将该顶点边表的头指针初始化为nullptr；3.依次输入边的信息并存储在边表中：3.1输入边所依附的两个顶点的编号i和j；3.2生成边表结点s，其邻接点的编号为j； 3.3将结点s插入到第i个边表的表头；13∧

0123

v0

v1

v2

v3

0∧02∧∧图的建立

v0

v1

v2

v3

∧∧∧∧template<typenameDataType>ALGraph<DataType>::ALGraph(DataTypea[],intn,inte){

inti,j,k;

EdgeNode*s=nullptr;

vertexNum=n;edgeNum=e;

for(i=0;i<vertexNum;i++)//初始化顶点表

{

adjList[i].vertex=a[i];

adjList[i].firstEdge=nullptr;}}图的建立for(k=0;k<edgeNum;k++)//依次输入每一条边{cin>>i>>j;//输入边所依附的两个顶点的编号s=newEdgeNode;s->adjvex=j;//生成一个边表结点ss->next=adjList[i].firstEdge;//将结点s插入到第i个边表的表头adjList[i].firstEdge=s;}3∧

0

v0

1stemplate<typenameDataType>ALGraph<DataType>::ALGraph(DataTypea[],intn,inte){

inti,j,k;

EdgeNode*s=nullptr;

vertexNum=n;edgeNum=e;

for(i=0;i<vertexNum;i++)

{

adjList[i].vertex=a[i];

adjList[i].firstEdge=nullptr;}}图的建立在邻接表存储中，须释放所有在程序运行过程中申请的的边表结点template<typenameDataType>ALGraph<DataType>::~ALGraph(){EdgeNode*p=nullptr,*q=nullptr;for(inti=0;i<vertexNum;i++){p=q=adjList[i].firstEdge;while(p!=nullptr){p=p->next;deleteq;q=p;}}}13∧

0123

v0

v1

v2

v3

0∧02∧∧图的销毁深度优先遍历算法：DFTraverse输入：顶点的编号v输出：无1.访问顶点v;修改标志visited[v]=1;2.j=顶点v的第一个邻接点；3.while(j存在)3.1if(j未被访问)从顶点j出发递归执行该算法;3.2j=顶点v的下一个邻接点;13∧

0123

v0

v1

v2

v3

0∧02∧∧template<typenameDataType>voidALGraph<DataType>::DFTraverse(intv){

intj;

EdgeNode*p=nullptr;

cout<<adjList[v].vertex;visited[v]=1;

p=adjList[v].firstEdge;

while(p!=nullptr)

{

j=p->adjvex;

if(visited[j]==0)DFTraverse(j);

p=