第6章 数据结-图-jy.ppt

建立无向网络邻接矩阵算法 CREATGRAPH(AMGraph G) { cinG.vexnumG.arcnum; for(i＝0；i＜ G.vexnum ；i++) cin G.vexs[i];//读入顶点信息 for(i＝0；i＜；i++) for(j＝0；j＜ G.vexnum ；j++) G.arcs[i][j]＝MaxInt;// 邻接矩阵初始化 for(k＝0；k＜ G.arcnum ；k++) //读入e条边 { cini jw； G.arcs[i][j]＝w； G.arcs[j][i]＝w； } } 邻接矩阵表示法： 一、优点 1.便于判断两个顶点间有边 2. 便于计算各个顶点的度 二、缺点 1.不便于增加和删除顶点 2.不便于统计边的数目 3.空间复杂度高 基于邻接表的深度优先遍历 int visited[n];//初值为FALSE void DFS(ALGraph G, int i) {coutG.data; visited[i]=TRUE; p= G[i].firstarc; while(p!=NULL) {w=p-adjvex; if (!visited[w]) DFS(G, w); p=p-nextarc; } } 基于邻接矩阵的遍历算法 void BFS(AMGraph G, int k) { InitQueue (Q) ; coutG.vexs[k]; visited[k]=TRUE; EnQueue(Q,k); while(! QueueEmpty (Q)) { DeQueue (Q, i); for(j=0;jG.vexnum;j++) if((G.arcs[i][j]==1) ((!visited[j])) {cout G.vexs[j]; visited[j]=TRUE; ENQUEUE(Q,j); } } } 7.6 两点之间的最短路径问题 求从某个源点到其余各点的最短路径 (Single Source Shortest Paths) 弗洛伊德算法 void FLOYD(AMGraph G) {for (i=0;iG.vexnum; i++) for (j=0;jG.vexnum;j++) {D[i][j]=G.arcs[i][j]; if(D[i][j] MaxInt) Path[i][j]=i; //j的前驱为i else path[i][j]= -1; } for (k=0;kG.vexnum; k++) for (i=0;iG.vexnum; i++) for (j=0;jG.vexnum;j++) if(D[i][j](D[i][k]+D[k][j])) {D[i][j]= D[i][k]+D[k][j]; Path[i][j]=Path[k][j]; //更改j的前驱 } } 通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动，这些活动完成时，整个工程也就完成了。 例如，计算机专业学生的课程开设可看成一个工程。 A Topological order(sequence)(拓扑序列） is a sequence of vertices,this sequence has two properties: (1) Including every vertex(task) in the AOV network (2) For every edge i, j in the AOV network , task i comes before task j in the sequence. Topological sorting (拓扑排序) The process of constructing a topological order from an AOV network is called topological sorting. 其余最短路径的特点： 再下一条路径长度次短的最短路径的特点: 它可能有三