摘自：https://blog.csdn.net/qq_45694646/article/details/106764026
C++实现图的基本操作
数据结构之图（存储，遍历，最短路径）
图是一种比线性表和树更为复杂的数据结构，它是”多对多”的关系。图（Graph）G是由两个集合V和E组成，记为G=（V,E）。
一、图的邻接矩阵存储
邻接矩阵法来表示图，需要用一个二维数组来存储邻接矩阵，一个一维数组来存储顶点信息。用邻接矩阵来存储图有它的优点也有它的缺点：
优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。
缺点：n个顶点需要n*n个单元存储边;空间效率为O(n2)。 对稀疏图而言尤其浪费空间。
代码实现
#define MaxInt 32767 //表示极大值 即无穷大
#define MVNum 100 //最大顶点数
typedef string VerTexType; //设顶点的数据类型为string，需#include
typedef int ArcType; //设权值类型为整型
typedef struct
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum; //图的当前点数和边数
}AMGraph;
二、用邻接矩阵来创建无向网
【算法思想】：
1.输入总顶点数和总边数
2.依次输入点的信息存入顶点表中
3.初始化邻接矩阵，使每个权值初始化为极大值
4.构造邻接矩阵
代码实现
bool CreateUDN(AMGraph& G) //采用邻接矩阵表示法，创建无向网 { int i, j, k ; VerTexType v1, v2; ArcType w; cout << "请输入图的顶点总数和边的总数:"; cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数 cout << "请依次输入顶点信息:" << endl; for (i = 0; i < G.vexnum; ++i) cin >> G.vexs[i]; //依次输入顶点信息 for (i = 0; i < G.vexnum; ++i) for (j = 0; j < G.vexnum; ++j) G.arcs[i][j] = MaxInt;//初始化邻接矩阵，置为无穷大 cout << "请输入边的信息，格式：头，尾，权值" << endl; for (k = 0; k < G.arcnum; ++k) { cin >> v1 >> v2 >> w; //输入一条边依附的顶点及权值 i = LocateVex(G, v1);j= LocateVex(G, v2); //确定v1,v2在G中的位置，即顶点数组的下标 G.arcs[i][j] = w; //边的权值为w ,v2> G.arcs[j][i] = G.arcs[i][j]; //对称边 } return true; }
LocateVex()函数：查询顶点是否在顶点表中，若在则返回顶点表中的下标；否则返回-1
int LocateVex(AMGraph G, VerTexType u)
{//存在则返回u在顶点表中的下标;否则返回-1
int i;
for (i = 0; i < G.vexnum; ++i)
if (u == G.vexs[i])
return i;
return -1;
}
输出无向网的信息
void PrintGraph(AMGraph G)
{
int i, j;
cout << "图的邻接矩阵存储信息:" << endl;
cout << "顶点信息：" << endl;
for (i = 0; i < G.vexnum; i++)
cout << i << ":" << G.vexs[i] << endl; //输出顶点信息
cout << "邻接矩阵数据：" << endl;
for (i = 0; i < G.vexnum; i++)
{
for (j = 0; j < G.vexnum; j++)
{
if (G.arcs[i][j] == MaxInt)
cout << left<6)<<"∞";
else
cout << left<6) << G.arcs[i][j];
}
cout << endl;
}
}
三、图的遍历
遍历的定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算
遍历的实质：找每个顶点的邻接点的过程
1.深度优先遍历
简单归纳：
(1) 访问起始点v;
(2) 若v的第1个邻接点没访问过，深度遍历此邻接点；
(3) 若当前邻接点已访问过，再找v的第2个邻接点重新遍历
辅助数组：
避免重复访问，bool visited[MVNum];初值为false,若i被访问，则改visited[i]=true;
代码实现：
void DFS_AM(AMGraph G, int v) //深度优先搜索遍历,从第v个顶点开始
{
cout <8)<< G.vexs[v]; visited[v] = true; //访问第v个顶点，并置visited数组对应的值为true
for (int w = 0; w < G.vexnum; w++)
if ((G.arcs[v][w] != 0) && (!visited[w]))
DFS_AM(G,w); //G.arcs[v][w] != 0表示w是v的邻接点，如果w未访问，则递归调用DFS_AM
}
DFS算法效率分析：
（1）用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。
（2）用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)
（3）结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。
2.广度优先遍历
简单归纳：
（1）在访问了起始点v之后，依次访问 v的邻接点
（2）然后再依次访问这些顶点中未被访问过的邻接点
（3）直到所有顶点都被访问过为止
辅助队列：
这里用的是链队列，用顺序队列（循环队列）也可以。
//队列的DAT//
typedef int Elemtype; //BFS中队列存放的是图元素下标
typedef int Status;
typedef struct QNode {
Elemtype data;
struct QNode* next;
}*QueuePrt;
typedef struct {
QueuePrt front, rear; //指针形式的对头和队尾指针
}*LinkQueue;
要写出队列的基本操作函数：
初始化 Status InitQuene(LinkQueue q) ；
判空操作 bool QueueEmpty(LinkQueue Q) ；
入队操作 Status EnQueue(LinkQueue q, Elemtype e)；
出队操作Status DeQueue(LinkQueue q, Elemtype* e)；
Status InitQuene(LinkQueue q)
{
if (NULL == q) {
return -1;
}
q->front = NULL;
q->rear = NULL;
return 0;
}
bool QueueEmpty(LinkQueue Q)
{
if (NULL == Q) {
return true;
}
if (NULL == Q->front)
{
return true;
}
return false;
}
Status EnQueue(LinkQueue q, Elemtype e)
{
QueuePrt QP = NULL;
if (NULL == q) {
return -1;
}
QP = (QueuePrt)calloc(1, sizeof(struct QNode));
QP->data = e;
QP->next = NULL;
if (NULL == q->front) {
q->front = QP;
q->rear = QP;
} else {
q->rear->next = QP;
q->rear = QP;
}
return 0;
}
Status DeQueue(LinkQueue q, Elemtype *e)
{
QueuePrt QP = NULL;
QueuePrt QP_prev = NULL;
QueuePrt front = NULL;
if (NULL == q || NULL == e) {
return -1;
}
if (QueueEmpty(q)) {
return 0;
}
if (NULL == q->front->next) {
q->rear = NULL;
}
front = q->front;
q->front = q->front->next;
*e = front->data;
free(front);
return 0;
}
void BFS(AMGraph G, int v) //广度优先遍历
{
int i, j;
LinkQueue Q;
Q =(LinkQueue)malloc(sizeof(LinkQueue));
InitQuene(Q);//采用的是链队列
for (i = 0; i < G.vexnum; i++)
visited[i] = false;
for (i = 0; i < G.vexnum; i++)
{
if (visited[i] == false)
{
cout << setw(8) << G.vexs[v]; visited[v] = true; //访问第v个顶点，并置visited数组对应值为true
EnQueue(Q, v); //v进队
while (!QueueEmpty(Q)) //队列非空
{
DeQueue(Q, &i);//队头元素出队，并置为i
for (j = 0; j < G.vexnum; j++)
{
if ((G.arcs[i][j] = !MaxInt || G.arcs[i][j] != 0) && visited[j] == false)
{//检查i的所有邻接点
visited[j] = true;
cout << setw(8) << G.vexs[j];//访问j
EnQueue(Q, j);//j入队
}
}
}
}
}
}
BFS算法效率分析：
（1）如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O(n2)。
（2）用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。
3.DFS与BFS算法效率比较
（1）空间复杂度相同，都是O(n)(借用了堆栈或队列）；
（2）时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。
四、最短路径算法(Dijkstra算法)
最短路径：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。
辅助结构：
数组S[n]：记录相应顶点是否已被确定最短距离
数组Dist[n]：记录源点到相应顶点路径长度
数组Path[n]：记录相应顶点的前驱顶点
【Dijkstra算法思想】
（1） 初始化：
● 将源点v0加到S中，即S[v0]=true
● 将v0到各个终点的最短路径长度初始化为权值，即Dist[i]=G.arcs[v0][vi]
● 如果v0和顶点vi之间有弧，则将vi的前驱置为v0，即Path[i]=v0,否则Path[i]=-1
（2） 循环n-1次执行以下操作：
● 选择下一条最短路径的终点vk，使得Dist[k]=Min{Dist[i]|vi∈V-S}
● 将vk加入到S中，即S[vk]=true
● 根据条件更新从v0出发到集合V-S上任一顶点的最短路径的长度，若条件Dist[k]+G.arcs[k][i]
Original: https://www.cnblogs.com/LiuYanYGZ/p/16317836.html
Author: LiuYanYGZ
Title: C++实现图的遍历和最短路径
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/535525/
转载文章受原作者版权保护。转载请注明原作者出处！