这周学的是图，既然是新的概念，首先要了解它的定义和基本术语，我们这里主要讲术语，包括但不限于有向图和无向图，邻接点，出度和入度，路径和路径长度，连通图和连通分量（这里重点讲一下）图中任意两个顶点属于V集合，则图是连通的，所谓连通分量，指的是无向图中的极大连通子图；对于有向图，就是它本身啊！！！不能再错了）
然后就是图的存储结构这里，主要有邻接矩阵和邻接表，邻接矩阵主要有两数组，顶点表和邻接矩阵，若有权值则需将矩阵中赋予相应的值；然后是邻接表，这里涉及到指针，在构建时，有3个结构体，我个人比较容易忘记是定点指针那里，还要多多回归课本。
对图的遍历主要有2种算法BFS和DFS；直接上代码：
void DFS_AM(AMGraph G, int v) { //图G为邻接矩阵类型 cout << v << " "; //访问第v个顶点 visited[v] = true; for(w=0; w<G.vexnum; w++) //依次检查邻接矩阵v所在的行 if((G.arcs[v][w]!=0)&& (!visited[w])) DFS_AM(G, w); //w是v的邻接点，如果w未访问，则递归调用DFS_AM } void DFSTraverse(Graph G) { // 对图 G 作深度优先遍历 for(v=0; v<G.vexnum; ++v) visited[v] = FALSE; //访问标志数组初始化 for (v=G.vexnum-1; v>=0; --v) if (!visited[v]) DFS(G, v); //对尚未访问的顶点调用DFS }
BFS，我个人不太熟，要多多看课本
void BFS(Graph &G, int j) {//宽度优先分析 visited[j] = true; queue<int> qu; qu.push(j); while(qu.size() != 0) { int mark = qu.front(); qu.pop(); cout<<mark<<" "; for(int i=0; i<G.Nnum; i++) { if(G.edges[i][mark] == 1 && visited[i] == false) { visited[i] = true; qu.push(i); } } } }
然后是最小生成树这里，有两个重要的方法，一个是不断找能构成最小权值的边的顶点，把他补充到集合U中。
原文：https://www.cnblogs.com/ckie111/p/13128574.html