Benature
0%

基本算法简要

Posted on Edited on

算法知识简要大纲

抽象数据类型(Abstract Data Type, ADT)
抽象数据类型的特征是 实现 与 操作 分离，从而实现 封装 。
抽象数据类型体现了程序设计中 问题分解 和 信息隐藏 的特征。它把问题分解为多个规模较小且容易处理的问题，然后把每个功能模块的实现为一个独立单元，通过一次或多次调用来实现整个问题。

算法分析

递归简论

  1. 基准情况：在某一情况下无须递归就会 return。
  2. 不断推进：每一次递归都往基准推进。
  3. 设计法则：所有递归都能调用。
  4. 合成效益法则：在同一个问题中，勿在不同递归调用中做同一个工作

时间复杂度

(大概是看看就好了吧)

  • 定义：如果存在正常数$𝑐$和$𝑛_0$, 使当$𝑁≥𝑛_0$时$𝑇(𝑁)≤𝑐𝑓(𝑁)$, 则记为$𝑇(𝑁)=\mathcal{O}(𝑓(𝑁))$
  • 定义：如果存在正常数$𝑐$和$𝑛_0$, 使当$𝑁≥𝑛_0$时$𝑇(𝑁)≥𝑐𝑔(𝑁)$, 则记为$𝑇(𝑁)=Ω(𝑔(𝑁))$
  • 定义：$𝑇(𝑁)=Θ(ℎ(𝑁)$当且仅当$𝑇(𝑁)=\mathcal{O}(ℎ(𝑁))$且$𝑇(𝑁)=Ω(ℎ(𝑁))$
  • 定义：如果$𝑇(𝑁)=\mathcal{O}(𝑝(𝑁))$且$𝑇(𝑁)≠Ω(𝑝(𝑁))$, $𝑇(𝑁)=\mathcal{O}(𝑝(𝑁))$
名称 运行时间 T(N) 算法举例
常数时间 $\mathcal{O}(1)$ 判断一个二进制数的奇偶
对数时间 $\mathcal{O}(log⁡N)$ 二分搜索
（小于 1 次）幂时间 $\mathcal{O}(N^c)$其中$0<c<1$ K-d 树的搜索操作
线性时间 $\mathcal{O}(N)$ 无序数组的搜索
线性对数时间 $\mathcal{O}(N\log{⁡N})$ 最快的比较排序
二次时间 $\mathcal{O}(N^2)$ 冒泡排序、插入排序
三次时间 $\mathcal{O}(N^3)$ 矩阵乘法的基本实现，计算部分相关性
指数时间 $\mathcal{O}(2^N)$ /
时间复杂度
  • 计算时间复杂度
    • 一层循环的时间复杂度为$𝑂(𝑁)$
    • 多层嵌套循环的时间复杂度是每层循环的时间复杂度之积$𝑂(𝑁^n)$
    • if…else… /case…switch…语句中取各个分支中最长的时间作为时间开销

表、栈、队列

表 ADT(链表) List

习惯上会留出一个 标志节点 , 有时称之为 表头(header) 或 哑节点(dummy node)

1
2
3
4
5
6
7
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;
// series of functions
// ......
  • 结构体定义
1
2
3
4
5
struct Node{
    ElementType Element;
    Position Next;
    // 可以加一个前置节点, 则成为双链表
};
  • Find 查询
    其实就是从头遍历
1
2
3
4
5
6
7
8
Position Find( ElementType X, List L){
    Position P;
    P = L->Next;
    while( P != NULL && P->Element != X){
        P = P->Next;
    }
    return P;
}
  • FindPrevious 查询前一个节点
    和 Find 类似, 区别仅在 line2,3
1
2
3
4
5
6
7
8
Position FindPrevious( ElementType X, List L){
    Position P;
    P = L;
    while(P->Next != NULL && P->Next->Element != X){
        P = P->Next;
    }
    return P;
}
  • Delete 删除
1
2
3
4
5
6
7
8
9
void Delete( ElementType X, List L){
    Position P, TmpCell;
    P = FindPrevious(X, L);
    if ( !IsLast( P, L) ){
        TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free(TmpCell); // 及时释放内存空间
    }
}
  • Insert 插入
1
2
3
4
5
6
7
8
9
10
11
void Insert( ElementType X, List L, Position P){
    Position TmpCell;
    TmpCell = malloc( sizeof (struct Node));
    if (TmpCell == NULL){
        // FatalError("Out of space!!!");
        printf("Out of space!!!");
    }
    TmpCell->Element = X;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}
  • 其他类型
    • 双链表
    • 循环链表
    • 多重表
  • 基数排序(radix sort)
    • 低位排序 LSD
    • 高位排序 MSD
  • 游标(cursor)实现法
    需要链表又不能使用指针(如 BASIC 和 FORTRAN 等)

栈 ADT Stack

又名 LIFO(先进后出)表
基本上就Pop(出栈)和Push(进栈)操作

  • 实现

    • 链表实现
      主要时间花费在于分配新空间和删除弹出的结点
    • 数组实现
      唯一潜在危害: 需要提前声明一个数组大小

  • 应用

    • 后缀表达式
    • 中缀到后缀的转换
    • 函数调用
      • 尾递归(TODO:未懂)
        执行的任何递归调用是在这种情况下的最后操作,而且通过封闭递归,递归调用的返回值(若有)立即返回.
        必须是 线性递归 (递归内只调用一个新的递归)
    • 平衡符号
平衡符号

队列 Queue

  • 基本操作
    • Enqueue 入队 : 在表的末端(队尾 rear)插入一个元素
    • Dequeue 出队 : 删除 / 返回 表的开头(队头 front)
  • 实现
    • 链表实现
    • 数组实现(循环数组 circular array 实现)
  • 应用
    • 排队论(queueing theory)

树 Tree

预备知识

  • 基本术语
术语 定义
根(root) /
边(edge) 连接节点的有向线
- - - - - -
子节点(child) 一个节点含有的子树的根节点称为该节点的子节点
父节点(parent) 若一个节点含有子节点，则这个节点称为其子节点的父节点
兄弟节点(sibling) 具有相同父节点的节点互称为兄弟节点
堂兄弟节点 双亲在同一层的节点互为堂兄弟
祖先(grandparent) 从根到该节点所经分支上的所有节点
子孙(grandchild) 以某节点为根的子树中任一节点都称为该节点的子孙
- - - - - -
树叶(leaf) 没有子节点的节点
从节点$n_1$到$n_k$的路径(path) 节点$n_1, n_2, \cdots,n_k$的一个序列
路径的长(length) 路径上边的条数
深度(depth) 从根到$n_i$的位移路径的长
高度(height) 从$n_i$到一片树叶的最长路径的长
树的高度或深度 树中节点的最大层次
- - - - - -
非终端节点或分支节点 度不为 0 的节点
节点的层次 从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推
节点的度 一个节点含有的子树的个数称为该节点的度
树的度 一棵树中，最大的节点的度称为树的度
森林 由 m（m>=0）棵互不相交的树的集合称为森林
  • 种类
    • 无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;
    • 有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；
    • 二叉树：每个节点最多含有两个子树的树称为二叉树；
    • 完全二叉树
    • 满二叉树
    • 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

遍历

遍历顺序 应用 顺序 动画
先序遍历 显示文件夹结构 中->左->右 :前序遍历
后序遍历 计算文件夹总大小 左->右->中 :后序遍历
中序遍历 表达式树 左->中->右 :中序遍历
层序遍历 :层序遍历

二叉树

动画

  • 种类: 表达式树, 查找树 ADT——二叉查找树
  • Head File
1
2
3
4
5
6
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
typedef int ElementType;
// series of functions
// ......
  • 结构体定义
1
2
3
4
5
struct TreeNode{
    ElementType Element;
    SearchTree Left;
    SearchTree Right;
};
  • Find 查询
1
2
3
4
5
6
7
8
9
10
11
12
Position Find( ElementType X, SearchTree T){
    if (T==NULL){
        return NULL;
    }
    if(X<T->Element){// 元素大了
        return Find(X,T->Left);// 去找左边小一点的
    }else if(X>T->Element){
        return Find(X,T->Right);
    }else{
        return T;// 返回后类型变为Position了
    }
}
  • Insert 插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
SearchTree Insert( ElementType X, SearchTree T){
    if (T==NULL){
        //创建并返回一个一节点树
        T = malloc(sizeof(struct TreeNode));
        if (T==NULL){
            printf("out of space!!!");
        }else{
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    }else if(X < T->Element){
        T->Left = Insert(X,T->Left);
    }else if(X > T->Element){
        T->Right = Insert(X,T->Right);
    }else{
        printf("%d is already in tree...\n",X);
    }
    return T;
}
  • Delete 删除节点
1
//TODO:
  • PrintTree 打印树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void PrintTree( SearchTree T,int space,int LR,int *N){
    // LR: 标志左右节点的参数,用以打印`/`或`\`
    // *N: 打印前N个节点
    int len = 10; // 每一层的打印间距(空格)
    if (T!=NULL && (*N)>0){
        (*N)--;
        PrintTree(T->Right,space+len,1,N);
        for (int loop = 0;loop<space; loop++){
            printf(" ");
        }
        if(LR==1){
            printf("/");
        }else if(LR==0){
            printf("\\");
        }
        printf("%-6d\n",T->Element);
        PrintTree(T->Left,space+len,0,N);
    }
}

AVL 树 (Adelson-Velsky 和 Landis)

动画

  • 定义: 每个节点的左子树和有字数的高度最大相差 1 的二叉查找树
  • 深度: $\mathcal{O}(\log{N})$
  • 旋转
    • 单旋转
      相邻子树高度相差大于等于 2
    • 双旋转
      相邻子树高度相差为 1

伸展树 splay tree

  • 基本想法: 当一个节点被访问后,它就要经过一系列 AVL 树的旋转被放到根上
  • 两种情况
    • 之字形(zig-zag): AVL 双旋转
    • 一字形(zig-zig): AVL 单旋转两次

B-树 (B-tree)

不是二叉树的查找树

  • 称呼
    • 4 阶 B-树 == 2-3-4 树
    • 3 阶 B-树 == 2-3 树

考试好像不考但是先马克这个博客吧

分析树

这个好像也不考

哈希 Hash

又名散列

哈希函数

  • 简单
    1
    2
    3
    Index HashNormal(ElementType Key, int TableSize){
      return Key%TableSize;
    }
  • 优秀
    1
    2
    3
    4
    5
    6
    7
    8
    Index HashBeautifully(ElementType Key, int TableSize){
    ElementType * ptrKey = &Key;
    unsigned int HashVal = 0;
    while (*ptrKey !='\0'){
        HashVal = (HashVal << 5) + *ptrKey++;
    }
    return HashVal % TableSize;
    }

分离链表法(拉链法)

  • 头文件

    1
    2
    3
    4
    5
    6
    struct ListNode;
    typedef struct ListNode *Position;
    struct HashTbl;
    typedef struct HashTbl *HashTable;
    typedef int ElementType;
    typedef int Index;

  • 初始化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    HashTable
    InitializeTable(int TableSize){
      HashTable H;
      int i;
      if (TableSize < MinTableSize){
          printf("Table size too small");
          return NULL;
      }
      // allocate table
      H = malloc(sizeof(struct HashTbl));
      if(H == NULL){
          printf("out of sapce !!!");
      }
      // allocate list headers
      for (i=0; i<H->TableSize; i++){
          H->TheLists[i] = malloc(sizeof(struct ListNode));
          if (H->TheLists[i]==NULL){
              printf("out of space !!!");
          }else{
              H->TheLists[i]->Next = NULL;
          }
      }
      return H;
    }

  • 结构体定义

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    struct ListNode{
        ElementType Element;
        Position Next;
    };

    typedef Position List;

    struct HashTbl{
        int TableSize;
        List *TheLists;
    };

  • Find

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    Position
    Find( ElementType Key, HashTable H, Index HashNum){
        Position P;
        List L;

        // L = H->TheLists[Hash(Key, H->TableSize)];
        L = H->TheLists[HashNum];
        P = L->Next;
        while(P!=NULL && P->Element!=Key){
            P=P->Next;
        }
        return P;
    }

  • Insert

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void
    Insert( ElementType Key, HashTable H, Index HashNum){
        Position Pos, NewCell;
        List L;
        Pos = Find(Key,H,HashNum);
        if(Pos == NULL){
            NewCell = malloc(sizeof(struct ListNode));
            if (NewCell == NULL){
                printf("out of space!!!");
            }else{
                // L = H->TheLists[Hash(Key,H->TableSize)];
                L = H->TheLists[HashNum];
                NewCell->Next = L->Next;
                NewCell->Element = Key;
                L->Next = NewCell;
            }
        }else{
            printf("already have it!\n");
        }
    }

  • 装填因子(load factor) $\lambda$

    尽量让表的大小与预料的元素个数差不多,即 $\lambda\approx 1$ .

开放定址法

  • 头文件

    1
    2
    3
    4
    5
    6
    7
    8
    typedef unsigned int Index;
    typedef Index Position;

    struct HashTbl;
    typedef struct HashTbl *HashTable;
    typedef int ElementType;
    // series of functions
    // ......

  • 基础声明

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #define MinTableSize 10
    extern int Collision_Square,Collision_Liner,Collision_Double;
    enum KindOfEntry{Legitimate,Empty,Deleted};

    struct HashEntry{
        ElementType Element;
        enum KindOfEntry Info;
    };

    typedef struct HashEntry Cell;

    // 哈希表
    struct HashTbl{
        int TableSize;
        Cell *TheCells;
    };

  • 初始化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    HashTable
    InitializeTable(int TableSize){
        HashTable H;
        int i;

        if(TableSize<MinTableSize){
            printf("Table Size too small");
            return NULL;
        }

        // allocate table
        H = malloc(sizeof(struct HashTbl));
        if (H == NULL){
            printf("out of space!!!\n");
        }
        H->TableSize = NextPrime(TableSize);

        // allocate array of cells
        H->TheCells = malloc(sizeof(Cell) * H->TableSize);
        if (H->TheCells == NULL){
            printf("out of space!!!\n");
        }

        for (i = 0;i<H->TableSize;i++){
            H->TheCells[i].Info = Empty;
        }
        return H;
    }

线性探测法

  • Find
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    Position
    FindByLiner(ElementType Key, HashTable H){
        Position CurrentPos;
        int CollisionNum;
        CollisionNum = 0;
        CurrentPos = HashNormal(Key,H->TableSize);
        while(H->TheCells[CurrentPos].Info != Empty &&  // 非空
              H->TheCells[CurrentPos].Element != Key){  // 不等于查询值
            CurrentPos++;
            CollisionNum++;
            if(CurrentPos >= H->TableSize){
                CurrentPos -= H->TableSize;             // 循环查找
            }
        }// 一旦找到就跳出循环
        Collision_Liner += CollisionNum;
        return CurrentPos;
    }

  • Insert

    1
    2
    3
    4
    5
    6
    7
    8
    void InsertByLiner(ElementType Key, HashTable H){
        Position Pos;
        Pos = FindByLiner(Key,H);
        if(H->TheCells[Pos].Info != Legitimate){// 该位置没有数据
            H->TheCells[Pos].Info = Legitimate;
            H->TheCells[Pos].Element = Key;
        }
    }

  • 一次聚集(primary clustering)
    占据的单元形成一些区块

  • 预期探测次数

    • 插入 / 不成功的查找
    • 成功的查找

平方散列法

  • 快速公式
    CurrentPos += 2 * ++CollisionNum - 1
  • Find
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    Position
    FindBySquare(ElementType Key, HashTable H){
        Position CurrentPos;
        int CollisionNum;
        CollisionNum = 0;
        CurrentPos = HashNormal(Key,H->TableSize);
        while(H->TheCells[CurrentPos].Info != Empty &&  // 非空
              H->TheCells[CurrentPos].Element != Key){  // 不等于查询值
            CurrentPos += 2 * ++CollisionNum - 1;       // 平方探测 快速方法
            if(CurrentPos >= H->TableSize){
                CurrentPos -= H->TableSize;             // 循环查找
            }
        }// 一旦找到就跳出循环
        Collision_Square += CollisionNum;
        return CurrentPos;
    }
  • Insert
    1
    2
    3
    4
    5
    6
    7
    8
    void InsertBySquare(ElementType Key, HashTable H){
        Position Pos;
        Pos = FindBySquare(Key,H);
        if(H->TheCells[Pos].Info != Legitimate){        // 该位置没有数据
            H->TheCells[Pos].Info = Legitimate;
            H->TheCells[Pos].Element = Key;
        }
    }

双(倍)散列

  • Find

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    Position
    FindByDouble(ElementType Key, HashTable H){
        Position CurrentPos;
        int CollisionNum = 0;
        int addDouble = HashDoubel(Key,7);
        CurrentPos = HashNormal(Key,H->TableSize);
        while(H->TheCells[CurrentPos].Info != Empty &&  // 非空
              H->TheCells[CurrentPos].Element != Key){  // 不等于查询值
            CurrentPos += addDouble;
            CollisionNum++;
            if(CurrentPos >= H->TableSize){
                CurrentPos -= H->TableSize;             // 循环查找
            }
        }// 一旦找到就跳出循环
        Collision_Double += CollisionNum;
        return CurrentPos;
    }

  • Insert

    1
    2
    3
    4
    5
    6
    7
    8
    void InsertByDouble(ElementType Key, HashTable H){
        Position Pos;
        Pos = FindByDouble(Key,H);
        if(H->TheCells[Pos].Info != Legitimate){        // 该位置没有数据
            H->TheCells[Pos].Info = Legitimate;
            H->TheCells[Pos].Element = Key;
        }
    }

再散列

当表有超过 70% 的单元是满的, 建立新表
新表大小是原表大小两倍后的第一个素数

  • 实现
    • 表满一半就再散列
    • 当插入失败是才再散列
    • 途中(middle-of-the-road)策略 : 当表达到某个装填因子时进行再散列

可扩散列

略

优先队列（堆） Heap

二叉堆 binary heap

动画
堆是一刻完全二叉树(complete binary tree)

  • 堆序性 heap order
    • 最小元在根上
    • 任意节点小于其所有后裔

基本堆操作

  • Insert

    • 上滤
      加在队尾然后向上排序
    • 标记 sentinel
      通过添加一条 哑信息(dummy piece of information) , 避免在插入新的最小值时每个循环都执行一次的测试

  • DeleteMin

    • 下滤
      删除根, 队尾换到队头, 向下排序

应用

  • 选择问题
  • 时间模拟

d-堆

略 TODO:

左式堆

略 TODO:

斜堆

略 TODO:

二项队列

略 TODO:

图论 Graph

基本概念

  • 图(Graph) 是 顶点(Vertex) 和 边(Edge) 的集合。边是对任意两个顶点的连接。

基本术语

术语 定义
阶（Order） 图中顶点的个数
尺寸（Size） 图中边的个数
子图（Sub-graph） 一个图的顶点与边的子集。即，当$𝑉(𝐺’)∈𝑉(𝐺)$并且$𝐸(𝐺’ )∈𝐸(𝐺)$时，$𝐺’$是$𝐺$的一个子图
生成子图（Sub-graph） 当$𝐺’$是$𝐺$的子集，并且$𝑉(𝐺’ )=𝑉(𝐺)$时， $𝐺’$是$𝐺$的一个生成子图
度（Degree） 一个顶点 𝑣 的度是与它相连的边的数量，记作 𝑑(𝑣)。$\sum_{\nu \in V}d(\nu)=2 \mid E \mid$
出度（In-degree） 出度为从该顶点出发的边的个数
入度（Out-degree） 入度为终点时该节点的边的个数
路径（Path） 路径经过的边数为 𝑘，即路径长度为$𝑘$
简单路径（simple-path） 路径的所有顶点都不相同或只有起点$𝑣0$和终点$𝑣𝑘$两个顶点相同
圈（cycle） 在有向图中路径起点$𝑣0$和终点$𝑣𝑘$相同。若满足简单路径的条件则是一个简单圈。
距离 两个顶点之间的最短路径长度就是两点之间的距离

图的分类

  • 按边
类型 定义
简单图（simple graph） 既没有平行边，也没有自环
多重图（multi-graph） 有平行边的图
伪图（Pseudograph） 既有平行边的图，也有自环的图
完全图 每对顶点之间都有边的图是完全图

有的作者也允许多重图有自环

类型
  • 按路径
类型 定义
连通图 一个图中的每个顶点到其他顶点都有路径
强连通图 有向图满足该条件
弱连通图 有向图不连通，但是它的基础图连通

基础图: 边去掉方向的图

  • 按方向
    有向图与无向图
  • 按权重
    有权图与无权图

存储显示方式

邻接矩阵 adjacency matrices

邻接矩阵使用$|V|∗|V|$的二维数组来表示图。$g[i][j]$表示的是顶点$i$和顶点$j$的关系。

  • 无向图
    只需要知道顶点$i$和顶点$j$是否是相连的，因此我们只需要将$g[i][j]$和$g[j][j]$设置为 1 或是 0 表示相连或不相连即可。
    邻接矩阵
  • 有向图
    只需要知道是否有从顶点$i$到顶点$j$的边，因此如果顶点$i$有一条指向顶点$j$的边，那么$g[i][j]$就设为 1，否则设为 0。有向图与无向图不同，并不需要满足$g[i][j]=g[j][i]$
    邻接矩阵

  • 有权图
    在带权值的图中，g[i][j]表示的是顶点 i 到顶点 j 的边的权值。由于在边不存在的情况下，如果将 g[i][j]设为 0，就无法和权值为 0 的情况区分开来，因此选取适当的较大的常数 INF（只要能和普通的权值区别开来就可以了），然后令 g[i][j]=INF 就好了。当然，在无向图中还是要保持 g[i][j]=g[j][i]。在一条边上有多种不带权值的情况下，定义多个同样的|V|∗|V|数组，或者是使用结构体或类作为数组的元素，就可以和原来一样对图进行处理了。
    邻接矩阵

  • 优点
    很方便地判断任意两个顶点之间是否有边以及确定顶点的度

  • 缺点
    在这种表示法中扫描所有边至少需要 O(n2)时间，因为必须检查矩阵中的 n2−n 个元素才能确定图中边的条数（邻接矩阵对角线上的 n 个元素都是 0，因此不用检查。又因为无向图的邻接矩阵是对称的，实际只需检查邻接矩阵的一半元素）。
    通常把边很少的图成为稀疏图（sparse graphs）。如果用邻接矩阵表示稀疏图就会浪费大量内存空间

邻接表

  • 优点: 只需$\mathcal{O}(|V|+|E|)$的内存空间
    邻接表
1
2
3
4
5
6
7
8
#define MAX_VERTICES 50
typedef struct node *node-pointer;
typedef struct node {
    int vertex;
    struct node *link;
};
node_pointer graph[MAX_VERTICES];
int n=0;

链接多重表

在无向图的邻接表存储表示中，每一条边$(v_i，v_j)$
都表示为两项：一项在顶点 vi 的邻接表中，而另一项在顶点 $v_j$ 的邻接表中。在多重表中，各链表中的结点可以被几个链表共享，此时图中的每一条边只对应于一个结点，而这个结点出现在该边所关联的两个顶点的每个邻接链表中。

1
2
3
4
5
6
7
8
typedef struct edge *edge-pointer
typedef struct edge {
    short int marked;
    int vertex1;
    int vertex2;
    edge_pointer path1;
    edge_pointer path2;
};

操作

拓扑排序

最短路径

略……

参考资料：