毓秀数据结构实验七:图
图原本为第六次实验，但是因为实验调整哈夫曼树成为第六次实验，图的实验成为第七次实验。
图的基本操作
一、实验目的
1、掌握图的存储方式
2、 掌握图的相关操作
二、实验内容
1、实现无向图的广度优先遍历。
2、最短路径算法。（可选作）
报告内容为小组共同完成
一、实验目的
1、掌握图的存储方式。
2、掌握图的相关操作。
二、实验内容
1、实现无向图的广度优先遍历
2、最短路径算法
三、实验步骤
1、通过邻接表（或邻接矩阵）建图
2、理解BFS算法以及最短路径算法的主要思想
3、该写啥写啥
四、代码实现
#include<iostream>
using namespace std;
const int MAXN = 105;
const long long INF = 0x3f3f3f3f;
//---------------------Edge----------------------------
typedef struct Edge
{
int ed;
int data;
Edge* next;
}Edge, * PtEdge;
PtEdge head[MAXN];
Edge* EdgeInit()
{
Edge* head;
head = new Edge();
head->next = NULL;
head->data = 0;
return head;
}
void DestroyEdgeList(PtEdge& head)
{
while (head->next)
{
Edge* now = head->next;
head->next = head->next->next;
delete now;
}
delete head;
}
void AddEdge(PtEdge& head, int nowEd, int nowData = 0)//向邻接表中添加数据
{
Edge* now = new Edge();
now->ed = nowEd;
now->data = nowData;
now->next = head->next;
head->next = now;
}
void showEdge(PtEdge& head)
{
Edge* now = head->next;
while (now)
{
printf("%d ", now->ed);
now = now->next;
}
printf("\n");
}
void ShowAllEdge(int n)
{
for (int i = 1; i <= n; i++)
{
printf("%d:", i);
showEdge(head[i]);
}
}
//---------------------Queue---------------------------
typedef struct Queue
{
int* base;
int front;
int rear;
}Queue;
void QueueInit(Queue& Q)
{
Q.base = new int[MAXN];
Q.front = 0;
Q.rear = 0;
}
void DestroyQueue(Queue& Q)
{
delete[]Q.base;
}
void QueuePush(Queue& Q, int num)
{
if ((Q.rear + 1) % MAXN == Q.front)
{
printf("把队列开大一点!\n");
return;
}
Q.base[Q.rear] = num;
Q.rear = (Q.rear + 1) % MAXN;
}
int QueuePop(Queue& Q)
{
if (Q.front == Q.rear)
{
printf("队列已空，请检查程序哪里出错!\n");
return 0;
}
int num = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXN;
return num;
}
bool QueueEmpty(Queue& Q)
{
if (Q.front == Q.rear)return true;
return false;
}
//---------------------BFS-----------------------------
void BFS(int Start)
{
int bj[MAXN];
memset(bj, 0, sizeof(bj));
Queue MyQueue;
QueueInit(MyQueue);
QueuePush(MyQueue, Start); bj[Start] = 1;
printf("图的bfs先后顺序为:");
while (!QueueEmpty(MyQueue))
{
int now = QueuePop(MyQueue);
printf("%d ", now);
Edge* nowEdge = head[now]->next;
while (nowEdge)
{
int nowEd = nowEdge->ed;
if (bj[nowEd] == 0)
{
QueuePush(MyQueue, nowEd);
bj[nowEd] = 1;
}
nowEdge = nowEdge->next;
}
}
printf("\n");
DestroyQueue(MyQueue);
}
//---------------------Dijkstra------------------------
void Dijkstra(int Start, int n)
{
long long dist[MAXN];
for (int i = 1; i <= n; i++)//初始化，将所有边设为不可达
dist[i] = INF;
dist[Start] = 0;
Edge* now = head[Start]->next;//初始化源点可直达的点与源点的距离
while (now)
{
dist[now->ed] = now->data;
now = now->next;
}
int bj[MAXN];
memset(bj, 0, sizeof(bj));
bj[Start] = 1;
for (int i = 1; i <= n - 1; i++)
{
int nowMin = INF, nowLoc = 0;
for (int j = 1; j <= n; j++)
if (bj[j] == 0 && dist[j] < nowMin)
{
nowMin = dist[j];
nowLoc = j;
}
bj[nowLoc] = 1;
//为什么要只取邻接的去做是因为如果存在负边权，如果你的INF不够大，这时Inf加上负边权赋值到dist上在理论上是一定会对结果产生影响的（因为本来是不通的，这么一改就把它变成通路了），而且在实际上也容易引起错误
Edge* now = head[nowLoc]->next;
while (now)
{
if (dist[now->ed] == INF || dist[now->ed] > dist[nowLoc] + now->data)
dist[now->ed] = dist[nowLoc] + now->data;
now = now->next;
}
}
for (int i = 2; i <= n; i++)
printf("1->%d : %lld\n", i, dist[i]);
}
//---------------------main----------------------------
int n, m;
int main()
{
int op;
printf("1.图的广度优先遍历\n2.图的最短路径算法\n");
scanf_s("%d", &op);
if (op == 1)
{
printf("请输入图的节点个数:\n");
scanf_s("%d", &n);
printf("请输入边的条数:\n");
scanf_s("%d", &m);
int i;
for (i = 1; i <= n; i++)
head[i] = EdgeInit();
printf("请输入%d条边:\n", m);
for (i = 1; i <= m; i++)
{
int st, ed;
scanf_s("%d%d", &st, &ed);
AddEdge(head[st], ed);
AddEdge(head[ed], st);
}
//ShowAllEdge(n);
BFS(1);//默认从1出发
for (i = 1; i <= n; i++)
DestroyEdgeList(head[i]);
}
else
{
printf("请输入图的节点个数:\n");
scanf_s("%d", &n);
printf("请输入边的条数:\n");
scanf_s("%d", &m);
int i;
for (i = 1; i <= n; i++)
head[i] = EdgeInit();
printf("请输入%d条边:\n", m);
for (i = 1; i <= m; i++)
{
int st, ed, data;
scanf_s("%d%d%d", &st, &ed, &data);
AddEdge(head[st], ed, data);
AddEdge(head[ed], st, data);
}
printf("请输入源点:\n");
int st;
scanf_s("%d", &st);
Dijkstra(st, n);
}
return 0;
}
五、实验难点
1、BFS算法的实现：有些类似层序遍历，从原点出发一层一层地扩展。结合到实现就是对当前处理到的节点继续找与其邻接的节点，然后对于未访问也未进去待处理序列的节点使其加入队列中，直到队列空。
2、对Dijkstra算法的理解：
首先是和Floyd算法相同的求最短路的关键步骤，如右图的三角形：
这个关键步骤就是找i、j两点之间比当前已知最短距离更短距离的方法，这个方法就是找到一个与i，j均有连边的点k，如果i到k的距离与k到j的距离之和小于已知的i到j的距离，就用这个距离和去替代i到j的距离，一直找直到dist(i,j)再也不能变得更小，则我们找到了i，j之间的最小距离。
伪码大概是：dist(i,j) = min(dist(i,j), dist(i,k) + dist(k,j))
这个步骤（说是思想也没问题）用在Dijkstra算法中，i就是我们的源点，而k是当前i能到达的
点中距离最小的节点，而这个j则是与k邻接的节点。Dijkstra算法每次都会找的当前距离
源点最近且未访问过的节点k然后找到k的所有邻接点j进行扩展，如此操作n（节点数）-1次后所有节点都被访问过，我们也求出了源点到所有点的最短路径。
那么这里就存在一个问题，为什么每次找距离最小的节点去扩展是正确的？
这个问题可以结合Dijkstra算法不能处理有负边权的图来理解。因为对于每个点我们都只访问一次，那要保证这个点的值不会再被修改（不然的话通过这个点扩展的结果就不是最优的，可能会影响后面的扩展），而如果一个点已经可以确定它到源点的距离一定不会再变小，那么从这个点扩展出来的数据也会是当前最优的，不会影响之后的扩展。那么基于这个，再基于没有负边权，我们自然可以想到当前和源点之间的距离最小的节点一定不能再次被扩展，每次处理我们都可以找到这样不能被扩展的节点，经过n-1次后，n个节点都不能被扩展了，那么我们自然就得出了要求的最短距离。
六、运行程序：
省略
七、实验心得
其实图论问题的难点就在于把现实的问题抽象成图的模型并在计算机中通过特定的存储方法体现出来，再根据抽象出来的问题对应的使用相应的算法去解决，我们现在学习的都是一些比较基础的用于解决问题的算法，至于更深层次的理解需要在将来碰到具体问题时在解决问题中提升（没错说的就是课程设计）
加速支持