影视网站设计论文,上线了做的网站可以登陆,企业为什么要建立集团,什么是静态网站一.思维导图二.概念笔记图的存储结构1. 邻接矩阵定义#xff1a;设图G有n (n大于等于1) 个顶点#xff0c;则邻接矩阵是一个n阶方阵。当矩阵中的 [i,j] !0(下标从1开始) ,代表其对应的第i个顶点与第j个顶点是连接的特点无向图的邻接矩阵是对称矩阵#xff0c;n个顶点的无向图…一.思维导图二.概念笔记图的存储结构1. 邻接矩阵定义设图G有n (n大于等于1) 个顶点则邻接矩阵是一个n阶方阵。当矩阵中的 [i,j] !0(下标从1开始) ,代表其对应的第i个顶点与第j个顶点是连接的特点无向图的邻接矩阵是对称矩阵n个顶点的无向图需要n*(n1)/2个空间大小有向图的邻接矩阵不一定对称n个顶点的有向图需要n²的存储空间无向图中第i行的非零元素的个数为顶点Vi的度有向图中第i行的非零元素的个数为顶点Vi的出度第i列的非零元素的个数为顶点Vi的入度2.邻接表定义为图G中的每一个顶点建立一个单链表每条链表的结点元素为与该顶点连接的顶点特点无向图顶点Vi的度为第i个单链表中的结点数无向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为全部单链表中连接点域值是i的结点个数图的遍历深度优先遍历图的深度优先遍历类似于树的前序遍历。先以一个未被访问过的顶点作为起始顶点沿当前顶点的边走到未访问过的顶点当没有未访问过的顶点时则回到上一个顶点继续试探别的顶点直到所有的顶点都被访问。广度优先遍历图的广度优先遍历类似于树的层次遍历。从图中某顶点出发依次访问各个邻接点然后分别从这些邻接点出发依次访问它们的邻接点并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问则需要另选一个未曾被访问过的顶点作为新的起始点直至图中所有顶点都被访问到为止。最小生成树Prim算法Prim算法首先以一个结点作为最小生成树的初始结点然后以迭代的方式找出与最小生成树中各结点权重最小边并加入到最小生成树中。加入之后如果产生回路则跳过这条边选择下一个结点。直至所有结点都加入到最小生成树中。Kruskal算法Kruskal算法在找最小生成树结点之前需要对所有权重边做从小到大排序。将排序好的权重边依次加入到最小生成树中如果加入时产生回路就跳过这条边加入下一条边。当所有结点都加入到最小生成树中之后就找出了最小生成树。Kruskal在算法效率上是比Prim快因为Kruskal只需一次对权重的排序就能找到最小生成树而Prim算法需要多次对邻边排序才能找到最短路径Dijkstra算法Dijkstra算法是典型的单源最短路径算法用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展直到扩展到终点为止。Floyd算法Floyd算法是先找出最短的距离然后在考虑如何找出对应的行进路线。三.疑难问题关于Dijkstra算法和Floyd算法的代码实现从网上摘取两段代码理解const int MAXINT 32767;const int MAXNUM 10;int dist[MAXNUM];int prev[MAXNUM];int A[MAXUNM][MAXNUM];void Dijkstra(int v0){bool S[MAXNUM]; // 判断是否已存入该点到S集合中int nMAXNUM;for(int i1; in; i){dist[i] A[v0][i];S[i] false; // 初始都未用过该点if(dist[i] MAXINT)prev[i] -1;elseprev[i] v0;}dist[v0] 0;S[v0] true;for(int i2; in; i){int mindist MAXINT;int u v0; // 找出当前未使用的点j的dist[j]最小值for(int j1; jn; j)if((!S[j]) dist[j]{u j; // u保存当前邻接点中距离最小的点的号码mindist dist[j];}S[u] true;for(int j1; jn; j)if((!S[j]) A[u][j]{if(dist[u] A[u][j] dist[j]) //在通过新加入的u点路径找到离v0点更短的路径{dist[j] dist[u] A[u][j]; //更新distprev[j] u; //记录前驱顶点}}}}typedef struct{char vertex[VertexNum]; //顶点表int edges[VertexNum][VertexNum]; //邻接矩阵,可看做边表int n,e; //图中当前的顶点数和边数}MGraph;void Floyd(MGraph g){int A[MAXV][MAXV];int path[MAXV][MAXV];int i,j,k,ng.n;for(i0;ifor(j0;j{A[i][j]g.edges[i][j];path[i][j]-1;}for(k0;k{for(i0;ifor(j0;jif(A[i][j](A[i][k]A[k][j])){A[i][j]A[i][k]A[k][j];path[i][j]k;}}}
