目录
邻接矩阵的阶乘性质
例一：
例二：
图的存储
邻接矩阵法
邻接表法
十字链表法（只能存储有向图）
邻接多重表（只能存储无向图）
图的部分基本操作
在图中插入新结点
在图中删除结点
图的遍历
无向图的广度优先遍历（邻接矩阵）
无向图的广度优先遍历（邻接表）
无向图的广度优先遍历（含有多个连通分量的无向图）
有向图的广度优先遍历
无向图的深度优先遍历（邻接矩阵）
无向图的深度优先遍历（邻接表）
无向图的深度优先遍历（含有多个连通分量的无向图）
有向图的深度优先遍历
图的应用
最小生成树（Prim算法）
最小生成树（kruskal算法）
邻接矩阵的阶乘性质
假设有图如下所示：
例一：
如图所示，A²[1][4]表示的是从A到D长度为2的路径数目，即用左矩阵的第一行与右矩阵的第4列作内积。
为1表示A->B有1条长度为1的路径，为1表示B->D有一条长度为1的路径，它们相乘为1，说明A->D有一条长度为2的路径。
完整结果如下：
例二：
左矩阵为A²，右矩阵为A，则A³[1][4] 表示的是从A到D的长度为3的路径的数目，即用左矩阵的第一行与右矩阵的第4列作内积。
A²[1][2]为0表示A->B没有长度为2的路径，A[2][4]为1表示B->D有一条长度为1的路径，它们相乘为0，说明当前这条路径不是一条A->D的长度为3的路径。
A²[1][3]为1表示A->C有一条长度为2的路径，A[3][4]为1表示C->D有一条长度为1的路径，它们相乘为1，说明A->D有一条长度为3的路径。
图的存储
邻接矩阵法
在实际题目应用中如果所需用到的图的信息不多的话，不用这么麻烦来定义一个结构体graph，直接用一个二维数组来表示邻接矩阵即可。
#define maxsize 100
#define inf 999999
struct graph
{
char node[maxsize]; //顶点表，记录每个点的名字，例如1号节点叫A，2号节点叫B
int edge[maxsize][maxsize]; //邻接矩阵
int nodenum, edgenum; //记录图的顶点数和边数
};
//构造邻接矩阵，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化矩阵
g->nodenum = node_num;
for (int i = 0; i < maxsize; i++)
{
for (int j = 0; j < maxsize; j++)
{
//对角线上的值设为0，其他的设为无穷大
if (i == j) g->edge[i][j] = 0;
else g->edge[i][j] = inf;
}
}
for (int i = 0; i < vec.size(); i++)
{
//一条a->b，权值为w的边
int a = vec[i][0];
int b = vec[i][1];
int w = vec[i][2];
g->edge[a][b] = w;
g->edgenum++;
}
return g;
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 5}, {2, 3, 4}, {3, 1, 8}, {3, 6, 9}, {4, 3, 5}, {4, 6, 6}, {5, 4, 5}, {6, 1, 3}, {6, 5, 1} };
graph* g = creat(vec, 6);
//打印邻接矩阵
for (int i = 1; i < g->nodenum + 1; i++)
{
for (int j = 1; j < g->nodenum + 1; j++)
{
if (g->edge[i][j] == inf) cout << "i";
else cout << g->edge[i][j];
cout << " ";
}cout << endl;
}
return 0;
}
打印结果如下（用 i 来表示无穷大）
邻接表法
在实际运用中，可以只用顶点表结构体和边表结点结构体，将结构体graph简化为一个数组来存储邻接表。
#define maxsize 100
#define inf 999999
struct edgenode //边表结点
{
int b; //该结点的位置，通过该位置可以在邻接表adjlist[]中访问，得到该结点的信息
int w; //该条边的权值
edgenode* next = nullptr; //指向下一个边表结点的指针
};
struct headnode //顶点表结点
{
char data; //存储该结点的信息，例如名字啥的
edgenode* first = nullptr; //指向第一个边表结点
};
struct graph
{
headnode adjlist[maxsize]; //邻接表
int nodenum, edgenum; //记录图的顶点数和边数
};
//向某个顶点中，用头插法插入新的边表结点
void insert_edgenode(headnode& hn, edgenode* en)
{
en->next = hn.first;
hn.first = en;
}
//构造邻接表，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化邻接表
g->nodenum = node_num;
for (int i = 0; i < vec.size(); i++)
{
//一条a->b，权值为w的边
int a = vec[i][0];
int b = vec[i][1];
int w = vec[i][2];
//创建一个新的边表结点
edgenode* node = new edgenode;
node->b = b;
node->w = w;
insert_edgenode(g->adjlist[a], node);
}
return g;
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 5}, {2, 3, 4}, {3, 1, 8}, {3, 6, 9}, {4, 3, 5}, {4, 6, 6}, {5, 4, 5}, {6, 1, 3}, {6, 5, 1} };
graph* g = creat(vec, 6);
//打印邻接表
for (int i = 1; i < g->nodenum + 1; i++)
{
cout << i;
edgenode* temp = g->adjlist[i].first;
while (temp != nullptr)
{
cout << " -> " << temp->b << "," << temp->w;
temp = temp->next;
}cout << endl;
}
return 0;
}
打印结果如下：
十字链表法（只能存储有向图）
十字链表法没用过，对我来说还是比较抽象的，自己动手画一遍会好点。
相比邻接表法的改进在于：顶点节点中添加了一个firstin域，连接以该顶点作为弧头的第一条弧（即入边）；边表结点中添加了两个int类型的域来存储头结点和尾结点，并又添加了一个hlink域，连接弧头相同的下一条弧（即顶点的下一条入边） 。
【注】画图时要注意边表结点中的指针都是在边表结点当中互连的，不要连接到顶点表上去。
邻接多重表（只能存储无向图）
用邻接表存储无向图会将一条边重复存储，出现冗余的问题，当要删除一个结点时需要分别在两个结点的边表中遍历，效率较低。因此可以采用如下的邻接多重表：
对我来说太抽象了。。不过吉大不考，先放过吧。
图的部分基本操作
在图中插入新结点
不论是有向图还是无向图，都是与上图一样的操作。
邻接矩阵中插入新结点，只需要在顶点表中新开一个区域存放其信息，在邻接矩阵中新开一行和一列即可，然后再存放边。
邻接表中插入新结点，只需要在顶点表中新开一个区域，然后依次插入边即可。
在图中删除结点
有向图与无向图的操作都一样。
邻接矩阵中删除结点，如果要释放该结点所对应的空间的话，会导致出现大量的数据移动操作，复杂性较低。因此可以在邻接矩阵中将该结点所对应的行和列上的值都设为0/∞，同时在顶点表中添加一个bool类型的变量，用来表示某个顶点是否是空结点。
邻接表中删除结点，除了在顶点表中删除该结点所对应的所有边之外，还需要在其他顶点中遍历，删除连有该结点的其他信息。
图的遍历
无向图的广度优先遍历（邻接矩阵）
#define maxsize 100
#define inf 999999
struct graph
{
char node[maxsize]; //顶点表，记录每个点的名字，例如1号节点叫A，2号节点叫B
int edge[maxsize][maxsize]; //邻接矩阵
int nodenum, edgenum = 0; //记录图的顶点数和边数
};
//构造邻接矩阵，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化矩阵
g->nodenum = node_num;
for (int i = 0; i < maxsize; i++)
{
for (int j = 0; j < maxsize; j++)
{
//所有元素初始化为0
g->edge[i][j] = 0;
}
}
for (int i = 0; i < vec.size(); i++)
{
//一条两边结点为a和b的边
int a = vec[i][0];
int b = vec[i][1];
g->edge[a][b] = 1;
g->edge[b][a] = 1;
g->edgenum++;
}
return g;
}
//在图g中，从顶点v开始进行广度优先遍历
void BFS(graph* g, int v, bool visited[])
{
queue que; //辅助队列
cout << v << " "; //访问初始顶点v
visited[v] = true; //将顶点v标记已访问
que.push(v); //初始顶点v入队
while (!que.empty())
{
int a = que.front(); //取队列头顶点a
que.pop();
for (int b = 1; b < g->nodenum + 1; b++)
{
if (g->edge[a][b] == 1) //如果a-b这条边存在
{
if (!visited[b]) //如果顶点b还未被访问过
{
cout << b << " "; //访问顶点b
visited[b] = true; //将顶点b标记已访问
que.push(b); //将顶点b入队
}
}
}
}
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 0}, {1, 5, 0}, {2, 6, 0}, {6, 3, 0}, {6, 7, 0}, {3, 7, 0}, {3, 4, 0}, {4, 7, 0}, {4, 8, 0}, {7, 8, 0} };
graph* g = creat(vec, 8); //构造图
bool visited[maxsize]; //辅助函数，用于判断某顶点是否被访问过
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点1出发得到的广度优先遍历：";
BFS(g, 1, visited); //从顶点1开始进行广度优先遍历
cout << endl;
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点2出发得到的广度优先遍历：";
BFS(g, 2, visited); //从顶点2开始进行广度优先遍历
cout << endl;
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点3出发得到的广度优先遍历：";
BFS(g, 3, visited); //从顶点3开始进行广度优先遍历
return 0;
}
#define maxsize 100
#define inf 999999
struct graph
{
char node[maxsize]; //顶点表，记录每个点的名字，例如1号节点叫A，2号节点叫B
int edge[maxsize][maxsize]; //邻接矩阵
int nodenum, edgenum = 0; //记录图的顶点数和边数
};
//构造邻接矩阵，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化矩阵
g->nodenum = node_num;
for (int i = 0; i < maxsize; i++)
{
for (int j = 0; j < maxsize; j++)
{
//所有元素初始化为0
g->edge[i][j] = 0;
}
}
for (int i = 0; i < vec.size(); i++)
{
//一条两边结点为a和b的边
int a = vec[i][0];
int b = vec[i][1];
g->edge[a][b] = 1;
g->edge[b][a] = 1;
g->edgenum++;
}
return g;
}
//在图g中，从顶点v开始进行广度优先遍历
void BFS(graph* g, int v, bool visited[])
{
queue que; //辅助队列
cout << v << " "; //访问初始顶点v
visited[v] = true; //将顶点v标记已访问
que.push(v); //初始顶点v入队
while (!que.empty())
{
int a = que.front(); //取队列头顶点a
que.pop();
for (int b = 1; b < g->nodenum + 1; b++)
{
if (g->edge[a][b] == 1) //如果a-b这条边存在
{
if (!visited[b]) //如果顶点b还未被访问过
{
cout << b << " "; //访问顶点b
visited[b] = true; //将顶点b标记已访问
que.push(b); //将顶点b入队
}
}
}
}
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 0}, {1, 5, 0}, {2, 6, 0}, {6, 3, 0}, {6, 7, 0}, {3, 7, 0}, {3, 4, 0}, {4, 7, 0}, {4, 8, 0}, {7, 8, 0} };
graph* g = creat(vec, 8); //构造图
bool visited[maxsize]; //辅助函数，用于判断某顶点是否被访问过
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点1出发得到的广度优先遍历：";
BFS(g, 1, visited); //从顶点1开始进行广度优先遍历
cout << endl;
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点2出发得到的广度优先遍历：";
BFS(g, 2, visited); //从顶点2开始进行广度优先遍历
cout << endl;
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点3出发得到的广度优先遍历：";
BFS(g, 3, visited); //从顶点3开始进行广度优先遍历
return 0;
}
对于下图来说：
得到的打印结果如下所示：
【注】由于邻接矩阵的表示方式唯一，所得到的从顶点出发得到的广度优先遍历序列是唯一的，得到的广度优先生成树也是唯一的
无向图的广度优先遍历（邻接表）
#define maxsize 100
#define inf 999999
struct edgenode //边表结点
{
int b; //该结点的位置，通过该位置可以在邻接表adjlist[]中访问，得到该结点的信息
int w; //该条边的权值
edgenode* next = nullptr; //指向下一个边表结点的指针
};
struct headnode //顶点表结点
{
char data; //存储该结点的信息，例如名字啥的
edgenode* first = nullptr; //指向第一个边表结点
};
struct graph
{
headnode adjlist[maxsize]; //邻接表
int nodenum, edgenum = 0; //记录图的顶点数和边数
};
//向某个顶点中，用头插法插入新的边表结点
void insert_edgenode(headnode& hn, edgenode* en)
{
en->next = hn.first;
hn.first = en;
}
//构造邻接表，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化邻接表
g->nodenum = node_num;
for (int i = 0; i < vec.size(); i++)
{
//一条两边结点为a和b的边
int a = vec[i][0];
int b = vec[i][1];
//创建一个新的边表结点
edgenode* node = new edgenode;
node->b = b;
insert_edgenode(g->adjlist[a], node);
node = new edgenode;
node->b = a;
insert_edgenode(g->adjlist[b], node);
}
return g;
}
//在图g中，从顶点v开始进行广度优先遍历
void BFS(graph* g, int v, bool visited[])
{
queue que; //辅助队列
cout << v << " "; //访问初始顶点v
visited[v] = true; //将顶点v标记已访问
que.push(v); //初始顶点v入队
while (!que.empty())
{
int a = que.front(); //取队列头顶点a
que.pop();
for (edgenode* it = g->adjlist[a].first; it != nullptr; it = it->next)
{
int b = it->b;
if (!visited[b]) //如果顶点b还未被访问过
{
cout << b << " "; //访问顶点b
visited[b] = true; //将顶点b标记已访问
que.push(b); //将顶点b入队
}
}
}
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 0}, {1, 5, 0}, {2, 6, 0}, {6, 3, 0}, {6, 7, 0}, {3, 7, 0}, {3, 4, 0}, {4, 7, 0}, {4, 8, 0}, {7, 8, 0}};
graph* g = creat(vec, 8);
//打印邻接矩阵
for (int i = 1; i < g->nodenum + 1; i++)
{
cout << i;
edgenode* temp = g->adjlist[i].first;
while (temp != nullptr)
{
cout << " -> " << temp->b;
temp = temp->next;
}cout << endl;
}cout << endl;
bool visited[maxsize]; //辅助函数，用于判断某顶点是否被访问过
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点1出发得到的广度优先遍历：";
BFS(g, 1, visited); //从顶点1开始进行广度优先遍历
cout << endl;
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点2出发得到的广度优先遍历：";
BFS(g, 2, visited); //从顶点2开始进行广度优先遍历
cout << endl;
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点3出发得到的广度优先遍历：";
BFS(g, 3, visited); //从顶点3开始进行广度优先遍历
return 0;
}
对于下图来说：
打印结果为：
【注】由于邻接表的表示方式不唯一，因此从某个顶点出发得到的广度优先遍历是不唯一的，得到的广度优先生成树也是不唯一的
无向图的广度优先遍历（含有多个连通分量的无向图）
上述BFS()函数的问题在于，若图中含有多个连通分量，那么仅凭一次BFS是无法遍历完所有顶点的，因此可以增加一个BFS_traverse()函数，每检测到visited数组中还有未被访问过的结点，就调用一次BFS函数，以邻接矩阵存储为例，代码如下所示：
#define maxsize 100
#define inf 999999
struct graph
{
char node[maxsize]; //顶点表，记录每个点的名字，例如1号节点叫A，2号节点叫B
int edge[maxsize][maxsize]; //邻接矩阵
int nodenum, edgenum = 0; //记录图的顶点数和边数
};
//构造邻接矩阵，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化矩阵
g->nodenum = node_num;
for (int i = 0; i < maxsize; i++)
{
for (int j = 0; j < maxsize; j++)
{
//所有元素初始化为0
g->edge[i][j] = 0;
}
}
for (int i = 0; i < vec.size(); i++)
{
//一条两边结点为a和b的边
int a = vec[i][0];
int b = vec[i][1];
g->edge[a][b] = 1;
g->edge[b][a] = 1;
g->edgenum++;
}
return g;
}
//在图g中，从顶点v开始进行广度优先遍历
void BFS(graph* g, int v, bool visited[])
{
queue que; //辅助队列
cout << v << " "; //访问初始顶点v
visited[v] = true; //将顶点v标记已访问
que.push(v); //初始顶点v入队
while (!que.empty())
{
int a = que.front(); //取队列头顶点a
que.pop();
for (int b = 1; b < g->nodenum + 1; b++)
{
if (g->edge[a][b] == 1) //如果a-b这条边存在
{
if (!visited[b]) //如果顶点b还未被访问过
{
cout << b << " "; //访问顶点b
visited[b] = true; //将顶点b标记已访问
que.push(b); //将顶点b入队
}
}
}
}
}
//对图进行广度优先遍历的总函数
void BFS_traverse(graph* g)
{
bool visited[maxsize]; //辅助函数，用于判断某顶点是否被访问过
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "该图的广度遍历序列为：";
for (int i = 1; i < g->nodenum + 1; i++)
{
//对每个连通分量调用一次BFS()函数
if (!visited[i])
{
BFS(g, i, visited); //从顶点i开始进行广度优先遍历
}
}
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 0}, {1, 5, 0}, {2, 6, 0}, {6, 3, 0}, {6, 7, 0}, {3, 7, 0}, {3, 4, 0}, {4, 7, 0}, {4, 8, 0}, {7, 8, 0}, {9, 10, 0}, {9, 11, 0}, {10, 11, 0} };
graph* g = creat(vec, 11); //构造图
BFS_traverse(g);
return 0;
}
对于下图来说：
打印结果为：
【注】图中有几个连通分量就调用几次BFS函数
有向图的广度优先遍历
对于有向图来说，一次BFS不一定能遍历完所有顶点，例如下图所示：
若从顶点1出发，则一次BFS无法遍历完所有顶点。
若从顶点7或顶点8出发，只需一次BFS就可以遍历完所有顶点。
因此针对有向图，可以采用上述的“无向图的广度优先遍历（含有多个连通分量的无向图）”这种方法，即多次调用BFS。
无向图的深度优先遍历（邻接矩阵）
深度优先遍历与广度优先遍历相比，都只是换个DFS函数罢了
#define maxsize 100
#define inf 999999
struct graph
{
char node[maxsize]; //顶点表，记录每个点的名字，例如1号节点叫A，2号节点叫B
int edge[maxsize][maxsize]; //邻接矩阵
int nodenum, edgenum = 0; //记录图的顶点数和边数
};
//构造邻接矩阵，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化矩阵
g->nodenum = node_num;
for (int i = 0; i < maxsize; i++)
{
for (int j = 0; j < maxsize; j++)
{
//所有元素初始化为0
g->edge[i][j] = 0;
}
}
for (int i = 0; i < vec.size(); i++)
{
//一条两边结点为a和b的边
int a = vec[i][0];
int b = vec[i][1];
g->edge[a][b] = 1;
g->edge[b][a] = 1;
g->edgenum++;
}
return g;
}
//在图g中，从顶点v开始进行深度度优先遍历
void DFS(graph* g, int v, bool visited[])
{
cout << v << " "; //访问初始顶点v
visited[v] = true; //将顶点v标记已访问
for (int b = 1; b < g->nodenum + 1; b++)
{
int a = v;
if (g->edge[a][b] == 1) //如果a-b这条边存在
{
if (!visited[b]) //如果顶点b还未被访问过
{
DFS(g, b, visited);
}
}
}
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 0}, {1, 5, 0}, {2, 6, 0}, {6, 3, 0}, {6, 7, 0}, {3, 7, 0}, {3, 4, 0}, {4, 7, 0}, {4, 8, 0}, {7, 8, 0} };
graph* g = creat(vec, 8); //构造图
bool visited[maxsize]; //辅助函数，用于判断某顶点是否被访问过
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点1出发得到的深度优先遍历：";
DFS(g, 1, visited); //从顶点1开始进行深度优先遍历
cout << endl;
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点2出发得到的深度优先遍历：";
DFS(g, 2, visited); //从顶点2开始进行深度优先遍历
cout << endl;
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点3出发得到的深度优先遍历：";
DFS(g, 3, visited); //从顶点3开始进行深度优先遍历
return 0;
}
对于下图来说：
打印结果为：
【注】由于邻接矩阵的表示方式唯一，所得到的从顶点出发得到的深度优先遍历序列是唯一的，得到的深度优先生成树也是唯一的
无向图的深度优先遍历（邻接表）
同理将广度优先遍历的BFS函数改为DFS函数即可
#define maxsize 100
#define inf 999999
struct edgenode //边表结点
{
int b; //该结点的位置，通过该位置可以在邻接表adjlist[]中访问，得到该结点的信息
int w; //该条边的权值
edgenode* next = nullptr; //指向下一个边表结点的指针
};
struct headnode //顶点表结点
{
char data; //存储该结点的信息，例如名字啥的
edgenode* first = nullptr; //指向第一个边表结点
};
struct graph
{
headnode adjlist[maxsize]; //邻接表
int nodenum, edgenum = 0; //记录图的顶点数和边数
};
//向某个顶点中，用头插法插入新的边表结点
void insert_edgenode(headnode& hn, edgenode* en)
{
en->next = hn.first;
hn.first = en;
}
//构造邻接表，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化邻接表
g->nodenum = node_num;
for (int i = 0; i < vec.size(); i++)
{
//一条两边结点为a和b的边
int a = vec[i][0];
int b = vec[i][1];
//创建一个新的边表结点
edgenode* node = new edgenode;
node->b = b;
insert_edgenode(g->adjlist[a], node);
node = new edgenode;
node->b = a;
insert_edgenode(g->adjlist[b], node);
}
return g;
}
//在图g中，从顶点v开始进行深度度优先遍历
void DFS(graph* g, int v, bool visited[])
{
cout << v << " "; //访问初始顶点v
visited[v] = true; //将顶点v标记已访问
int a = v;
for (edgenode* it = g->adjlist[a].first; it != nullptr; it = it->next)
{
int b = it->b;
if (!visited[b])
{
visited[b] = true;
DFS(g, b, visited);
}
}
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 0}, {1, 5, 0}, {2, 6, 0}, {6, 3, 0}, {6, 7, 0}, {3, 7, 0}, {3, 4, 0}, {4, 7, 0}, {4, 8, 0}, {7, 8, 0} };
graph* g = creat(vec, 8); //构造图
bool visited[maxsize]; //辅助函数，用于判断某顶点是否被访问过
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点1出发得到的深度优先遍历：";
DFS(g, 1, visited); //从顶点1开始进行深度优先遍历
cout << endl;
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点2出发得到的深度优先遍历：";
DFS(g, 2, visited); //从顶点2开始进行深度优先遍历
cout << endl;
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "从顶点3出发得到的深度优先遍历：";
DFS(g, 3, visited); //从顶点3开始进行深度优先遍历
return 0;
}
对于下图来说：
打印结果为：
【注】由于邻接表的表示方式不唯一，因此从某个顶点出发得到的深度优先遍历是不唯一的，得到的深度优先生成树也是不唯一的
无向图的深度优先遍历（含有多个连通分量的无向图）
与广度优先遍历类似，需要解决在多个连通分量下无法遍历完所有顶点的问题，以邻接矩阵存储为例的代码：
#define maxsize 100
#define inf 999999
struct graph
{
char node[maxsize]; //顶点表，记录每个点的名字，例如1号节点叫A，2号节点叫B
int edge[maxsize][maxsize]; //邻接矩阵
int nodenum, edgenum = 0; //记录图的顶点数和边数
};
//构造邻接矩阵，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化矩阵
g->nodenum = node_num;
for (int i = 0; i < maxsize; i++)
{
for (int j = 0; j < maxsize; j++)
{
//所有元素初始化为0
g->edge[i][j] = 0;
}
}
for (int i = 0; i < vec.size(); i++)
{
//一条两边结点为a和b的边
int a = vec[i][0];
int b = vec[i][1];
g->edge[a][b] = 1;
g->edge[b][a] = 1;
g->edgenum++;
}
return g;
}
//在图g中，从顶点v开始进行深度度优先遍历
void DFS(graph* g, int v, bool visited[])
{
cout << v << " "; //访问初始顶点v
visited[v] = true; //将顶点v标记已访问
for (int b = 1; b < g->nodenum + 1; b++)
{
int a = v;
if (g->edge[a][b] == 1) //如果a-b这条边存在
{
if (!visited[b]) //如果顶点b还未被访问过
{
DFS(g, b, visited);
}
}
}
}
//对图进行深度优先遍历的总函数
void DFS_traverse(graph* g)
{
bool visited[maxsize]; //辅助函数，用于判断某顶点是否被访问过
for (int i = 1; i < g->nodenum + 1; i++)
{
visited[i] = false;
}
cout << "该图的深度遍历序列为：";
for (int i = 1; i < g->nodenum + 1; i++)
{
//对每个连通分量调用一次BFS()函数
if (!visited[i])
{
DFS(g, i, visited); //从顶点i开始进行广度优先遍历
}
}
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 0}, {1, 5, 0}, {2, 6, 0}, {6, 3, 0}, {6, 7, 0}, {3, 7, 0}, {3, 4, 0}, {4, 7, 0}, {4, 8, 0}, {7, 8, 0}, {9, 10, 0}, {9, 11, 0}, {10, 11, 0} };
graph* g = creat(vec, 11); //构造图
DFS_traverse(g);
return 0;
}
对于下图来说：
打印结果为：
【注】在DFS_traverse函数中，图中有几个连通分量就调用几次BFS函数
有向图的深度优先遍历对于有向图来说，一次DFS不一定能遍历完所有顶点，例如下图所示：
若从顶点1出发，则一次DFS无法遍历完所有顶点。
若从顶点7或顶点8出发，只需一次DFS就可以遍历完所有顶点。
因此针对有向图，可以采用上述的“无向图的深度优先遍历（含有多个连通分量的无向图）”这种方法。
图的应用
最小生成树（Prim算法）
适用于稠密图，时间复杂度O(n²)
#define maxsize 100
#define inf 999999
struct graph
{
char node[maxsize]; //顶点表，记录每个点的名字，例如1号节点叫A，2号节点叫B
int edge[maxsize][maxsize]; //邻接矩阵
int nodenum, edgenum = 0; //记录图的顶点数和边数
};
//构造邻接矩阵，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化矩阵
g->nodenum = node_num;
for (int i = 0; i < maxsize; i++)
{
for (int j = 0; j < maxsize; j++)
{
//对角线上的值设为0，其他的设为无穷大
if (i == j) g->edge[i][j] = 0;
else g->edge[i][j] = inf;
}
}
for (int i = 0; i < vec.size(); i++)
{
//一条两边结点为a和b的边
int a = vec[i][0];
int b = vec[i][1];
int w = vec[i][2];
g->edge[a][b] = w;
g->edge[b][a] = w;
g->edgenum++;
}
return g;
}
int prim(graph* g, int start)
{
//记录图中的顶点到生成树的最短距离，若某个顶点已经加入了最短生成树，将其记为-1
//不过在这个算法中，由于每次求某一条边的权值之前会先判断另一头的顶点是否被访问过，访问过的顶点就跳过，所以即使不将访问过的顶点的minlen值设为-1也可以
int minlen[maxsize];
//记录某个顶点是否已经被访问过，即是否已经加入了生成树中
bool visited[maxsize];
for (int i = 1; i < g->nodenum + 1; i++) visited[i] = false;
//先将点start加入生成树中
minlen[start] = -1;
visited[start] = true;
//将minlen数组初始化，除了点start外，其余顶点的minlen值都设为到点start的距离
for (int i = 1; i < g->nodenum + 1; i++)
{
if (i == start) continue;
minlen[i] = g->edge[i][start];
}
int ans = 0; //所要求的最小生成树的权值之和
//开始prim算法
//由于刚才已经加入了一个顶点start了，因此只需要再循环 g->nodenum - 1次即可
for (int i = 1; i < g->nodenum; i++) //这里的i无实际意义，只用于循环
{
int cur_index = -1;
int cur_minlen = inf;
//找出到生成树的距离最短的点
for (int j = 1; j < g->nodenum + 1; j++)
{
if (visited[j]) continue; //已经访问过的顶点不用再考虑
if (cur_minlen > minlen[j])
{
cur_index = j;
cur_minlen = minlen[j];
}
}
//将找到的顶点cur_index加入生成树中
ans += cur_minlen;
visited[cur_index] = true;
minlen[cur_index] = -1;
cout << " -- " << cur_index;
//因为向生成树中加入了一个新的顶点cur_index，所以现在要通过cur_index更新其他顶点到生成树的最短距离
for (int j = 1; j < g->nodenum + 1; j++)
{
//如果顶点j已经被访问过，或者顶点j和顶点cur_index之间不存在边，则不用考虑
if (visited[j] || g->edge[j][cur_index] == inf) continue;
minlen[j] = min(minlen[j], g->edge[j][cur_index]);
}
}
return ans;
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 6}, {1, 3, 1}, {1, 4, 5}, {2, 3, 5}, {3, 4, 5}, {2, 5, 3}, {3, 5, 6}, {3, 6, 4}, {4, 6, 2}, {5, 6, 6} };
graph* g = creat(vec, 6);
//打印邻接矩阵
for (int i = 1; i < g->nodenum + 1; i++)
{
for (int j = 1; j < g->nodenum + 1; j++)
{
if (g->edge[i][j] == inf) cout << "i";
else cout << g->edge[i][j];
cout << " ";
}cout << endl;
}cout << endl;
cout << "最小生成树为：1";
int ans = prim(g, 1);
cout << endl;
cout << "最小生成树的权值为：" << ans;
return 0;
}
对于下图来说：
打印结果如下：
最小生成树（kruskal算法）
适用于稀疏图，时间复杂度O(eloge)
#define maxsize 100
#define inf 999999
struct graph
{
char node[maxsize]; //顶点表，记录每个点的名字，例如1号节点叫A，2号节点叫B
int edge[maxsize][maxsize]; //邻接矩阵
int nodenum = 0, edgenum = 0; //记录图的顶点数和边数
};
//构造邻接矩阵，传入图的信息及节点数量
graph* creat(vector>& vec, int node_num)
{
graph* g = new graph;
//初始化矩阵
g->nodenum = node_num;
for (int i = 0; i < maxsize; i++)
{
for (int j = 0; j < maxsize; j++)
{
//对角线上的值设为0，其他的设为无穷大
if (i == j) g->edge[i][j] = 0;
else g->edge[i][j] = inf;
}
}
for (int i = 0; i < vec.size(); i++)
{
//一条两边结点为a和b的边
int a = vec[i][0];
int b = vec[i][1];
int w = vec[i][2];
g->edge[a][b] = w;
g->edge[b][a] = w;
g->edgenum++;
}
return g;
}
//并查集
struct Union_Find
{
int father[maxsize];
Union_Find(int n)
{
for (int i = 1; i < n + 1; i++)
{
father[i] = -1;
}
}
int Find(int x)
{
if (father[x] < 0) return x;
return father[x] = Find(father[x]);
}
void Union(int x, int y)
{
int fx = father[x];
int fy = father[y];
if (fx == fy) return;
if (father[fx] < father[fy])
{
father[fy] = fx;
}
else
{
if (father[fx] == father[fy]) father[fy]--;
father[fx] = fy;
}
}
};
//边的排序函数
void sort_edge(graph* g, int edge[][3])
{
int k = 1;
for (int i = 1; i < g->nodenum + 1; i++)
{
for (int j = i + 1; j < g->nodenum + 1; j++)
{
if (g->edge[i][j] == inf) continue; //如果i - j这条边不存在，跳过
//分别存储两个节点和权值
edge[k][0] = i;
edge[k][1] = j;
edge[k][2] = g->edge[i][j];
k++;
}
}
bool flag = true;
while (flag)
{
flag = false;
for (int k = 1; k < g->edgenum; k++)
{
if (edge[k][2] > edge[k + 1][2])
{
flag = true;
int temp = edge[k][0];
edge[k][0] = edge[k + 1][0];
edge[k + 1][0] = temp;
temp = edge[k][1];
edge[k][1] = edge[k + 1][1];
edge[k + 1][1] = temp;
temp = edge[k][2];
edge[k][2] = edge[k + 1][2];
edge[k + 1][2] = temp;
}
}
}
cout << "排序后的边为：";
for (int k = 1; k < g->edgenum + 1; k++)
{
cout << edge[k][0] << "--" << edge[k][1] << ":" << edge[k][2] << " ";
}cout << endl;
}
int kruskal(graph* g)
{
int edge[maxsize][3]; //用edge存储图的所有边
sort_edge(g, edge); //将所有边按权值从小到大排序
Union_Find uf(g->nodenum);
int T = g->nodenum; //T表示连通分量的个数，一开始即为顶点个数
int k = 1; //edge数组中的元素下标
int ans = 0; //最小生成树的权值之和
//开始kruskal算法
while (T > 1) //直到连通分量个数为1，说明连成了一棵最小生成树
{
int a = edge[k][0];
int b = edge[k][1];
int w = edge[k][2];
k++;
if (uf.Find(a) == uf.Find(b)) //如果顶点a和顶点b属于同一个连通分量，跳过
{
continue;
}
uf.Union(a, b); //连接顶点a和顶点b所在的两个连通分量
ans += w;
T--; //连通分量个数减一
}
return ans;
}
int main()
{
//每个一维的数组表示一条边的信息，依次是头结点、尾结点、权值
vector> vec = { {1, 2, 6}, {1, 3, 1}, {1, 4, 5}, {2, 3, 5}, {3, 4, 5}, {2, 5, 3}, {3, 5, 6}, {3, 6, 4}, {4, 6, 2}, {5, 6, 6} };
graph* g = creat(vec, 6);
//打印邻接矩阵
for (int i = 1; i < g->nodenum + 1; i++)
{
for (int j = 1; j < g->nodenum + 1; j++)
{
if (g->edge[i][j] == inf) cout << "i";
else cout << g->edge[i][j];
cout << " ";
}cout << endl;
}cout << endl;
int ans = kruskal(g);
cout << "最小生成树的权值为：" << ans;
return 0;
}
由于我对并查集比较熟悉，所以感觉kruskal算法比较好理解，代码也比较好写。
PS：我到现在排序法还只会一个冒泡，自从sort()用多了之后连冒泡咋写也忘了。。上面代码中的排序法先用个暴力冒泡凑合一下吧。
对下图来说：
结果为：
kruskal算法所生成的最小生成树不好输出，就不输出了。
