图的基本定义

图的表示方式与基本运作

表示方式

相邻矩阵

若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 1short 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)的活动称为临界活动