北工商复习资料-算法讲义.doc

第一章
抽象数据类型(ADT)：是指一个数学模型以及定义在该模型上的一组操作。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
数据的逻辑结构：元素间关系的表示，是具体关系的抽象。
数据的存储结构：数据结构在计算机内存中的表示
顺序存储结构：把逻辑上相邻的元素存储在物理位置相邻的存储单元里，元素间的逻辑关系由存储单元的相邻关系来体现，由此得到的存储表示称为顺序存储结构。
链式存储结构：对逻辑上相邻的元素不要求其物理位置相邻，元素之间的逻辑关系通过附设指针字段表示，由此得到的存储表示称为链式存储结构。
算法：是为了解决某类问题而规定的一个有限长的操作序列。
算法的五个特性：
1、有穷性:对于任意一组合法输入值，在执行有穷步骤之后一定能结束。
2、确定性:组成算法的操作必须清晰无二义性。
3、可行性(有效性):组成算法的操作必须能够在计算机上实现。
4、有输入:0个或多个输入；
5、有输出 :1个或多个输出；
如何衡量一个正确算法的好坏？
衡量的三个尺度：
• 运行所花费的时间（算法的时间特性）；
• 所占用存储空间的大小（算法的空间特性）；
• 其它（正确性、可读性、健壮性等）。
第二章 线性表
一、概念
1.线性表：线性表是n 个类型相同数据元素的有限序列，通常记作（a1, a2, a3, …, an ）。
2.线性表的顺序存储结构：用一组连续的内存单元依次存放线性表的数据元素。
3.线性表的链式存储结构
（1）线性链表（单链表）：用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。
（2）双向链表：双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。
（3）循环链表：循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点。
二、算法
1．线性表的基本运算（不同存储结构下，线性表基本运算的特点）：
①初始化操作 InitList_Sq( SqList &L)
功能：建立空的顺序表L
Status InitList_Sq(SqList &L){
//构造一个空的顺序表L
L.elem=(ElemType* ) malloc (LIST_INIT_SIZE * sizeof(ElemType) );
if (! L.elem) exit(OVERFLOW); //存储分配失败
L. length=0; //空表长度为0
L.listsize = LIST_INIT_SIZE; //初始存储容量
return OK;
} //InitList_Sq
②销毁操作 DestroyList_Sq(SqList &L)
功能：回收为顺序表动态分配的存储空间
Status DestroyList_Sq(SqList &L){
if(!L.elem) return ERROR; //若表L不存在
free(L.elem); //若表L已存在，回收动态分配的存储空间
L.elem = NULL;
L.length = 0;
L.Listsize = 0;
return OK;
} //DestroyList_Sq
③置空操作ClearList_Sq ( SqList &L)
功能：若L已存在，重新将其置成空表；
Status ClearList_Sq ( SqList &L) {
if (!L.elem) return ERROR; // 若表L不存在
L.length = 0; //若表L已存在，将L置空
return OK;
}// ClearList_Sq
Status ClearList_Sq(SqList *L)
{ free (L.elem);
L.elem =( ElemType*)malloc(LIST_INIT_SIZE*
sizeof(ElemType));
if(!L.elem) exit(OVERFLOW);
L.length = 0;
L.Listsize = LIST_INIT_SIZE;
return OK;
}
④取元素操作GetElem_Sq(SqList L,int i, ElemType &e )
功能：将顺序表中第i 个元素赋值给 e
Status GetElem_Sq ( SqList *L, int i, ElemType &e ) {
if ((i< 1)||( i > L.length -1)) return ERROR; // i 非法
e = L.elem [ i-1 ]; // 将顺序表中第i 个元素赋值给 e
return OK;
} // GetElem_Sq
⑤插入操作 ListInsert_Sq ( &L, i, e )
功能：在顺序表L的第i个元素之前插入一个新元素e;
Status ListInsert_Sq(SqList &L, int i , ElemType e) {
//在顺序表L中第i个位置之前插入新的元素e,
// i的合法值为1≤i≤L.length+1,当i =L.length+1时, e插在表尾
if (i<1|| i>L.length+1) return ERROR; // i值不合法
if (L.length>=L.listsize) return ERROR; //顺序表已满
for ( j=L.length-1 ; j>= i-1; --j) L.elem[j+1]= L.elem[ j];
//插入位置及之后的元素后移一个位置
L.elem[i-1] =e; //插入e
++L.length; //表长增1
return OK;
} //ListInsert_Sq
⑥删除操作 ListDelete_sq (SqList &L, int i, ElemType &e )
功能：删除顺序表L的第i个元素，并用e返回
Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{//在顺序表L中删除第 i个元素，并用e返回其值
// i的合法值为 1≤i≤L.length，
// 表空L.length=0 则i> L.length
if ((i<1)||(i>L.length)) return ERROR; // i值不合法或表空
e = L.elem[i-1]; // 被删除元素的值赋给e
for ( j= i; j<= L.length-1; ++j) L.elem[j-1] = L.elem[ j]
//被删除元素之后的元素前移
--L.length; //表长减1
return OK;
}//ListDelete_Sq
顺序表的特点：
①通过元素的存储顺序反映线性表中数据元素之间的逻辑关系；
②可随机存取顺序表的元素；
③顺序表的插入、删除操作要通过移动元素实现。
2.线性表的其他运算（简单应用）
①利用基本操作实现线性表的其它操作
例:将两个有序线性表(非递减有序排列)归并成一个有序线性表；
设线性表A、B分别用La 、 Lb 的两个顺序表存储。
实现上 述功能的算法有很多，我们采用第三种： 
1）将Lb并入La;
2）将La并入Lb;
3）将La、Lb并入Lc; (顺序表Lc中的空间是新分配的存储空间)
基本思想：同时对La.elem, Lb.elem 进行扫描，在扫描过程中按两表当前元素的大小，依次将其插入到Lc的表尾
Void MergeList_Sq(SqList *La, SqList *Lb, SqList &Lc){
//已知顺序表La和Lb中的数据元素按值非递减排列。
//归并La和Lb得到新的顺序表Lc,Lc的数据元素也按值非递减排列
InitList_Sq(&Lc)；
La_len=Listength_Sq(La); Lb_len=ListLength_Sq(Lb);
i=1;j=1;k=1;
While((i<=La_len)&&(j<=Lb_len)){ //La和Lb均非空
GetElem_Sq(La, i, ai); GetElem_Sq(Lb, j, bj);
if(ai<=bj) {ListInsert_Sq(&Lc, k, ai); ++i; ++k;}
else {ListInsert_Sq(&Lc, k, bj); ++j; ++k;}
}
while(i<=La_len) {
GetElem_Sq(La, i, ai); ListInsert_Sq(&Lc, k, ai); ++i; ++k;
}
while(j<=Lb_len){
GetElem_Sq(Lb, j, bj); ListInsert_Sq (&Lc, k,bj); ++j; ++k;
}
}//MergeList_Sq
②直接对顺序表进行操作实现归并算法
void MergeList_Sq(SqList *La, SqList *Lb, SqList &Lc){
//已知顺序表La和Lb的元素按值非递减排列
//归并La和Lb得到新的顺序表Lc,Lc的元素也按值非递减排列
pa=La.elem; pb=Lb.elem
Lc.listsize= Lc.length= La.length+Lb.length;
pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));
if(!Lc.elem)exit(OVERFLOW);//存储分配失败
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last &&pb<=pb_last){ //归并
if(*pa<=*pb)*pc++=*pa++;
else *pc++=*pb++;
}
while (pa<=pa_last) *pc++=*pa++; //插入La的剩余元素
while (pb<=pb_last) *pc++=*pb++; //插入Lb的剩余元素
}//MergeList_Sq
3.双向链表的插删除结点
1）插入操作算法
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){
//在带头结点的双链循环线性表L中第i个位置之前插入元素e，
//i的合法值为1≤i≤表长+1。
if(!p=GetElemP_DuL(L,i))) //在L中确定第i个元素的位置指针p
return ERROR; //p=NULL，即第i个元素不存在
//建新结点、
if (!(s=(DuLinkList)malloc(sizeof(DuLNode))))return ERROR;
s->data=e;
s->prior=p-prior; p->prior->next=s; // 完成插入图示中的①②
s->next=p; p->priors; //完成插入图示中的③④
return OK;
}//LinstInsert_DuL
2）删除操作算法
Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e){
//删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长
if(!p=GetElemP_DuL(L,i))) //在L中确定第i个元素的位置指针p
return ERROR; //p=NULL，第i个元素不存在
e = p->data;
p->prior->next = p->next; //完成删除图示中的①
p->next->prior = p->prior; //完成删除图示中的②
free(p);
return OK;
}//LinstDelete_DuL
第三章
一、栈
1、栈是限定仅能在表尾一端进行插入、删除操作的线性表。
2、栈的元素具有后进先出的特点。
3、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈、出栈操作要修改栈顶指针。
栈空的条件
s->top=s->base
栈满的条件
s->top-s->base>=stacksize
二、顺序栈基本操作的算法
空栈：top=0
满栈：top=MAXN
1、初始化操作InitStack(SqStack &S)
功能：建一个空栈S。
Status InitStack(SqStack &S)
{//构造一个空栈S
S.base = (SElemType * )malloc(STACK_INIT_SIZE ×
sizeof(SElemType));
//为顺序栈动态分配存储空间
if (! S. base) exit(OVERFLOW); //存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
} //InitStack_Sq
2、销毁栈操作 DestroyStack(SqStack &S )
功能：销毁一个已存在的栈。
Status DestroyStack( SqStack &S)
{
if (!S.base) return ERROR; //若栈未建立(尚未分配栈空间)
free (S.base); // 回收栈空间
S.base = S.top = NULL;
S.stacksize = 0;
return OK;
} // DestroyStack_Sq
3、出栈操作Pop(SqStack &S, SElemType &e )
功能：栈顶元素退栈，并用e 返回。
Status GetTop(SqStack S,SElemType &e){
// 若栈不空，则用e返回S的栈顶元素，
并返回OK；否则返回ERROR
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}
Status Pop (SqStack &S, SElemType &e) {
// 若栈不空，则删除S的栈顶元素，
// 用e返回其值，并返回OK；
// 否则返回ERROR
if (S.top == S.base) return ERROR;
e = *--S.top;
return OK;
}
4、进栈操作Push(SqStack &S, SElemType e)
功能：元素e 进栈;
Status Push(SqStack &S, SElemType e)
{//将元素e插入栈成为新的栈顶元素
if (S.top - S.base >= S.stacksize) { //栈满，追加存储空间
S.base= (SElemType * )realloc(S.base,
(S.stacksize +STACKINCREMENT) *
sizeof(SElemType));
if (! S. base) exit (OVERFLOW); //存储分配失败
S.top = S.base + S.stacksize;
S.stacksize + STACKINCREMENT;
}
*S.top++ = e; //元素e 插入栈顶，修改栈顶指针
return OK;
} //Push
三、队列
1、队列是限定仅能在表尾一端进行插入，表头一端进行删除操作的线性表；
2、队列中的元素具有先进先出的特点；队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示。
3、入队操作要修改队尾指针,出队操作要修改队头指针。
空：Q.front = Q.rear
满: (Q.rear+1)% MAXQSIZE = Q.front
四、循环队列——队列的顺序存储和实现

插入： 尾指针增1 Q.rear++;
删除： 头指针增1 Q.front++。
1、初始化操作 InitQueue_Sq(SqQueue &Q)
参数：Q是存放队列的结构变量；
功能：建一个空队列Q；
Status InitQueue_Sq(SqQueue &Q) {
//构造一个空队列Q
Q.base = (QElemType * )malloc (MAXQSIZE *sizeof
(QElemType));
if (!Q.base) exit (OVERFLOW); //存储分配失败
Q.front = Q.rear = 0;
return OK;
} // InitQueue_Sq
2、求队列长度
int QueueLength(SqQueue Q){
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
3、入队操作EnQueue_Sq(SqQueue &Q, QElemType e )
功能：将元素e插入队尾
Status EnQueue_Sq(SqQueue &Q, QElemType e ) //将元素e插入队尾
{ if ((Q.rear+1)%MAXQSIZE = = Q.front) return ERROR ; //队列满
Q.base[Q.rear] = e ; // 将元素e插入队尾
Q.rear = (Q.rear +1) % MAXQSIZE; // 修改队尾指针
return OK;
}// EnQueue_Sq
4、出队操作 DeQueue_Sq (SqQueue &Q, QElemType &e )
功能：删除队头元素，用e返回其值 ；
Status DeQueue_Sq(SqQueue &Q, QElemType &e ){
//删除队头元素，用e返回其值,并返回OK；否则返回ERROR
if ((Q.rear = = Q.front) return ERROR； //队空，出队失败
e = Q.base[Q.front] ; // 将队头元素取出，放入e中
Q.front = (Q.front +1) % MAXQSIZE; // 修改队头指针
return OK;
} // DeQueue_Sq
第六章 树和二叉树
一、二叉树
1.概念
（1）二叉树：二叉树或为空树,或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。
完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。即：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树。
二叉树的结构特征及证明方法：
性质 1 ：
在二叉树的第 i 层上至多有2i-1 个结点。(i≥1)
用归纳法证明：
归纳基：i = 1 层时，只有一个根结点：
2i1 = 20 = 1；
归纳假设：假设对所有的 j，1≤ j < i，命题成立；
归纳证明：二叉树上每个结点至多有两棵子树，
则第 i 层的结点数 = 2i-2´ 2 = 2i-1 。
性质2：深度为 k 的二叉树上至多含 2k-1 个结点(k≥1)。
证明：
由性质1可以得出，1至K层各层最多的结点个数分别为：20,21,22,23,...,2K-1。这是一个以2为比值的等比数列，前n项之和的计算公式为：

其中 a1为第一项，an为第n项，q为比值。可以得到，该数列前K项之和为：

故深度为 k 的二叉树上的结点数至多为 2k-1 个结点。
性质 3 ：
对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。
证明：
设 二叉树上结点总数 n = n0 + n1 + n2 …¼(1)式
从上往下看，二叉树上分支总数 b = n1+2n2 …¼(2)式
又只有根结点不是由分支带出的，故有： b = n-1 …¼(3)式
将(1)式带入(3)式得：b = n-1 = n0 + n1 + n2 - 1 …¼(4)式
(2)式和(4)式右边相等，得： n1+2n2 = n0 + n1 + n2 - 1
故有： n0 = n2 + 1 。

（2）二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树
令：L：遍历左子树 D：访问根结点 R：遍历右子树
约定先左后右,故对“二叉树”而言，可以有三条搜索路径，
即有三种遍历方法： DLR、LDR、LRD ，分别称为
先序遍历、中序遍历、后序遍历
按层遍历根据中、后序（或中、先序）可唯一确定一颗二叉树
（3）Huffman树：假设有n个权值{w1, w2, ... , ... wn},构造一棵有n个叶子结点的二叉树,每个叶子结点有一个wi作为它的权值。则其中带权路径长度WPL最小的二叉树称做称哈夫曼树。(也叫最优二叉树)

在哈夫曼树中,权值大的,则路径长度短。
Huffman编码：利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。
2.方法：
（1）二叉树的链式存储：
二叉链表：二叉链表中每个结点包含三个域：数据域、左指针域、右指针域
表示：typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild;
// 左右孩子指针
} BiTNode, *BiTree;
（2）二叉树的顺序存储：用一组连续的内存单元，按编号顺序依次存储完全二叉树的元素（1）完全二叉树的顺序结构（2）一般二叉树的顺序结构：补齐二叉树所缺少的那些结点，然后对二叉树结点编号将二叉树原有的结点按编号存储到内存单元“相应”的位置上
（3）如何构造Huffman树
利用Huffman树进行编码：(1)根据给定的n个权值,构造n棵只有一个根结点的二叉
树, n个权值分别是这些二叉树根结点的权。设F是由
这n棵二叉树构成的集合;
(2)在F中选取两棵根结点权值最小的树作为左、右子树，
构造一颗新的二叉树,置新二叉树根的权值=左、右子
树根结点权值之和；
(3)从F中删除这两颗树,并将新树加入F；
(4)重复 (2)、(3),直到F中只含一颗树为止。
利用Huffman树进行编码：将需传送的文字转换成二进制的字符组成的字符串。编码方法:(1)等长编码 2n
(2)不等长编码 (01), (021) ,( 0354)….
3.算法：
二叉树先序、中序、后序递归遍历：
先序：（1）访问根结点A
（2）先序遍历左子树：即按DLR的顺序遍历左子树
（3）先序遍历右子树：即按DLR的顺序遍历右子树
中序：（1）中序遍历左子树：即按LDR的顺序遍历左子树
（2）访问根结点A
（3）中序遍历右子树：即按LDR的顺序遍历右子树
后序：（1）后序遍历左子树：即按LRD的顺序遍历左子树
（2）后序遍历右子树：即按LRD的顺序遍历右子树
（3）访问根结点A
（2）使用栈（前、中、后序）遍历二叉树
使用栈实现非递归中序遍历
Status InOrderTraverse(BiTree bt, Status(* Visit)(TelemType e)) {
//采用二叉链表存储结构，Visit 是对数据元素操作的应用函数。
//中序遍历二叉树bt的非递归算法，对每个数据元素调用函数Visit。
InitStack(S); p=bt;
While (p || ! StackEmpty(s)) {
if (p) {Push(s, p); p=p->lchild; }//根指针进栈，遍历左子树
else { //根指针退栈，访问根结点，遍历右子树
Pop (S, p); Visit(p->data);
p=p->rchild;
}//else
}//While
return OK;
}//InOrderTraverse
（3）使用队列层序遍历二叉树：
Status LevelTraverse(BiTree bt) {
//采用二叉链表存储结构，使用辅助队列Q, 按层遍历二叉树bt,出队时访问结点。
if(!bt) return ERROR;
InitQueue(Q); //建空的辅助队列Q
p=bt;
EnQueue(&Q,e) //e入队
While(!QueueEmpty(Q)){
DeQueue(&Q,&e); //队头元素出队,并赋值给e
Visit(p->data);
if(p->lchild!=NULL)
{p=p->lchild;EnQueueQ,e);}//处理左孩子
if(p->rchild !=NULL)
{p=p->rchild;EnQueue(&Q,e);}//处理右孩子
} //while
return OK;
} // LevelTraverse
二、树
1.概念
（1）树：树是n个结点的有限集合，在任一棵非空树中：
(1)有且仅有一个称为根的结点。
(2)其余结点可分为m个互不相交的集合，而且这些集合中的
每一个集合本身都又是一棵树，称为根的子树。
树是递归结构，在树的定义中又用到了树的概念
森林：是m（m≥0）棵互不相交的树的集合。
（2）树的先根遍历：若森林不空，则访问森林中第一棵树的根结点；
先序遍历森林中第一棵树的子树森林；
先序遍历森林中(除第一棵树之外)其余树构成的森林。
即：依次从左至右对森林中的每一棵树进行先序遍历。
后根遍历：若森林不空，则后序遍历森林中第一棵树的子树森林；
访问森林中第一棵树的根结点；
后序遍历森林中(除第一棵树之外)其余树构成的森林。
即：依次从左至右对森林中的每一棵树进行后序遍历。
层序遍历：
2.方法：
树、森林与二叉树相互转换：将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依次进行转换。
（2）树的链式存储
双亲表示法：通过保存每个结点的双亲结点的位置,表示树中结点之间
的结构关系。
孩子表示法：通过保存每个结点的孩子结点的位置,表示树中结点之间的结构关系。
方法1:多重链表(类似二叉链表)
两种方式：
1)定长结点
优点:结点结构一致，便于实现树的操作
缺点:要浪费一些内存
2)不定长结点
优点:节省内存
缺点:不定长会使一些操作的实现复杂一些
孩子兄弟表示法：孩子兄弟表示法用二叉链表作为树的存贮结构
第七章
一、 概念
图的深度优先遍历
DFSTraverse(G, v, Visit());
//从顶点v起深度优先遍历图G，并对每
//个顶点调用函数Visit一次且仅一次
图的广度优先遍历
BFSTraverse(G, v, Visit());
//从顶点v起广度优先遍历图G，并对每
//个顶点调用函数Visit一次且仅一次。
连通图
在无(有)向图G=中,若对任何两个顶点v、u
都存在从v到u的路径,则称G是连通图(强连通图)
最小生成树
权(之和)最小的生成树。
最短路径
两结点间权值之和最小的路径
有向无环图
（DAG图）没有回路的有向图
拓扑排序
就是将有向图中顶点排成拓扑序列。
关键路径
由于有些活动可以并行进行, 所以完成工程的最短时间是从开始点
到完成点的最长路径长度, 路径长度最长的路径叫做关键路径。

由关键活动组成的路径就是关键路径
二、 算法
深度优先遍历
void DFS(Graph G, int v ) {
// 从第v个顶点出发，递归地深度优先遍历图G。
// v是顶点在一维数组中的位置，假设G是非空图
visited[v] =TRUE; Visit(v); //访问第v个顶点
for (w= FirstAdjVex(G, v); w>=0; w=NextAdjVex(G, v, w))
if (!visited[w]) DFS(G, w); //对v的尚未访问的邻接顶点w递归调用DFS
} //DFS
广度优先遍历
void BFSTraverse(Graph G,Status(* Visit)(int v)){
//从v出发,广度优先遍历连通图G。 v是顶点在一维数组中的
// 位置,使用辅助队列Q和访问标志数组visited。
for(u=0; u< G.vexnum; ++u) visited[u]=FALSE; //初始化访问标志
InitQueue(Q); //建空的辅助队列Q
Visited[v]=TRUE; Visit(v) EnQueue(Q,v) //访问v,v入队
While(!QueueEmpty(Q)){
DeQueue(Q,u); //队头元素出队,并赋值给u
//下面for循环访问u所有未被访问的邻接点
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!visited[w]){ // 若w尚未访问
Visited[w]=TRUE; Visit(w); EnQueue(Q,w);
} //if
} //while
} //BFSTraverse
应用：遍历过程中寻找某个结点或对某（些或所有）结点进行某种操作
三、 方法
图的存储方法
（1） 邻接矩阵
（2） 邻接表
有向图的邻接表和逆邻接表
(1)有向图的邻接表
顶点:用一维数组存储(按编号顺序)
以同一顶点为起点的弧:用线性链表存储。
2、图的生成树与最小生成树
（1）从某一点出发按深度优先或广度优先遍历的生成树
深度优先搜索DFS
深度优先遍历(设图为非空连通图)，从图中某顶点v出发：
（1）访问顶点v；
（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；
广度优先搜索BFS
从图中某顶点v出发：
(1)访问顶点v;
(2)访问v的所有未被访问的邻接点w1 ,w2 , …wk;
(3)依次从这些邻接点(在步骤(2)访问的顶点)出发,访问它们的
所有未被访问的邻接点; 依此类推,直到图中所有访问过的
顶点的邻接点都被访问。
（2）最小生成树
Prim算法：
基本思想：
取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加
新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间
必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间
的边中取值最小。之后继续往生成树上添加顶点，直至生成树
上含有 n-1 个顶点为止。
Kruskal算法：
基本思想：
考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。
具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。
3、最短路径
Dijkstra算法
基本思想:
依最短路径的长度递增的次序求得各条路径。（其中，从源点到顶点v 的最短路径是所有最短路径中长度最短者。）
Dijkstra 算法的基本步骤：
设v0是起始源点，S=已求得最短路