带权图的边结点中保存该边上的权值 cost 顶点i的边链表的表头指针a在顶点表的 下标为i的顶点记录中,该记录还保存了该 顶点的其它信息。 在邻接表的边链表中,各个边结点的链入 顺序任意,视边结点输入次序而定。 设图中有n个顶点,e条边,则用邻接表表 示无向图时,需要n个顶点结点,2e个边 结点;用邻接表表示有向图时,若不考虑 逆邻接表,只需n个顶点结点,e个边结点
◼ 带权图的边结点中保存该边上的权值cost。 ◼ 顶点 i 的边链表的表头指针 adj 在顶点表的 下标为 i 的顶点记录中，该记录还保存了该 顶点的其它信息。 ◼ 在邻接表的边链表中，各个边结点的链入 顺序任意，视边结点输入次序而定。 ◼ 设图中有 n 个顶点，e 条边，则用邻接表表 示无向图时，需要 n 个顶点结点，2e 个边 结点；用邻接表表示有向图时，若不考虑 逆邻接表，只需 n 个顶点结点，e 个边结点
邻接表表示的图的定义 const int Num vertices=10;11点个数 typedef char VertexData;/点数据类型 typedef int EdgeData ∥/边上权值类型 typedef struct node t ∥/边结点 int dest: /目标顶点下标 EdgeData cost ∥/边上的权值 Struct node x link: /下一边链接指针 3 Edgenode;
邻接表表示的图的定义 const int NumVertices = 10; //顶点个数 typedef char VertexData; //顶点数据类型 typedef int EdgeData; //边上权值类型 typedef struct node { //边结点 int dest; //目标顶点下标 EdgeData cost; //边上的权值 Struct node * link; //下一边链接指针 } EdgeNode;
ty pede struct /项点结点 VertexData data /项点数据域 EdgeNode firstAdj,∥边链表头指针 3 Vertex Node, typedef struct t /图的邻接表 VertexNode VexList [Num Vertices;∥邻接表 int n e. /图中当前的顶点个数与边数 3 Digraph;
typedef struct { //顶点结点 VertexData data; //顶点数据域 EdgeNode * firstAdj; //边链表头指针 } VertexNode; typedef struct { //图的邻接表 VertexNode VexList [NumVertices]; //邻接表 int n, e; //图中当前的顶点个数与边数 } AdjGraph;
图的遍历与连通性 从已给的连通图中某一顶点出发,沿着一 些边访遍图中所有的顶点,且使每个顶点 仅被访问一次,就叫做图的遍历( Graph Traversal)。 图中可能存在回路,且图的任一顶点都可 能与其它顶点相通,在访问完某个顶点之 后可能会沿着某些边又回到了曾经访问过 的顶点 为了避免重复访问,可设置一个标志顶点 是否被访问过的辅助数组 visited I
图的遍历与连通性 ◼ 从已给的连通图中某一顶点出发，沿着一 些边访遍图中所有的顶点，且使每个顶点 仅被访问一次，就叫做图的遍历( Graph Traversal )。 ◼ 图中可能存在回路，且图的任一顶点都可 能与其它顶点相通，在访问完某个顶点之 后可能会沿着某些边又回到了曾经访问过 的顶点。 ◼ 为了避免重复访问，可设置一个标志顶点 是否被访问过的辅助数组visited [ ]
辅助数组 visited的初始状态为0,在图 的遍历过程中,一旦某一个顶点i被访问 就立即让 visited为1,防止它被多次访 问。 图的遍历的分类: ◆深度优先搜索 DFS Depth First Search) ◆广度优先搜索 BFS (Breadth First Search)
◼ 辅助数组 visited [ ] 的初始状态为 0, 在图 的遍历过程中, 一旦某一个顶点 i被访问, 就立即让 visited [i] 为 1, 防止它被多次访 问。 ◼ 图的遍历的分类: ◆ 深度优先搜索 DFS (Depth First Search) ◆ 广度优先搜索 BFS (Breadth First Search)