数据结构 图的邻接表存储结构及DFS遍历

//邻接表

#include

#include

#include

#include

#define INF 999

using namespace std;

typedef struct ANode

{

int adjvex;

struct ANode *nextarc;

int weight;

}ArcNode;

typedef struct VNode

{

ArcNode *firstarc;

}VNode;

typedef struct

{

VNode adjlist[100];

int n,e;

}AdjGraph;

int vis[99]={0};

void CreatAdj(AdjGraph *&G,int A[6][10],int n,int e)

{

int i,j,k;

ArcNode *p;

G=(AdjGraph *)malloc(sizeof(AdjGraph));

for(i=0;i

{

G->adjlist[i].firstarc=NULL;

}

for(i=0;i

{

for(j=n-1;j>=0;j--)

{

if(A[i][j]!=0&&A[i][j]!=INF)

{

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

p->adjvex=j;

p->weight=A[i][j];

p->nextarc=G->adjlist[i].firstarc;

G->adjlist[i].firstarc=p;

}

}

}

G->n=n;

G->e=e;

}

void DispAdj(AdjGraph *G)

{

ArcNode *p;

for(int i=0;in;i++)

{

p=G->adjlist[i].firstarc;

printf("%2d:",i);

while(p!=NULL)

{

printf("%2d[%d]->",p->adjvex,p->weight);

p=p->nextarc;

}

printf("^n");

}

}

void Destory(AdjGraph *&G)

{

int i;

ArcNode *pre,*p;

for(i=0;in;i++)

{

pre=G->adjlist[i].firstarc;

if(pre!=NULL)

{

p=pre->nextarc;

while(p!=NULL)

{

free(pre);

pre=p;

p=p->nextarc;

}

free(pre);

}

}

free(G);

}

void dfs(AdjGraph *G,int v)

{

cout<<" "<

vis[v] = 1;

ArcNode *p;

p = G->adjlist[v].firstarc;

while(p!=NULL)

{

if(vis[p->adjvex]==0)

{

dfs(G,p->adjvex);

}

p = p->nextarc;

}

}

int main()

{

memset(vis,sizeof(vis));

AdjGraph *G;

int A[6][10]={

{0,5,INF,7,INF},{INF,4,

{8,9},6},

{INF,{3,1,0}};

CreatAdj(G,A,6,10);

for(int i=0;i<6;i++){

for(int j=0;j<10;j++){

cout<

}

cout<

}

DispAdj(G);

cout<

dfs(G,0);

//Destory(G);

return 0;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!