图的基本定义

图的表示方式与基本运作

表示方式

• 相邻矩阵

  若G(V,E)是含n个顶点的图，表示图G的矩阵为mat[n][n]

    存在边的矩阵为mat[i][j]=1
    不存在边的矩阵为mat[i][j]=0
  

• 无向图

  

    无向图的相邻矩阵为对称
  

• 有向图

  

    有向图的相邻矩阵为非对称
  

• 相邻串链

• 无向图

  

• 有向图

  

  一维的表示法

  • 因上述的串链表示法空间需求较大，因此可改为一维的方式将图中所有顶点将图中所有顶点集合。

  • 阵列的空间表示方式为mat[n+2e+1]，n为顶点数，2e为顶点数*分支度。
    

      以G4为例，索引0~8为阵列的初始位置，9~22为储存值
    

实作连结:矩阵串链表示法

• 相邻多重串链

  
  

  先略

基本运作

追踪

• 深度追踪

  演算法

  #define FALSE 0
  #define TRUE 1
  short int visited[MAX_VERTICES];
  void dfs(int v){
    node_pointer w;
    visited[v]= TRUE;
    printf(“%5d”, v);
    for (w=graph[v]; w; w=w->link)
      if (!visited[w->vertex]){
        dfs(w->vertex);
      }
  }
  

  时间复杂度:
  • 相邻串链:O(e)
  • 相邻矩阵:O(n^2)

• 广度追踪

  演算法

    typedef struct queue *queue_pointer;
    typedef struct queue {
                    int vertex;
                    queue_pointer link;
    };
    queue_pointer front, rear;
    void addq(int);     // int 为顶点编号
    int deleteq();
    void bfs(int v){
        node_pointer w;
        front = rear = NULL;
        printf(“%5d”, v);
        visited[v] = TRUE;
        addq(v);
        while (front) {
          v= deleteq();
          for (w=graph[v]; w; w=w->link)
              if (!visited[w->vertex]) {
                  printf(“%5d”, w->vertex);
                  addq(w->vertex);
                  visited[w->vertex] = TRUE;
              } 
          }   
    } 
  

  时间复杂度:
  • 相邻串链:O(e)
  • 相邻矩阵:O(n^2)

实作连结:DFS与BFS追踪

扩张树(Spanning Trees)

定义:

• 1.包含一个图所有的顶点和部分的边形成的树，也称生成树
• 2.若图形式相连的，从任一节点追踪都会拜访到所有的顶点
• 3.当加入一个非树之边时，此扩张树会形成回路
  
• 4.深度优先扩张树(Depth First Spanning tree):利用DFS产生的扩张树
  
• 5.广度优先扩张树(Breadth First Spanning tree):利用BFS产生的扩张树
  
• 6.一个具有n个顶点的连接图最少有n-1个边;具有n-1个边的连接图即为树

最小成本扩张树(Minimum Cost Spanning Trees)

一个所有边具有成本权重的无向图，其最小成本和为最小成本扩张树

以下为利用贪婪法(greedy method)生成最小成本扩张树的演算法

• Kruskal’s 演算法
  一次以最小成本加一个边，当天家的边产生回圈则跳过

  
  
  演算法

  T= {};
  while (T 包含少於 n-1 个边且 E 不是空集合) {
        从E选择一个最小成本之边 (v, w) ;
        从E删除 (v, w)边;
        若边(v, w) 不会在T中产生回圈，则
            将 (v, w)边加入T中
        否则
            放弃(v, w)边;
  }
  若T包含少於 n-1个边，则
        印出”无扩张树”之讯息;
  

• Prim’s 演算法
  每次加一个周围最小成本的边加入树中，每一次添加後还是一棵树，直到这棵树包含n-1个边为止
  
  演算法:

  T={};
  TV={0};  /* 从顶点0开始 */
  while (T包含少於 n-1个边) {
      令 (u, v) 为最小成本之边，使得 u ? TV   
                      且 v ? TV
      若无此种边则停止;否则
      将顶点 v 加入 TV;
      将边 (u, v) 加入T;
  }
  若T包含少於 n-1个边，则
        印出”无扩张树”之讯息;
  
  

• Sollin’s 演算法
  待补
  
  

最短路径

找出单一来源到所有顶点的最短路径

图表法

Dijkstra’s 演算法
步骤:

• 插入第一个顶点至树中
  从树中每一顶点检查至尚未包括在树中的每一邻点总长度，选择具最小长度边插入树中
• 重复上述步骤，直到所有顶点均包含在树中为止
• 此法不得应用於边具有负权重值之图形

所有序对时间复杂度:
最短路径法O(n^2)*执行n次=O(n^3)

AOV网路

• 有向图中的工作次序关系

• 前辈一定出现在继承者前面
  

  图形中的拓朴次序(Topological order)

AOE网路

• 最早时间(e) :一个活动可以发生的最短时间

• 最晚时间(l) :一个活动可以发生的最迟时间

• 临界程度 (时间伸缩程度):l(i) - e(i) 的差值

  e(i)=l(i)的活动称为临界活动