基本算法简要

Posted on Edited on Views: Valine:

算法知识简要大纲

抽象数据类型(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
struct Node;
2
typedef struct Node *PtrToNode;
3
typedef PtrToNode List;
4
typedef PtrToNode Position;
5
typedef int ElementType;
6
// series of functions
7
// ......
  • 结构体定义
1
struct Node{
2
    ElementType Element;
3
    Position Next;
4
    // 可以加一个前置节点, 则成为双链表
5
};

  • Find 查询
    其实就是从头遍历

    1
    Position Find( ElementType X, List L){
    2
        Position P;
    3
        P = L->Next;
    4
        while( P != NULL && P->Element != X){
    5
            P = P->Next;
    6
        }
    7
        return P;
    8
    }

  • FindPrevious 查询前一个节点
    和Find类似, 区别仅在line2,3

    1
    Position FindPrevious( ElementType X, List L){
    2
        Position P;
    3
        P = L;
    4
        while(P->Next != NULL && P->Next->Element != X){
    5
            P = P->Next;
    6
        }
    7
        return P;
    8
    }

  • Delete 删除

    1
    void Delete( ElementType X, List L){
    2
        Position P, TmpCell;
    3
        P = FindPrevious(X, L);
    4
        if ( !IsLast( P, L) ){
    5
            TmpCell = P->Next;
    6
            P->Next = TmpCell->Next;
    7
            free(TmpCell); // 及时释放内存空间
    8
        }
    9
    }

  • Insert 插入 

    1
    void Insert( ElementType X, List L, Position P){
    2
        Position TmpCell;
    3
        TmpCell = malloc( sizeof (struct Node));
    4
        if (TmpCell == NULL){
    5
            // FatalError("Out of space!!!");
    6
            printf("Out of space!!!");
    7
        }
    8
        TmpCell->Element = X;
    9
        TmpCell->Next = P->Next;
    10
        P->Next = TmpCell;
    11
    }
  • 其他类型
    • 双链表
    • 循环链表
    • 多重表
  • 基数排序(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
    struct TreeNode;
    2
    typedef struct TreeNode *Position;
    3
    typedef struct TreeNode *SearchTree;
    4
    typedef int ElementType;
    5
    // series of functions
    6
    // ......

  • 结构体定义

    1
    struct TreeNode{
    2
        ElementType Element;
    3
        SearchTree Left;
    4
        SearchTree Right;
    5
    };

  • Find 查询

    1
    Position Find( ElementType X, SearchTree T){
    2
        if (T==NULL){
    3
            return NULL;
    4
        }
    5
        if(X<T->Element){// 元素大了
    6
            return Find(X,T->Left);// 去找左边小一点的
    7
        }else if(X>T->Element){
    8
            return Find(X,T->Right);
    9
        }else{
    10
            return T;// 返回后类型变为Position了
    11
        }
    12
    }

  • Insert 插入

    1
    SearchTree Insert( ElementType X, SearchTree T){
    2
        if (T==NULL){
    3
            //创建并返回一个一节点树
    4
            T = malloc(sizeof(struct TreeNode));
    5
            if (T==NULL){
    6
                printf("out of space!!!");
    7
            }else{
    8
                T->Element = X;
    9
                T->Left = T->Right = NULL;
    10
            }
    11
        }else if(X < T->Element){
    12
            T->Left = Insert(X,T->Left);
    13
        }else if(X > T->Element){
    14
            T->Right = Insert(X,T->Right);
    15
        }else{
    16
            printf("%d is already in tree...\n",X);
    17
        }
    18
        return T;
    19
    }

  • Delete 删除节点

    1
    //TODO:

  • PrintTree 打印树

    1
    void PrintTree( SearchTree T,int space,int LR,int *N){
    2
        // LR: 标志左右节点的参数,用以打印`/`或`\`
    3
        // *N: 打印前N个节点
    4
        int len = 10; // 每一层的打印间距(空格)
    5
        if (T!=NULL && (*N)>0){
    6
            (*N)--;
    7
            PrintTree(T->Right,space+len,1,N);
    8
            for (int loop = 0;loop<space; loop++){
    9
                printf(" ");
    10
            }
    11
            if(LR==1){
    12
                printf("/");
    13
            }else if(LR==0){
    14
                printf("\\");
    15
            }
    16
            printf("%-6d\n",T->Element);
    17
            PrintTree(T->Left,space+len,0,N);
    18
        }
    19
    }

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

    分离链表法(拉链法)

  • 头文件

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

  • 初始化

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

  • 结构体定义 

    1
    struct ListNode{
    2
        ElementType Element;
    3
        Position Next;
    4
    };
    5
    6
    typedef Position List;
    7
    8
    struct HashTbl{
    9
        int TableSize;
    10
        List *TheLists;
    11
    };

  • Find

    1
    Position 
    2
    Find( ElementType Key, HashTable H, Index HashNum){
    3
        Position P;
    4
        List L;
    5
    6
        // L = H->TheLists[Hash(Key, H->TableSize)];
    7
        L = H->TheLists[HashNum];
    8
        P = L->Next;
    9
        while(P!=NULL && P->Element!=Key){
    10
            P=P->Next;
    11
        }
    12
        return P;
    13
    }

  • Insert

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

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

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

开放定址法

  • 头文件
    1
    typedef unsigned int Index;
    2
    typedef Index Position;
    3
    4
    struct HashTbl;
    5
    typedef struct HashTbl *HashTable;
    6
    typedef int ElementType;
    7
    // series of functions
    8
    // ......

  • 基础声明

    1
    #define MinTableSize 10
    2
    extern int Collision_Square,Collision_Liner,Collision_Double;
    3
    enum KindOfEntry{Legitimate,Empty,Deleted};
    4
    5
    struct HashEntry{
    6
        ElementType Element;
    7
        enum KindOfEntry Info;
    8
    };
    9
    10
    typedef struct HashEntry Cell;
    11
    12
    // 哈希表
    13
    struct HashTbl{
    14
        int TableSize;
    15
        Cell *TheCells;
    16
    };

  • 初始化

    1
    HashTable 
    2
    InitializeTable(int TableSize){
    3
        HashTable H;
    4
        int i;
    5
    6
        if(TableSize<MinTableSize){
    7
            printf("Table Size too small");
    8
            return NULL;
    9
        }
    10
        
    11
        // allocate table
    12
        H = malloc(sizeof(struct HashTbl));
    13
        if (H == NULL){
    14
            printf("out of space!!!\n");
    15
        }
    16
        H->TableSize = NextPrime(TableSize);
    17
    18
        // allocate array of cells
    19
        H->TheCells = malloc(sizeof(Cell) * H->TableSize);
    20
        if (H->TheCells == NULL){
    21
            printf("out of space!!!\n");
    22
        }
    23
    24
        for (i = 0;i<H->TableSize;i++){
    25
            H->TheCells[i].Info = Empty;
    26
        }
    27
        return H;
    28
    }

线性探测法

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

  • Insert

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

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

  • 预期探测次数

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

平方散列法

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

双(倍)散列

  • Find

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

  • Insert

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

再散列

当表有超过 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
    #define MAX_VERTICES 50 
    2
    typedef struct node *node-pointer; 
    3
    typedef struct node { 
    4
        int vertex; 
    5
        struct node *link; 
    6
    }; 
    7
    node_pointer graph[MAX_VERTICES]; 
    8
    int n=0;

链接多重表

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

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

操作

拓扑排序

最短路径

略……

参考资料：