对于图的遍历的四种问题

王朝other·作者佚名 2006-01-09

宽屏版字体: 小|中|大|超大

图建立，输入示例：

input the number for vexnum and arcnum:8 9

input8char for vexs(use -enter- to change):a

input9arc(char -enter- char -enter- weigh):

0:a

1:a

2:b

3:b

4:d

5:e

6:c

7:c

8:f

遍历建立的矩阵：

88 11 11 88 88 88 88 88

11 88 88 11 11 88 88 88

11 88 88 88 88 11 11 88

88 11 88 88 88 88 88 23

88 11 88 88 88 88 88 11

88 88 11 88 88 88 11 88

88 88 11 88 88 11 88 88

88 88 88 23 11 88 88 88

遍历的结果：

(邻接矩阵图深度遍历结果)

实际图形示例：

b c

d e f ------g

(其他是上下连起)

代码：

邻接表图的广度遍历

#include <stdio.h>

#include <stdlib.h>

#include <iostream.h>

#define INFINITY INT_MAX

#define MAX_VERTEX_NUM 20

#define MAXQSIZE 10 //最大队列长度

#define FALSE 0

#define TRUE 1

typedef int VRType;

typedef char VertexType;

typedef int Status;

typedef int QElemType;

typedef struct

{

QElemType *base;

int front;

int rear;

} SqQueue;

typedef struct ArcNode

{

int adjvex;

struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode

{

VertexType data;

ArcNode *firstarc;

}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct

{

AdjList vertices;

int vexnum, arcnum;

}ALGraph;

bool visited[MAX_VERTEX_NUM];

Status (*VisitFunc)(int v);

int w;

void CreateGraph(ALGraph &G);

void BFSTraverse(ALGraph G, Status (*Visit)(int v));

Status printGraph(int v);

int FirstAdjVex(ALGraph G, int v);

int NextAdjVex(ALGraph G, int v, int w);

Status InitQueue(SqQueue &);

Status EnQueue(SqQueue &, QElemType);

Status DeQueue(SqQueue &, QElemType &);

Status QueueEmpty(SqQueue);

void main( void )

{

int i;

ALGraph G;

ArcNode *p;

CreateGraph(G);

for(i= 0; i < G.vexnum; i++)

{

cout<<i<<" "<<G.vertices[i].data;

p = G.vertices[i].firstarc;

while(p != NULL)

{

cout<<"--->";

cout<<(G.vertices[p->adjvex].data);

p = p->nextarc;

}

cout<<endl;

}

BFSTraverse(G, printGraph);

}

void CreateGraph(ALGraph &G)

{

int i, j = 0, k = 0;

char hand, tide;

ArcNode *p;

cout<<"input the number for vexnum and arcnum:";

cin>>G.vexnum>>G.arcnum;

cout<<endl;

cout<<"input"<<G.vexnum<<"char for vexs:";

for(i=0; i < G.vexnum; i++)

cin>>G.vertices[i].data;

cout<<endl;

for(i=0;i<G.vexnum;++i)

G.vertices[i].firstarc=NULL;

cout<<"input"<<G.arcnum<<"arc(char-enter-char):"<<endl;

j = 0;

k = 0;

for(i=0; i < G.arcnum; i++)

{

cout<<i<<":";

cin>>hand;

cin>>tide;

while (hand != G.vertices[j].data)

j++;

while (tide != G.vertices[k].data)

k++;

p=new ArcNode;

p->adjvex=j;

p->nextarc=G.vertices[j].firstarc;

G.vertices[k].firstarc=p;

p=new ArcNode;

p->adjvex=k;

p->nextarc=G.vertices[j].firstarc;

G.vertices[j].firstarc=p;

j = 0;

k = 0;

cout<<endl;

}

void BFSTraverse(ALGraph G, Status (*Visit)(int v))

{

SqQueue Q;

QElemType u;

InitQueue(Q);

for(int v=0; v < G.vexnum;++v)

visited[v]=FALSE;

for(v=0; v<G.vexnum;++v)

if(!visited[v])

{

visited[v]=TRUE;

EnQueue(Q, v);

Visit(v);

while(QueueEmpty(Q))

{

DeQueue(Q, u);

for(w = FirstAdjVex(G, u); w; w = NextAdjVex(G, u, w))

if(! visited[w])

{

visited[w]=TRUE;

Visit(w);

EnQueue(Q, w);

}

int FirstAdjVex(ALGraph G, int v)

{

ArcNode *p;

p = G.vertices[v].firstarc;

while(p != NULL)

{

if(visited[p->adjvex] != 1)

return p->adjvex;

p = p->nextarc;

}

return 0;

}

int NextAdjVex(ALGraph G, int v, int w)

{

ArcNode *p;

p = G.vertices[v].firstarc;

while(p != NULL)

{

if(visited[p->adjvex] != 1 && p->adjvex != w)

return p->adjvex;

p = p->nextarc;

}

return 0;

}

Status printGraph(int v)

{

printf("%c", v + 'a');

cout<<endl;

return 1;

}

Status InitQueue(SqQueue & queue)

{

queue.base = (QElemType *) malloc(MAXQSIZE * sizeof(QElemType));

if (!queue.base)

return FALSE;

queue.front = queue.rear = 0;

return TRUE;

}

///////////////////////////////////////////////////////////////////////

// 函数名 : EnQueue

// 功能描述 : 插入元素到队列

// 参数 : SqQueue &queue

// 参数 : QElemType element

// 返回值 : Status

///////////////////////////////////////////////////////////////////////

Status EnQueue(SqQueue &queue, QElemType element)

{

//先判断是不是没满的队列

if ((queue.rear + 1) % MAXQSIZE == queue.front)

return FALSE;

queue.base[queue.rear] = element;

queue.rear = (queue.rear + 1) % MAXQSIZE;

return TRUE;

}

///////////////////////////////////////////////////////////////////////

// 函数名 : DeQueue

// 功能描述 : 删除队列的头结点

// 参数 : SqQueue &queue

// 参数 : QElemType &element

// 返回值 : Status

///////////////////////////////////////////////////////////////////////

Status DeQueue(SqQueue &queue, QElemType &element)

{

//判断队列是不是空的

if (queue.front == queue.rear)

return FALSE;

element = queue.base[queue.front];

queue.front = (queue.front + 1) % MAXQSIZE;

return TRUE;

}

Status QueueEmpty(SqQueue queue)

{

if (queue.front == queue.rear)

return FALSE;

else

return TRUE;

}

邻接表图的深度遍历

#include <stdio.h>

#include <stdlib.h>

#include <iostream.h>

#define INFINITY INT_MAX

#define MAX_VERTEX_NUM 20

typedef int VRType;

typedef char VertexType;

typedef int Status;

typedef struct ArcNode

{

int adjvex;

struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode

{

VertexType data;

ArcNode *firstarc;

}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct

{

AdjList vertices;

int vexnum, arcnum;

}ALGraph;

bool visited[MAX_VERTEX_NUM];

Status (*VisitFunc)(int v);

int w;

void CreateGraph(ALGraph &G);

void DFSTraverse(ALGraph G, Status (*Visit)(int v));

Status printGraph(int v);

int FirstAdjVex(ALGraph G, int v);

int NextAdjVex(ALGraph G, int v, int w);

void DFS(ALGraph G, int v);

void main( void )

{

int i;

ALGraph G;

ArcNode *p;

CreateGraph(G);

for(i= 0; i < G.vexnum; i++)

{

cout<<i<<" "<<G.vertices[i].data;

p = G.vertices[i].firstarc;

while(p != NULL)

{

cout<<"--->";

cout<<(G.vertices[p->adjvex].data);

p = p->nextarc;

}

cout<<endl;

}

DFSTraverse(G, printGraph);

}

void CreateGraph(ALGraph &G)

{

int i, j = 0, k = 0;

char hand, tide;

ArcNode *p;

cout<<"input the number for vexnum and arcnum:";

cin>>G.vexnum>>G.arcnum;

cout<<endl;

cout<<"input"<<G.vexnum<<"char for vexs:";

for(i=0; i < G.vexnum; i++)

cin>>G.vertices[i].data;

cout<<endl;

for(i=0;i<G.vexnum;++i)

G.vertices[i].firstarc=NULL;

cout<<"input"<<G.arcnum<<"arc(char-enter-char):"<<endl;

j = 0;

k = 0;

for(i=0; i < G.arcnum; i++)

{

cout<<i<<":";

cin>>hand;

cin>>tide;

while (hand != G.vertices[j].data)

j++;

while (tide != G.vertices[k].data)

k++;

p=new ArcNode;

p->adjvex=j;

p->nextarc=G.vertices[j].firstarc;

G.vertices[k].firstarc=p;

p=new ArcNode;

p->adjvex=k;

p->nextarc=G.vertices[j].firstarc;

G.vertices[j].firstarc=p;

j = 0;

k = 0;

cout<<endl;

}

void DFSTraverse(ALGraph G, Status (*Visit)(int v))

{

int j;

VisitFunc = Visit;

for( j=0; j<G.vexnum; j++)

visited[j] = 0;

for(j=0; j<G.vexnum; j++)

if(!visited[j])

DFS(G, j);

}

void DFS(ALGraph G, int v)

{

visited[v]=1;

VisitFunc(v);

for(w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w))

if(!visited[w])

DFS(G, w);

}

int FirstAdjVex(ALGraph G, int v)

{

ArcNode *p;

p = G.vertices[v].firstarc;

while(p != NULL)

{

if(visited[p->adjvex] != 1)

return p->adjvex;

p = p->nextarc;

}

return 0;

}

int NextAdjVex(ALGraph G, int v, int w)

{

ArcNode *p;

p = G.vertices[v].firstarc;

while(p != NULL)

{

if(visited[p->adjvex] != 1 && p->adjvex != w)

return p->adjvex;

p = p->nextarc;

}

return 0;

}

Status printGraph(int v)

{

printf("%c", v + 'a');

cout<<endl;

return 1;

}

邻接矩阵的广度遍历

#include <stdio.h>

#include <stdlib.h>

#include <iostream.h>

#define INFINITY INT_MAX

#define MAX_VERTEX_NUM 20

#define MAXQSIZE 10 //最大队列长度

#define FALSE 0

#define TRUE 1

typedef int VRType;

typedef int InfoType;

typedef char VertexType;

typedef int Status;

typedef int QElemType;

typedef struct

{

QElemType *base;

int front;

int rear;

} SqQueue;

typedef struct ArcCell

{

VRType adj;

InfoType *info;

}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{

VertexType vexs[MAX_VERTEX_NUM];

AdjMatrix arcs;

int vexnum, arcnum;

}MGraph;

bool visited[MAX_VERTEX_NUM];

Status (*VisitFunc)(int v);

int w;

void CreateGraph(MGraph &G);

void BFSTraverse(MGraph G, Status (*Visit)(int v));

Status printGraph(int v);

int FirstAdjVex(MGraph G, int v);

int NextAdjVex(MGraph G, int v, int w);

Status InitQueue(SqQueue &);

Status EnQueue(SqQueue &, QElemType);

Status DeQueue(SqQueue &, QElemType &);

Status QueueEmpty(SqQueue);

void main( void )

{

int i, j;

MGraph G;

CreateGraph(G);

for(i = 0; i < G.vexnum; i++)

{

for(j = 0; j < G.vexnum; j++)

{

cout<<G.arcs[i][j].adj;

cout<<" ";

}

cout<<endl;

}

BFSTraverse(G, printGraph);

}

void CreateGraph(MGraph &G)

{

int weigh;

int i, j = 0, k = 0;

char hand, tide;

cout<<"input the number for vexnum and arcnum:";

cin>>G.vexnum>>G.arcnum;

for(i = 0; i < G.vexnum; i++)

{

for(j = 0; j < G.vexnum; j++)

G.arcs[i][j].adj = 88;

}

cout<<endl;

cout<<"input"<<G.vexnum<<"char for vexs(use -enter- to change):";

for(i=0; i < G.vexnum; i++)

cin>>G.vexs[i];

cout<<endl;

cout<<"input"<<G.arcnum<<"arc(char -enter- char -enter- weigh):"<<endl;

j = 0;

k = 0;

for(i=0; i < G.arcnum; i++)

{

cout<<i<<":";

cin>>hand;

cin>>tide;

cin>>weigh;

while (hand != G.vexs[j])

j++;

while (tide != G.vexs[k])

k++;

G.arcs[j][k].adj = weigh;

G.arcs[k][j].adj = weigh;

j = 0;

k = 0;

cout<<endl;

}

void BFSTraverse(MGraph G, Status (*Visit)(int v))

{

SqQueue Q;

QElemType u;

InitQueue(Q);

for(int v=0; v < G.vexnum;++v)

visited[v]=FALSE;

for(v=0; v<G.vexnum;++v)

if(!visited[v])

{

visited[v]=TRUE;

Visit(v);

EnQueue(Q, v);

while(QueueEmpty(Q))

{

DeQueue(Q, u);

for(w = FirstAdjVex(G, u); w; w = NextAdjVex(G, u, w))

if(! visited[w])

{

visited[w]=TRUE;

Visit(w);

EnQueue(Q, w);

}

int FirstAdjVex(MGraph G, int v)

{

int j;

for(j = 0; j < G.vexnum; j++)

{

if(G.arcs[v][j].adj != 88 && visited[j] != 1)

return j;

}

return 0;

}

int NextAdjVex(MGraph G, int v, int w)

{

int j;

for(j = 0; j < G.vexnum; j++)

{

if(G.arcs[v][j].adj != 88 && j != w && visited[j] != 1)

return j;

}

return 0;

}

Status printGraph(int v)

{

printf("%c", v + 'a');

cout<<endl;

return 1;

}

Status InitQueue(SqQueue & queue)

{

queue.base = (QElemType *) malloc(MAXQSIZE * sizeof(QElemType));

if (!queue.base)

return FALSE;

queue.front = queue.rear = 0;

return TRUE;

}

///////////////////////////////////////////////////////////////////////

// 函数名 : EnQueue

// 功能描述 : 插入元素到队列

// 参数 : SqQueue &queue

// 参数 : QElemType element

// 返回值 : Status

///////////////////////////////////////////////////////////////////////

Status EnQueue(SqQueue &queue, QElemType element)

{

//先判断是不是没满的队列

if ((queue.rear + 1) % MAXQSIZE == queue.front)

return FALSE;

queue.base[queue.rear] = element;

queue.rear = (queue.rear + 1) % MAXQSIZE;

return TRUE;

}

///////////////////////////////////////////////////////////////////////

// 函数名 : DeQueue

// 功能描述 : 删除队列的头结点

// 参数 : SqQueue &queue

// 参数 : QElemType &element

// 返回值 : Status

///////////////////////////////////////////////////////////////////////

Status DeQueue(SqQueue &queue, QElemType &element)

{

//判断队列是不是空的

if (queue.front == queue.rear)

return FALSE;

element = queue.base[queue.front];

queue.front = (queue.front + 1) % MAXQSIZE;

return TRUE;

}

Status QueueEmpty(SqQueue queue)

{

if (queue.front == queue.rear)

return FALSE;

else

return TRUE;

}

邻接矩阵的深度遍历

#include <stdio.h>

#include <stdlib.h>

#include <iostream.h>

#define INFINITY INT_MAX

#define MAX_VERTEX_NUM 20

typedef int VRType;

typedef int InfoType;

typedef char VertexType;

typedef int Status;

typedef struct ArcCell

{

VRType adj;

InfoType *info;

}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{

VertexType vexs[MAX_VERTEX_NUM];

AdjMatrix arcs;

int vexnum, arcnum;

}MGraph;

bool visited[MAX_VERTEX_NUM];

Status (*VisitFunc)(int v);

int w;

void CreateGraph(MGraph &G);

void DFSTraverse(MGraph G, Status (*Visit)(int v));

Status printGraph(int v);

int FirstAdjVex(MGraph G, int v);

int NextAdjVex(MGraph G, int v, int w);

void DFS(MGraph G, int v);

void main( void )

{

int i, j;

MGraph G;

CreateGraph(G);

for(i = 0; i < G.vexnum; i++)

{

for(j = 0; j < G.vexnum; j++)

{

cout<<G.arcs[i][j].adj;

cout<<" ";

}

cout<<endl;

}

DFSTraverse(G, printGraph);

}

void CreateGraph(MGraph &G)

{

int weigh;

int i, j = 0, k = 0;

char hand, tide;

cout<<"input the number for vexnum and arcnum:";

cin>>G.vexnum>>G.arcnum;

for(i = 0; i < G.vexnum; i++)

{

for(j = 0; j < G.vexnum; j++)

G.arcs[i][j].adj = 88;

}

cout<<endl;

cout<<"input"<<G.vexnum<<"char for vexs(use -enter- to change):";

for(i=0; i < G.vexnum; i++)

cin>>G.vexs[i];

cout<<endl;

cout<<"input"<<G.arcnum<<"arc(char -enter- char -enter- weigh):"<<endl;

j = 0;

k = 0;

for(i=0; i < G.arcnum; i++)

{

cout<<i<<":";

cin>>hand;

cin>>tide;

cin>>weigh;

while (hand != G.vexs[j])

j++;

while (tide != G.vexs[k])

k++;

G.arcs[j][k].adj = weigh;

G.arcs[k][j].adj = weigh;

j = 0;

k = 0;

cout<<endl;

}

void DFSTraverse(MGraph G, Status (*Visit)(int v))

{

int j;

VisitFunc = Visit;

for( j=0; j<G.vexnum; j++)

visited[j] = 0;

for(j=0; j<G.vexnum; j++)

if(!visited[j])

DFS(G, j);

}

void DFS(MGraph G, int v)

{

visited[v]=1;

VisitFunc(v);

for(w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w))

if(!visited[w])

DFS(G, w);

}

int FirstAdjVex(MGraph G, int v)

{

int j;

for(j = 0; j < G.vexnum; j++)

{

if(G.arcs[v][j].adj != 88 && visited[j] != 1)

return j;

}

return 0;

}

int NextAdjVex(MGraph G, int v, int w)

{

int j;

for(j = 0; j < G.vexnum; j++)

{

if(G.arcs[v][j].adj != 88 && j != w && visited[j] != 1)

return j;

}

return 0;

}

Status printGraph(int v)

{

printf("%c", v + 'a');

cout<<endl;

return 1;

}