个人网站建设案例课堂,商标注册网上缴费,邮箱网页版入口,wordpress rss feed第七章 图论
一、数据结构定义
图的邻接矩阵存储法#define MaxVertexNum 100 // 节点数目的最大值// 无边权#xff0c;只用0或1表示边是否存在
bool graph[MaxVertexNum][MaxVertexNum];// 有边权
int graph[MaxVertexNum][MaxVertexNum];图的邻接表存储法 把所有节点存储为…第七章 图论
一、数据结构定义
图的邻接矩阵存储法#define MaxVertexNum 100 // 节点数目的最大值// 无边权只用0或1表示边是否存在
bool graph[MaxVertexNum][MaxVertexNum];// 有边权
int graph[MaxVertexNum][MaxVertexNum];图的邻接表存储法 把所有节点存储为节点数组每个节点里有自己的数据和一个边指针这个边指针相当于一个链表的头指针这个链表里存放所有与这个节点相连的边边里存放该边指向的节点编号和下一条边指针 #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; // 邻接表图的十字链表存储法有向图 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;图的邻接多重表存储法无向图 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; 二、代码/算法
遍历/搜索 DFS实现BFS实现 最小生成树 Prim算法ACE不要求记忆Kruskal算法ACE不要求掌握理解并查集在Kruskal中的作用即可 最短路径 Dijkstra算法Floyd算法 拓扑排序算法ACE常考选择题关键路径算法 ACE常考选择题并查集
