图的存储--邻接表法
//“顶点”
typedef struct VNode{VertexType data; //顶点信息ArcNode *first; //第一条边/弧
}VNode,AdjList[MaxVertexNum]; //用邻接表存储的图
typedef struct{AdjList data; //顶点信息int vexnum,arcnum;
}ALGraph; //“边/弧 ”
typedef struct ArcNode{int adjvex; //边/弧指向哪个节点 struct ArcNode *next;//指向下一条弧的指针 //InfoType info; //边权值
}ArcNode;
图的广度优先遍历--BFS算法
//图的广度优先算法--BFS算法
bool visited[MAX_VERTEX_NUM]//访问标记数组
void BFSTraverse(Graph G){ //对图G进行广度优先算法 for(i=0;i<G.vexnum;++i) visited[i]=FALSE; //访问标记数组初始化 InitQueue(Q); //初始化辅助队列Q for(i=0;i<G.vexnum;++i) //从0号顶点开始遍历 if(!visited[i]) //对每个连同分量调用一次BFS BFS(G,i); //vi未访问过，从vi开始BFS
}
// 广度优先遍历 通过辅助队列实现
void BFS(Graph G,int v){ //从顶点v出发，广度优先遍历图G visit(v); //访问初始顶点v visited[v]=TRUE; //对v做已访问标记 EnQueue(Q,v); //顶点v入队列Q while(!isEmpty(Q)){ DeQueue(Q,v); //顶点v出队列 for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))//检测v所有的邻接点 if(!visited[w]){ //w为v的尚未访问的邻接顶点 visit(w); //访问顶点w visited[w]=TRUE; //对w做已访问标记 EnQueue(Q,w);//顶点w入队列 }//if }//while
} 
图的深度优先遍历-DFS算法
//图的深度优先遍历算法 通过栈实现
bool visited[MAX_VERTEX_NUM]//访问标记数组
void DFSTraverse(Graph G){ //对图G进行深度优先算法 for(i=0;i<G.vexnum;++i) visited[i]=FALSE; //访问标记数组初始化 for(i=0;i<G.vexnum;++i) //从0号顶点开始遍历 if(!visited[i]) //对每个连同分量调用一次BFS DFS(G,i); //vi未访问过，从vi开始BFS
}void DFS(Graph G,int v){ //从顶点v出发，深度优先遍历图G visit(v);visited[v]=TRUE;for(w=FirseNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))if(!visited[w]){ //w为v尚未访问的邻接节点 DFS(G,W);}
}
Prim算法实现最小生成树
#include <stdio.h>
#include <limits.h> // 提供 INT_MAX 的定义#define INF INT_MAX // 定义无穷大值
#define V 5 // 图中的顶点数量// 函数：找到未加入MST的顶点中键值最小的顶点
int minKey(int key[], int mstSet[]) {int min = INF, minIndex; // 初始化最小值为无穷大// 遍历所有顶点for (int v = 0; v < V; v++) {// 如果顶点未加入MST且当前键值小于最小值，则更新最小值和最小值索引if (!mstSet[v] && key[v] < min) {min = key[v];minIndex = v;}}return minIndex; // 返回键值最小的顶点索引
}// 函数：打印构造的MST
void printMST(int parent[], int graph[V][V]) {printf("Edge \tWeight\n"); // 打印表头// 遍历所有顶点（从1开始，因为0是根节点，没有父节点）for (int i = 1; i < V; i++) {// 打印边和权重printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);}
}// 函数：使用Prim算法构造并打印MST
void primMST(int graph[V][V]) {int parent[V]; // 用于存储MST的数组int key[V]; // 用于存储每个顶点的键值，键值代表该顶点到MST的最小距离int mstSet[V]; // 布尔数组，用于跟踪顶点是否已加入MST// 初始化所有键值为无穷大，所有顶点都未加入MSTfor (int i = 0; i < V; i++) {key[i] = INF;mstSet[i] = 0;}key[0] = 0; // 将第一个顶点的键值设为0，以便从它开始构建MSTparent[0] = -1; // 第一个顶点没有父节点// 构建MST，需要V-1条边for (int count = 0; count < V - 1; count++) {// 找到键值最小且未加入MST的顶点int u = minKey(key, mstSet);mstSet[u] = 1; // 将该顶点加入MST// 更新相邻顶点的键值for (int v = 0; v < V; v++) {// 如果存在边，且顶点v未加入MST，且边的权重小于当前键值if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {parent[v] = u; // 更新父节点key[v] = graph[u][v]; // 更新键值}}}// 打印构造的MSTprintMST(parent, graph);
}int main() {// 定义一个图的邻接矩阵表示int graph[V][V] = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};// 调用Prim算法函数primMST(graph);return 0;
}Kruskal算法实现最小生成树
#include <stdio.h>
#include <stdlib.h>#define MAX_EDGES 100 // 定义最大边数// 定义边的结构体
typedef struct {int u, v, weight; // 边的两个顶点和权重
} Edge;// 定义图的结构体
typedef struct {int V, E; // 顶点数和边数Edge edges[MAX_EDGES]; // 存储所有边
} Graph;// 定义并查集的结构体
typedef struct {int parent[MAX_EDGES]; // 父节点数组int rank[MAX_EDGES]; // 秩数组，用于优化合并操作
} DisjointSet;// 创建图的函数
Graph* createGraph(int V, int E) {Graph* graph = (Graph*)malloc(sizeof(Graph)); // 分配内存graph->V = V; // 设置顶点数graph->E = E; // 设置边数return graph; // 返回图的指针
}// 查找函数，用于并查集
int find(DisjointSet* ds, int i) {if (ds->parent[i] != i) { // 如果当前节点不是根节点ds->parent[i] = find(ds, ds->parent[i]); // 路径压缩，递归查找根节点}return ds->parent[i]; // 返回根节点
}// 合并函数，用于并查集
void unionSets(DisjointSet* ds, int x, int y) {x = find(ds, x); // 找到x的根节点y = find(ds, y); // 找到y的根节点if (ds->rank[x] < ds->rank[y]) { // 如果x的秩小于y的秩ds->parent[x] = y; // 将x的根节点设置为y的根节点} else if (ds->rank[x] > ds->rank[y]) { // 如果x的秩大于y的秩ds->parent[y] = x; // 将y的根节点设置为x的根节点} else { // 如果秩相等ds->parent[y] = x; // 将y的根节点设置为x的根节点ds->rank[x]++; // 增加x的秩}
}// 比较函数，用于qsort排序
int compare(const void* a, const void* b) {Edge* edge1 = (Edge*)a; // 将void指针转换为Edge指针Edge* edge2 = (Edge*)b; // 将void指针转换为Edge指针return edge1->weight - edge2->weight; // 按权重升序排序
}// Kruskal算法实现
void kruskalMST(Graph* graph) {DisjointSet ds; // 创建并查集int V = graph->V; // 获取顶点数int E = graph->E; // 获取边数// 初始化并查集for (int i = 0; i < V; i++) {ds.parent[i] = i; // 每个节点的父节点初始化为自身ds.rank[i] = 0; // 每个节点的秩初始化为0}// 按边的权重排序qsort(graph->edges, E, sizeof(Edge), compare);int e = 0; // 已选择的边数int i = 0; // 当前处理的边的索引// 构建最小生成树while (e < V - 1) { // 最小生成树需要V-1条边Edge nextEdge = graph->edges[i++]; // 获取当前边int x = find(&ds, nextEdge.u); // 找到边的一个顶点的根节点int y = find(&ds, nextEdge.v); // 找到边的另一个顶点的根节点if (x != y) { // 如果两个顶点不在同一个集合中printf("%d - %d : %d\n", nextEdge.u, nextEdge.v, nextEdge.weight); // 输出边unionSets(&ds, x, y); // 合并两个集合e++; // 增加已选择的边数}}
}int main() {int V = 4; // 顶点数int E = 5; // 边数Graph* graph = createGraph(V, E); // 创建图// 添加边graph->edges[0].u = 0;graph->edges[0].v = 1;graph->edges[0].weight = 10;graph->edges[1].u = 0;graph->edges[1].v = 2;graph->edges[1].weight = 6;graph->edges[2].u = 0;graph->edges[2].v = 3;graph->edges[2].weight = 5;graph->edges[3].u = 1;graph->edges[3].v = 3;graph->edges[3].weight = 15;graph->edges[4].u = 2;graph->edges[4].v = 3;graph->edges[4].weight = 4;// 调用Kruskal算法kruskalMST(graph);return 0;
}BFS算法解决无权图的单源最短路径问题
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h> // 用于 INT_MAX#define MAX_VERTEX_NUM 20 // 假设图的最大顶点数// 邻接表的边表节点
typedef struct ArcNode {int adjvex; // 邻接点域，存储该顶点对应的下标struct ArcNode *next; // 链域，指向下一个邻接点
} ArcNode;// 邻接表的表头节点
typedef struct VNode {int data; // 顶点信息ArcNode *first; // 边表头指针
} VNode, ALGraph[MAX_VERTEX_NUM];// 队列结构
typedef struct {int data[MAX_VERTEX_NUM];int front, rear;
} Queue;// 初始化队列
void InitQueue(Queue *Q) {Q->front = Q->rear = 0;
}// 队列是否为空
bool IsEmpty(Queue *Q) {return Q->front == Q->rear;
}// 入队操作
void EnQueue(Queue *Q, int v) {Q->data[Q->rear++] = v;
}// 出队操作
int DeQueue(Queue *Q) {return Q->data[Q->front++];
}// 创建邻接表的边表节点
ArcNode* CreateArcNode(int adjvex) {ArcNode *newNode = (ArcNode *)malloc(sizeof(ArcNode));newNode->adjvex = adjvex;newNode->next = NULL;return newNode;
}// 广度优先搜索求单源最短路径
void BFS_ShortestPath(ALGraph G, int source, int dist[]) {bool visited[MAX_VERTEX_NUM] = {false}; // 访问标记数组Queue Q;InitQueue(&Q);EnQueue(&Q, source);visited[source] = true;dist[source] = 0; // 源点到自身的距离为0while (!IsEmpty(&Q)) {int v = DeQueue(&Q);ArcNode *p = G[v].first;while (p != NULL) {int w = p->adjvex;if (!visited[w]) {visited[w] = true;dist[w] = dist[v] + 1; // 源点到w的距离等于源点到v的距离加1EnQueue(&Q, w);}p = p->next;}}
}int main() {ALGraph G; // 邻接表int n; // 顶点数int e; // 边数int source; // 源点// 输入顶点数和边数printf("Enter number of vertices and edges: ");scanf("%d %d", &n, &e);// 初始化邻接表for (int i = 0; i < n; ++i) {G[i].data = i;G[i].first = NULL;}// 输入边printf("Enter edges (u v):\n");for (int i = 0; i < e; ++i) {int u, v;scanf("%d %d", &u, &v);ArcNode *newNode = CreateArcNode(v);newNode->next = G[u].first;G[u].first = newNode;}// 输入源点printf("Enter source vertex: ");scanf("%d", &source);// 初始化距离数组int dist[MAX_VERTEX_NUM];for (int i = 0; i < n; ++i) {dist[i] = INT_MAX; // 初始化为无穷大}// 调用BFS求单源最短路径BFS_ShortestPath(G, source, dist);// 输出结果printf("Shortest distances from source vertex %d:\n", source);for (int i = 0; i < n; ++i) {if (dist[i] != INT_MAX) {printf("Vertex %d: %d\n", i, dist[i]);} else {printf("Vertex %d: unreachable\n", i);}}return 0;
}代码二书上代码
//BFS算法解决单源最短路径问题
void BFS_MIN_Distance(Graph G,int u){//d[i]表示从u到i节点的最短路径for(i=0;i<G.vexnum;++i)d[i]=INT_MAX;//初始化路径长度,即到所有的节点距离都是无穷 INT_MAX表示无穷 visited[u]=TRUE;d[u]=0; //初始化源点 EnQueue(Q,u);while(!isEmpty(Q)){ //BFSDeQueue(Q,u); //对头元素u出队列 for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))//检测v所有的邻接点 if(!visited[w]){ //w为u的尚未访问的邻接顶点 visited[w]=TRUE; //对w做已访问标记 d[w]=d[u]+1; //路径长度+1 EnQueue(Q,w);//顶点w入队列 }//if }//while
} 
Dijkstra算法求单源最短路径问题
#include <stdio.h> // 包含标准输入输出库
#include <stdlib.h> // 包含标准库函数
#include <limits.h> // 包含INT_MAX等宏定义#define V 5 // 定义图中顶点的数量// 找到距离源点最近的未处理顶点
int minDistance(int dist[], int sptSet[], int n) {int min = INT_MAX, min_index; // 初始化最小距离为INT_MAX，用于比较for (int v = 0; v < n; v++) { // 遍历所有顶点if (sptSet[v] == 0 && dist[v] <= min) { // 如果顶点未处理且当前距离小于等于最小值min = dist[v]; // 更新最小距离min_index = v; // 更新最小距离对应的顶点索引}}return min_index; // 返回距离源点最近的未处理顶点的索引
}// 打印最短路径结果
void printSolution(int dist[], int n) {printf("Vertex\t Distance from Source\n"); // 打印表头for (int i = 0; i < n; i++) { // 遍历所有顶点printf("%d \t\t %d\n", i, dist[i]); // 打印顶点编号和到源点的最短距离}
}// Dijkstra算法实现
void dijkstra(int graph[V][V], int src) {int dist[V]; // 保存从源点到每个顶点的最短路径int sptSet[V]; // 保存每个顶点是否已经被处理（最短路径集合）// 初始化所有距离为无穷大，sptSet[]为falsefor (int i = 0; i < V; i++) {dist[i] = INT_MAX; // 初始距离设为无穷大sptSet[i] = 0; // 初始时所有顶点都未处理}// 源点到自身的距离是0dist[src] = 0; // 源点到自身的距离为0for (int count = 0; count < V - 1; count++) { // 迭代V-1次，找到所有顶点的最短路径// 选择距离源点最近的未处理顶点int u = minDistance(dist, sptSet, V); // 调用minDistance函数找到最近的顶点sptSet[u] = 1; // 标记该顶点已处理// 更新相邻顶点的距离for (int v = 0; v < V; v++) { // 遍历所有顶点// 如果顶点v未处理，且u到v有边，且u到v的路径长度小于当前已知的最短路径if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {dist[v] = dist[u] + graph[u][v]; // 更新v的最短路径}}}printSolution(dist, V); // 打印最终的最短路径结果
}int main() {/* 假设图的邻接矩阵如下：例图是一个有向图，顶点编号为0到40 -- 4 --> 1| ^8 || 1v |2 -- 2 --> 3 -- 7 --> 43 6^ || |7 --------*/int graph[V][V] = {{ 0, 4, 0, 0, 0 }, // 邻接矩阵表示图的边权重{ 0, 0, 8, 0, 0 },{ 0, 0, 0, 2, 0 },{ 0, 0, 0, 0, 7 },{ 0, 0, 0, 0, 0 }};dijkstra(graph, 0); // 从顶点0开始计算最短路径return 0; // 程序结束
}
Floyd算法解决单源最短路径问题
#include <stdio.h>
#include <limits.h> // 包含INT_MAX等宏定义#define V 5 // 定义图中顶点的数量// 打印最短路径矩阵
void printSolution(int dist[][V]) {printf("The following matrix shows the shortest distances between every pair of vertices:\n");for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {if (dist[i][j] == INT_MAX) // 如果距离为INT_MAX，表示没有路径printf("%7s", "INF");elseprintf("%7d", dist[i][j]); // 打印距离}printf("\n");}
}// Floyd算法实现
void floydWarshall(int graph[][V]) {int dist[V][V]; // 创建一个二维数组dist，用于存储最短路径// 初始化dist矩阵为图的邻接矩阵for (int i = 0; i < V; i++)for (int j = 0; j < V; j++)dist[i][j] = graph[i][j];// 动态规划求解所有顶点对之间的最短路径for (int k = 0; k < V; k++) { // k表示中间顶点for (int i = 0; i < V; i++) { // i表示源顶点for (int j = 0; j < V; j++) { // j表示目标顶点// 如果i到j通过k的路径更短，则更新dist[i][j]if (dist[i][k] + dist[k][j] < dist[i][j])dist[i][j] = dist[i][k] + dist[k][j];}}}// 打印最终的最短路径矩阵printSolution(dist);
}int main() {/* 假设图的邻接矩阵如下：例图是一个有向图，顶点编号为0到40 -- 5 --> 1| ^8 || 2v |2 -- 3 --> 3 -- 4 --> 43 6^ || |7 --------*/int graph[V][V] = { { 0, 5, INT_MAX, 8, INT_MAX },{ INT_MAX, 0, 2, INT_MAX, INT_MAX },{ INT_MAX, INT_MAX, 0, 3, 4 },{ INT_MAX, INT_MAX, INT_MAX, 0, 6 },{ 7, INT_MAX, INT_MAX, INT_MAX, 0 } };// 调用Floyd算法floydWarshall(graph);return 0; // 程序结束
}
总结
逆拓扑排序的实现（DFS算法）
//逆拓扑排序的实现（DFS算法）
void DFSTraverse(Graph G){ //对图G进行深度优先遍历 for(v=0;v<G.vexnum;++v)visited[v]=false;//初始化已访问标记数据 for(v=0;v<G.vexnum;++v)//本代码从0开始遍历 if(!visited[v])DFS(G,v);
}
void DFS(Graph G,int v){ //从顶点v出发，深度优先遍历图G visited[v]=true; //设已访问标记 for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))if(!visited[w]){ //w为u的尚未访问的邻接节点 DFS(G,w);}print(v);//在所有邻接顶点都被访问后，打印顶点 v。//这一步实现了逆拓扑排序，因为顶点 v 在其所有邻接顶点之后被打印。
} 
拓扑排序的实现
//拓扑排序的实现
bool TopologicalSort(Graph G){InitStack(S); //初始化栈，存储入度为0的顶点for(int i=0;i<G.vexnum;i++)if(indegree[i]==0)Push(S,i); //将所有入度为0的顶点进栈int count=0; //计数，记录当前已经输出的顶点数while(!IsEmpty(S)){ //栈不空，则存在入度为0的顶点Pop(S,i);//栈顶元素出栈print[count++]=i;//输出顶点ifor(p=G.vertices[i].firstarc;p;p=p->nextarc){//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈 Sv=p->adjvex;if(!(--indegree[v]))Push(S,v);//入度为0，则入栈 } } //whileif(count<G.vexnum)return false;//排序失败，有向图中有回路elsereturn true;//拓扑排序成功
}
失败 错误代码：0×80240438)
