图的拓扑排序及其应用发布日期：2024-04-29 浏览次数：
一、实验目的
1.了解图的存储结构和常用算法。
2.熟悉邻接矩阵和邻接表两种图的存储结构。
3.实现图的存储结构及其基本操作。
4.掌握图的遍历算法。
5.能够应用图的存储结构和算法解决实际问题。
二、实验内容
1.设计图的存储结构及其基本操作，包括图的创建、插入节点、插入边、删除节点、删除边等操作。
2.实现图的遍历算法，包括深度优先遍历和广度优先遍历。
3.编写应用程序，实现通过图的存储结构和算法解决实际问题，如求最短路径、拓扑排序等。
三、实验原理
1.图的定义：图是由顶点集合和边集合组成的一种数据结构。其中，顶点表示节点，边表示节点之间的连线。
2.图的分类：根据图的性质，可以分为有向图和无向图，带权图和无权图，稠密图和稀疏图等。
3.图的存储结构：常用的图的存储结构有邻接矩阵和邻接表两种。
（1）邻接矩阵：用一个二维数组表示节点之间的关系，其中，数组元素为1表示对应位置的两个节点之间有边，为0则没有。
（2）邻接表：用一个数组和链表表示节点之间的关系。数组中的每个元素表示一个节点，链表表示该节点与其它节点之间的连线。
4.图的遍历算法：
（1）深度优先遍历（DFS）：从图的某个节点出发，依次遍历其它节点，直到所有节点都被访问过。具体实现是使用递归或栈来实现。
（2）广度优先遍历（BFS）：从图的某个节点出发，首先访问其周围的节点，然后再访问与之相邻的节点，直到所有节点都被访问过。具体实现是使用队列来实现。
5.图的应用：
（1）最短路径：求两个节点之间的最短路径，常用的算法有 Dijkstra 算法和 Floyd 算法。
（2）拓扑排序：用于解决有向无环图中的任务调度问题，使得每个任务的前置任务都在其前面执行。
四、实验步骤
1.设计图的存储结构及其基本操作。
（1）创建图：根据用户输入的节点数和边数，创建邻接矩阵或邻接表。
（2）插入节点：向图中添加一个新节点。
（3）插入边：向图中添加一条新边。
（4）删除节点：从图中删除指定节点及其相关的所有边。
（5）删除边：从图中删除指定边。
2.实现图的遍历算法。
（1）深度优先遍历：使用递归或栈来实现。
（2）广度优先遍历：使用队列来实现。
3.编写应用程序，实现通过图的存储结构和算法解决实际问题。
（1）最短路径：使用 Dijkstra 算法或 Floyd 算法求解两个节点之间的最短路径。
（2）拓扑排序：使用拓扑排序算法解决任务调度问题。
五、实验结果
1.设计图的存储结构及其基本操作。
（1）邻接矩阵存储结构：
```c++
#define MAXVEX 100
#define INFINITY 65535
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
```
（2）邻接表存储结构：
```c++
#define MAXVEX 100
#define INFINITY 65535
typedef struct EdgeNode
{
int adjvex;
int weight;
struct EdgeNode *next;
}EdgeNode;
typedef struct VertexNode
{
int in;
int data;
EdgeNode *firstedge;
}VertexNode;
typedef struct
{
VertexNode adjlist[MAXVEX];
int numVertexes, numEdges;
}GraphAdjList;
```
2.实现图的遍历算法。
（1）深度优先遍历：
```c++
void DFS(MGraph G, int i, bool visited[])
{
visited[i]=true;
printf("%d ", G.vexs[i]);
for (int j=0; j < G.numVertexes; j++)
{
if (G.arc[i][j]==1 && !visited[j])
{
DFS(G, j, visited);
}
}
}
void DFSTraverse(MGraph G)
{
bool visited[MAXVEX];
for (int i=0; i < G.numVertexes; i++)
{
visited[i]=false;
}
for (int i=0; i < G.numVertexes; i++)
{
if (!visited[i])
{
DFS(G, i, visited);
}
}
}
```
（2）广度优先遍历：
```c++
void BFSTraverse(MGraph G)
{
bool visited[MAXVEX];
for (int i=0; i < G.numVertexes; i++)
{
visited[i]=false;
}
queue<int> q;
for (int i=0; i < G.numVertexes; i++)
{
if (!visited[i])
{
visited[i]=true;
printf("%d ", G.vexs[i]);
q.push(i);
while (!q.empty())
{
int j=q.front();
q.pop();
for (int k=0; k < G.numVertexes; k++)
{
if (G.arc[j][k]==1 && !visited[k])
{
visited[k]=true;
printf("%d ", G.vexs[k]);
q.push(k);
}
}
}
}
}
}
```
3.编写应用程序，实现通过图的存储结构和算法解决实际问题。
（1）最短路径：
```c++
void Dijkstra(MGraph G, int v0, int dist[], int path[])
{
bool final[MAXVEX];
for (int i=0; i < G.numVertexes; i++)
{
final[i]=false;
dist[i]=G.arc[v0][i];
if (dist[i] !=INFINITY)
{
path[i]=v0;
}
else
{
path[i]=-1;
}
}
dist[v0]=0;
final[v0]=true;
for (int i=1; i < G.numVertexes; i++)
{
int min=INFINITY;
int k=0;
for (int j=0; j < G.numVertexes; j++)
{
if (!final[j] && dist[j] < min)
{
min=dist[j];
k=j;
}
}
final[k]=true;
for (int j=0; j < G.numVertexes; j++)
{
if (!final[j] && min + G.arc[k][j] < dist[j])
{
dist[j]=min + G.arc[k][j];
path[j]=k;
}
}
}
}
void ShortestPath_Dijkstra(MGraph G, int v0, int dist[], int path[])
{
Dijkstra(G, v0, dist, path);
for (int i=0; i < G.numVertexes; i++)
{
printf("v%d -> v%d: ", v0, i);
if (dist[i]==INFINITY)
{
printf("no path
");
}
else
{
int j=i;
stack<int> s;
while (j !=v0)
{
s.push(j);
j=path[j];
}
s.push(v0);
while (!s.empty())
{
printf("v%d", s.top());
s.pop();
if (!s.empty())
{
printf(" -> ");
}
}
printf(", dist=%d
", dist[i]);
}
}
}
```
（2）拓扑排序：
```c++
bool TopologicalSort(GraphAdjList GL)
{
int count=0;
queue<int> q;
for (int i=0; i < GL.numVertexes; i++)
{
if (GL.adjlist[i].in==0)
{
q.push(i);
}
}
while (!q.empty())
{
int i=q.front();
q.pop();
printf("%d ", GL.adjlist[i].data);
count++;
EdgeNode *p=GL.adjlist[i].firstedge;
while (p !=NULL)
{
int j=p->adjvex;
if (--GL.adjlist[j].in==0)
{
q.push(j);
}
p=p->next;
}
}
printf("
");
if (count < GL.numVertexes)
{
return false;
}
else
{
return true;
}
}
```
六、实验结论
1.邻接矩阵和邻接表两种存储结构各有优缺点，应根据实际需求选择合适的存储结构。
2.深度优先遍历和广度优先遍历两种遍历算法都可以遍历图中的所有节点，具体应根据实际需求选择。
3.Dijkstra 算法和 Floyd 算法都可以求解最短路径问题，具体应根据图的规模和稠密程度选择合适的算法。
4.拓扑排序算法可以解决有向无环图中的任务调度问题，应用广泛。
