第六章学习小结

一、学习到的知识

1.图：有一个顶点集和一个边集组成的数据结构，又分为有向图和无向图。
2.连通图、连通分量的概念
3.用邻接矩阵的方式来表示图

代码如下：
const int MVNum = 100;
typedef char VerTexType;// 假设顶点的数据类型为char形
typedef int ArcType;//假设边权值为整形
typedef struct AmGraph {
VerTexType vexs[MVNum];//顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum, arcnum;//顶点数+边数
}AmGraph;

基于邻接矩阵的一些操作：输入、查找

4.邻接表表示图
代码：
typedef struct VNode {
VerTexType data;//顶点序号
ArcNode* firstarc;//指向连接该点的边
}VNode,AdjList[MVNum];

typedef struct ArcNode {
int adjvex;;//改变所指顶点序号
struct ArcNode* nextarc;//指向下一条边的指针
int info;//权值
}ArcNode;
typedef struct ALGraph{
AdjList vertices;
int vexnum, arcnum;//顶点个数、边数
}ALGraph;

基于邻接表对图的操作：创建、查找、遍历

5.深度优先遍历DFS：

void DFS(graph& g, int v)//深度优先
{
cout << v << " ";
visited[v] = true;
for (int i = 0; i < g.vexnum; i++)
{
if (visited[i] == false && g.arcs[v][i] == 1) DFS(g, i);
}
}

6.广度优先遍历BFS：

void BFS(graph& g, int v)//广度优先
{
cout << v << " ";
visited[v] = true;
queue<int> q;
q.push(v);
while (!q.empty())
{
int k = q.front();
q.pop();
for(int i=0; i<g.vexnum; i++)
if (visited[i] == false && g.arcs[k][i] == 1)
{
cout << i << " ";
visited[i] = true;
q.push(i);
}
}
}
7.最短路径
Dijkstra算法：

 

 

8.最小生成树：
Prim算法：以指定顶点开始
Cruskal算法：以最小开始

二、心得体会

   感觉这一章的概念比较多，但是一些算法框架比较好理解的，实现起来还是能够接受。