第七章 图论

第七章 图论

一、数据结构定义

1. 图的邻接矩阵存储法

   #define MaxVertexNum 100 // 节点数目的最大值// 无边权，只用0或1表示边是否存在
   bool graph[MaxVertexNum][MaxVertexNum];// 有边权
   int graph[MaxVertexNum][MaxVertexNum];
   

2. 图的邻接表存储法
   把所有节点存储为节点数组，每个节点里有自己的数据和一个边指针，这个边指针相当于一个链表的头指针，这个链表里存放所有与这个节点相连的边，边里存放该边指向的节点编号和下一条边指针
   

   #define MaxVertexNum 100 // 节点数目的最大值
   typedef struct EdgeNode{ // 边表节点int adjvex; // 该边所指向的节点编号struct EdgeNode *next; // 指向下一条边的指针// Infotype info; // 边权值（如果有）
   }EdgeNode;typedef struct VNode{ //节点表节点VertexType data; // 节点信息EdgeNode *first; // 指向第一条依附该节点的边的指针
   }VNode;typedef struct{int verNum, edgeNum; // 节点数和边数VNode AdjList[MaxVertexNum]; // 节点数组
   } ALGraph; // 邻接表
   

3. 图的十字链表存储法（有向图）
   

   typedef struct edgeNode{int headVer, tailVer; struct edgeNode *hLink, *tLink; // 分别指向弧头和弧尾相同的下一条边infoType info;
   } edgeNode;typedef struct VNode{VerType data;edgeNode *firstIn, *firstOut; // 分别指向入边表和出边表中的第一个边节点
   } VNode;typedef struct{int verNum, edgeNum;VNode XList[verNum]; // 顶点表
   } OLGraph;
   

4. 图的邻接多重表存储法（无向图）
   

   typedef struct edgeNode{int iVer, jVer; // 边的两个顶点在顶点表（数组）里的下标struct edgeNode *iLink, *jLink; // 和顶点相连的下一条边infoType info; // 带权图可存储边的权值
   } edgeNode;typedef struct VNode{VerType data;edgeNode *firstEdge;
   } VNode;typedef struct{int verNum, edgeNum; // 图的顶点数和边数VNode adjMuList[verNum];
   } AMLGraph; 
   

二、代码/算法

1. 遍历/搜索
   • DFS实现
   • BFS实现
2. 最小生成树
   • Prim算法（ACE：不要求记忆）
   • Kruskal算法（ACE：不要求掌握，理解并查集在Kruskal中的作用即可）
3. 最短路径
   • Dijkstra算法
   • Floyd算法
4. 拓扑排序算法（ACE：常考选择题）
5. 关键路径算法 （ACE：常考选择题）
6. 并查集