以邻接表为存储结构编写一个算法

㈠ 采用邻接表存储的图的深度优先遍历算法类似于二叉树的先序遍历，为什么是先序呢

这是因为图的深度优先遍历算法先访问所在结点，再访问它的邻接点。与二叉树的先序遍历先访问子树的根结点，再访问它的孩子结点（邻接点）类似。图的广度优先遍历算法类似于二叉树的按层次遍历。

先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。

首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

例如，下图所示二叉树的遍历结果是：ABDECF。

(1)以邻接表为存储结构编写一个算法扩展阅读：

遍历种类：

一、NLR：前序遍历(Preorder Traversal 亦称（先序遍历）），访问根结点的操作发生在遍历其左右子树之前。

二、LNR：中序遍历(Inorder Traversal)，访问根结点的操作发生在遍历其左右子树之中（间）。

三、LRN：后序遍历(Postorder Traversal)，访问根结点的操作发生在遍历其左右子树之后。

注意：

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为 先根遍历、中根遍历和后根遍历。

㈡ 以邻接表作存储结构实现求源点到其余各顶点的最短路径的Dijkstra算法

具体算法为：

//Dijkstra求单源最短路径

#include<stdio.h>

#define N 20 //图的顶点最多数

#define MAX 1000

#define MIN -1

typedef int ElemType;//图的顶点标识，这里为自然数

//图的结点结构

typedef struct ArcNode{

ElemType adjvex;//图的顶点 （该弧指向顶点的位置）

struct ArcNode *nextarc;//指向下一条弧的指针

int info//该弧权值

}ArcNode;

//表头结点表

typedef struct VertexNode{

ElemType data;

ArcNode *firstarc;

}VertexNode;

//图

typedef struct AdjList{

VertexNode vertex[N];

int vexnum;//图的顶点数

int arcnum;//弧数;

int kind;//图的种类（kind=1为有向图）

int dist[N];//图的路径长度

int path[N];//辅助数组

}AdjList;

//边

typedef struct{

int i;

int j;

int f;

}Side;

//邻接表法创建图

int CreateDAG(AdjList *L){

int i,j;

ArcNode *p=NULL;

//测试用例

Side S[N];

S[0].i=1;S[0].j=3;S[0].f=10;

S[1].i=1;S[1].j=5;S[1].f=30;

S[2].i=1;S[2].j=6;S[2].f=100;

S[3].i=2;S[3].j=3;S[3].f=5;

S[4].i=3;S[4].j=4;S[4].f=50;

S[5].i=4;S[5].j=6;S[5].f=10;

S[6].i=5;S[6].j=6;S[6].f=60;

S[7].i=5;S[7].j=4;S[7].f=20;

for(i=1;i<7;i++){

L->vertex[i].data=i;

L->dist[i]=MAX;//设为最大值，表示不可达

L->path[i]=MIN;//设为最小值，表示尚未初始化

//L->vertex[i].indegree=0;

L->vertex[i].firstarc=NULL;

}

L->kind=1;

L->vexnum=6;

L->arcnum=8;

for(i=0;i<8;i++){

p=(ArcNode *)malloc(sizeof(ArcNode));

p->adjvex=S[i].j;

p->info=S[i].f;

p->nextarc=L->vertex[(S[i].i)].firstarc;

L->vertex[(S[i].i)].firstarc=p;

if(S[i].i==1){//初始顶点为1

L->dist[(S[i].j)]=S[i].f;

//L->path[(S[i].j)]=S[i].f;

}

// L->vertex[(S[i].j)].indegree++;

}

return 1;

}

//输出邻接表存储

void PrintALGraph(AdjList *L){

ArcNode *p=NULL;

int i,k=0;

for(i=1;i<=L->vexnum;i++){

k=L->vertex[i].data;

printf("V%d",k);

// printf(" 入度为%d 邻接点有 ",(L->vertex[i].indegree));

p=L->vertex[k].firstarc;

while(p!=NULL){

printf(" ->%d",p->adjvex);

p=p->nextarc;

}

printf(" ");

}

}

//Dijkstra求单源最短路径

void Dijkstra(AdjList *L){

int i=1,j,k=0;

Side s;

L->path[1]=0;

ArcNode *p=NULL;

while(k<10){

s.f=MAX;

for(i=1;i<=L->vexnum;i++){

if(L->path[i]!=MIN){

p=L->vertex[i].firstarc;

if(p!=NULL){

while(p!=NULL){

if(s.f>p->info&&L->path[(p->adjvex)]==MIN){

s.f=p->info;

s.i=i;

s.j=p->adjvex;

}

p=p->nextarc;

}

}

}

}

if(s.f==MAX){

}else if(L->dist[(s.j)]>L->dist[(s.i)]+s.f){

L->dist[(s.j)]=L->dist[(s.i)]+s.f;

L->path[(s.j)]=L->dist[(s.j)];

}else{

L->path[(s.j)]=L->dist[(s.j)];

}

k++;

}

//输出

printf("输出最短路径: ");

for(i=1;i<=L->vexnum;i++){

if(L->dist[i]==1000||i==1){

printf("v1到v%d不存在最短路径 ",i);

}else{

printf("v1到v%d的最短路径是%d ",i,L->dist[i]);

}

printf("path is %d ",L->path[i]);

}

}

int main(){

AdjList *L=(AdjList *)malloc(sizeof(AdjList));

if(CreateDAG(L)==1){

PrintALGraph(L);

Dijkstra(L);

}else{

printf("创建失败 ");

}

}

(2)以邻接表为存储结构编写一个算法扩展阅读：

要求带权有向图中某一顶点到其他各顶点的最短路径，常用Dijkstra算法，该算法基本思想是，先将图的顶点分为两个集合，一个为已求出最短路径的终点集合（开始为原点v1），另一个为还未求出最短路径的顶点集合（开始为除v1外的全部结点），然后按最短路径长度的递增顺序逐个将第二个集合的顶点加到第一组中。

算法中使用dist数组，dist[i]表示目前已经找到、v1到vi的当前最短路径，否则为MAX；path数组，作为是否找到该点最短路径的标志，path[i]==MIN表示为未找到，否则为最短路径值。