0-1开课;;7.1图的基本概念;图的分类;权：对边赋予的有意义的数值量;v0;图的逻辑关系;a1;完全图;度、入度和出度;;路径、回路;v0;v0;子图;连通图;连通分量;强连通图、强连通分量;图的抽象数据类型定义;7.2图的存储结构;邻接矩阵表示法;存储示意图;存储示意图;顶点间存在方向相反的弧;v0v1v2v3;存储结构定义;无向图的邻接矩阵存储结构;B;有向网络的邻接矩阵存储结构;图的建立;思路：;voidCreatGraph(Graph*G,DataTypea[],intn,inte)
{
inti,j,k,v1,v2,w;
};邻接表（AdjacencyList）;存储思想;;存储结构定义;无向图的邻接表存储结构;有向图的邻接表存储结构;有向网络的邻接表存储结构;基本操作;v0;v0;存储有向图;存储有向图;十字链表;b;邻接多重表;7.3图的遍历;图的遍历;;;深度优先搜索DFS;V1;遍历结果：A、B、D、C;算法实现;流程图描述;算法分析;广度优先搜索BFS;V1;遍历结果：A、B、C、D;算法实现;算法分析;7.4图的生成树与最小生成树;图的生成树;图的生成树;图的生成森林;最小生成树;如何构造最小生成树;最小生成树的重要性质：;Prim算法;Prim算法——基本思想;;算法：Prim
输入：无向连通网G=(V，E)
输出：最小生成树T=(U，TE)
1.初始化：U={u}；TE={}；
2.重复下述操作直到U=V：
2.1在E中寻找最短边(i，j)，且满足i∈U，j∈V-U；
2.2U=U+{j}；
2.3TE=TE+{(i，j)}；;侯选集：对于任意v∈V-U,选取该顶点v到U中个顶点的边中权值最小的边，成为顶点v关联的最短边。所有V-U集合中顶点到U中顶点的最短边集合形成候选集。;Prim算法——存储结构;初始时，lowcost[v]=0，表示将顶点v加入集合U中；
adjvex[i]=v，lowcost[i]=arcs[v][i]（0≤i≤n-1）;每一次迭代，设数组lowcost[n]中的最小权值是lowcost[j]，则
令lowcost[j]=0，表示将顶点j加入集合U中；;;;v0;v0;;Kruskal算法;Kruskal算法——基本思想;85;;找到连接U和V-U的最短边;算法：Kruskal算法
输入：无向连通网G=(V，E)
输出：最小生成树T=(U，TE)
1.初始化：U=V；TE={}；
2.重复下述操作直到所有顶点位于一个连通分量：
2.1在E中选取最短边(u，v);
2.2如果顶点u、v位于两个连通分量，则
2.2.1将边(u，v)并入TE；
2.2.2将这两个连通分量合成一个连通分量；
2.3在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取；;应用举例;7.5最短路径(ShortestPath);最短路径问题;最短路径的定义;最短路径的通用模型;最短路径的定义;单源点最短路径问题;计算机科学家：Dijkstra（1930-2002）;Dijkstra算法——基本思想;Dijkstra算法过程;（2）从U中选取一个距离v最小的顶点u，把u加入S中（该选定的距离就是v?u的最短路径长度）。;（3）以u为新考虑的中间点，修改U中各顶点j的最短路径长度：若从源点v到顶点j（j∈U）的最短路径长度（经过顶点u）比原来最短路径长度（不经过顶点u）短，则修改顶点j的最短路径长度。
;Dijkstra算法;Dijkstra算法——存储结构;算法：Dijkstra算法
输入：有向网图G=(V，E)，源点v
输出：从v到其他所有顶点的最短路径
1.初始化：集合S={v}；dist(v,vi)=wv,vi,(i=1...n)；
2.重复下述操作直到S==V
2.1dist(v,vk)=min{dist(v,vj),(j=1..n)}；
2.2S=S+{vk}；