以鄰接表為存儲結構編寫一個演算法

㈠ 採用鄰接表存儲的圖的深度優先遍歷演算法類似於二叉樹的先序遍歷，為什麼是先序呢

這是因為圖的深度優先遍歷演算法先訪問所在結點，再訪問它的鄰接點。與二叉樹的先序遍歷先訪問子樹的根結點，再訪問它的孩子結點（鄰接點）類似。圖的廣度優先遍歷演算法類似於二叉樹的按層次遍歷。

先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。

首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。

例如，下圖所示二叉樹的遍歷結果是：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表示為未找到，否則為最短路徑值。