图的存储衰示 邻接表 口无向图的邻接表 dest link dest link data link 2 ABCD 0 3 顶点数组 链接结点 dest保存的是邻接顶点的下标 12
图的存储表示 ◼ 邻接表 无向图的邻接表 12 B D C A 1 2 0 0 3 C B D A 1 2 1 3 0 data link dest link dest link dest保存的是邻接顶点的下标 顶点数组 链接结点
图的存储衰示 邻接表 有向图的邻接表和逆邻接表 data link dest link 0 A dest link BC 0 2 邻接表出边表 data link dest link ABC 1=02 13 逆邻接表(入边表
图的存储表示 ◼ 邻接表 有向图的邻接表和逆邻接表 13 1 0 2 C B A 2 1 0 data link dest link B C A 1 0 C 2 B A 2 1 0 data link dest link dest link 邻接表(出边表) 逆邻接表(入边表)
图的存储表示 a网络(带权图)的邻接表 86 B dest cost link dest cost link data link 24|∧ 0 A 22 39∧ B 36入 03 15 2|8∧ 邻接表出边表) 14
图的存储表示 ◼ 网络(带权图)的邻接表 14 邻接表(出边表) D C A B 8 6 3 9 5 2 1 4 C B D A 2 1 3 0 data link cost link 0 3 3 6 2 2 1 1 2 4 dest dest cost link 3 9 1 5 2 8
图的遍历 ■从给定顶点出发,沿某些边遍历图中所有顶点 次且仅一次 n使用辅助数组 visited[]标识顶点是否被访问过 口 visited]初始为0 n访问过后标识为1 15
图的遍历 ◼ 从给定顶点出发，沿某些边遍历图中所有顶点 一次且仅一次 ◼ 使用辅助数组visited[ ]标识顶点是否被访问过 visited[ ]初始为0 访问过后标识为1 15
图的遍历 n遍历方式 口深度优先遍历DFs( Depth First Search) 口广度优先遍历BFs( Breadth First search) 16
图的遍历 ◼ 遍历方式 深度优先遍历 DFS (Depth First Search) 广度优先遍历 BFS (Breadth First Search) 16