71 图的定义和基本术语 71 图的定义和基本术语.ppt

第七章图图(Graph)是较线性表和树更为复杂的结构。
图中任意数据两个元素之间都可能相关。7.1图的定义和基本术语7.1图的定义和基本术语(续一)子图：G=(V,{E})和G1=(V1,{E1})
若V1属于V,E1属于E则G1是G的子图7.1图的定义和基本术语(续三)7.2图的存储结构7.2.1数组表示法数组表示法(邻接矩阵)网及其邻接矩阵7.2.2邻接表---链式存储结构邻接表的链式存储结构示意图7.3图的遍历7.3.1深度优先搜索深度优先搜索算法7.3.2广度优先搜索voidBFSTraverse(GraphG,Status(*visit)(intv))
{
for(v=0;v<G.vexnum;++v)visited[v]=FALSE;
IntiQueque(Q);
for(v=0;v<G.vexnum;++v)
if(!visited[v]){
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(u);
visited[u]=TRUE;Visit(u);
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
if(!visited[w]){visited[w]=TRUE;visited(w);
EnQueue(G,w);}
}
}
}7.4图的连通性问题7.4.3最小生成树Prim算法示意图Kruskal算法示意图实验与习题