《数据结构》（C语言版）严蔚敏著 - 数据结构实验指导

void tdfs(graph *g); /*深度优先搜索整个图*/ void bfs(int k,graph *g); /*从第k个顶点广度优先搜索*/ void tbfs(graph *g); /*广度优先搜索整个图*/ void init_visit(); /*初始化访问标识数组*/

void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/ { int i,j; char v;

g->vexnum=0; g->arcnum=0; i=0;

printf(\输入顶点序列(以#结束)：\\n\ while((v=getchar())!='#') {

g->vexs[i]=v; /*读入顶点信息*/ i++;

}

g->vexnum=i; /*顶点数目*/

for(i=0;ivexnum;i++) /*邻接矩阵初始化*/ for(j=0;jvexnum;j++) g->arcs[i][j]=0;

printf(\输入边的信息：\\n\

scanf(\读入边i,j*/

while(i!=-1) /*读入i,j为－1时结束*/ {

g->arcs[i][j]=1; g->arcs[j][i]=1; scanf(\ } }

void dfs(int i,graph *g) /*从第i个顶点出发深度优先搜索*/ {

int j;

printf(\ visited[i]=TRUE;

for(j=0;jvexnum;j++)

if((g->arcs[i][j]==1)&&(!visited[j])) dfs(j,g); }

void tdfs(graph *g) /*深度优先搜索整个图*/ {

int i;

29

printf(\从顶点%C开始深度优先搜索序列：\ for(i=0;ivexnum;i++) if(visited[i]!=TRUE) dfs(i,g); }

void bfs(int k,graph *g) /*从第k个顶点广度优先搜索*/ {

int i,j;

queue qlist,*q; q=&qlist; q->rear=0;

q->front=0;

printf(\ visited[k]=TRUE; q->data[q->rear]=k; q->rear=(q->rear+1)%N; while(q->rear!=q->front) {

i=q->data[q->front];

q->front=(q->front+1)%N;

for(j=0;jvexnum;j++)

if((g->arcs[i][j]==1)&&(!visited[j])) {

printf(\ visited[j]=TRUE; q->data[q->rear]=j; q->rear=(q->rear+1)%N; } } }

void tbfs(graph *g) /*广度优先搜索整个图*/ {

int i;

printf(\从顶点%C开始广度优先搜索序列：\ for(i=0;ivexnum;i++) if(visited[i]!=TRUE) bfs(i,g); }

void init_visit() /*初始化访问标识数组*/ {

int i;

30

for(i=0;i

int main() {

graph ga;

int i,j;

createGraph(&ga);

printf(\无向图的邻接矩阵：\\n\

for(i=0;i

for(j=0;j

printf(\ printf(\ }

init_visit(); tdfs(&ga); init_visit(); tbfs(&ga); return 0;

}

? 根据右图的结构验证实验，输入： ABCDEFGH# 0,1 0,2 0,5 1,3 1,4 2,5 2,6 3,7 4,7 -1,-1 ?

2、阅读并运行下面程序，补充拓扑排序算法。 #include #include #define N 20

运行结果：

1 0 B 4 E 7 H A C 2 F 5 G 6

3 D 31

typedef struct edgenode{ /*图的邻接表：邻接链表结点*/ int adjvex; /*顶点序号*/

struct edgenode *next; /*下一个结点的指针*/ }edgenode;

typedef struct vnode{ /*图的邻接表：邻接表*/ char data; /*顶点信息*/

int ind; /*顶点入度*/

struct edgenode *link; /*指向邻接链表指针*/ }vnode;

void createGraph_list(vnode adjlist[],int *p)； /*建立有向图的邻接表*/ void topSort(vnode g[],int n)； /*拓扑排序*/

void createGraph_list(vnode adjlist[],int *p){ /*建立有向图的邻接表*/ int i,j,n,e; char v;

edgenode *s; i=0;n=0;e=0;

printf(\输入顶点序列(以#结束)：\\n\ while((v=getchar())!='#')

{

adjlist[i].data=v; /*读入顶点信息*/ adjlist[i].link=NULL; adjlist[i].ind=0; i++; }

n=i; *p=n;

/*建立邻接链表*/

printf(\请输入弧的信息(i=-1结束)：i,j:\\n\ scanf(\

while(i!=-1){

s=(struct edgenode*)malloc(sizeof(edgenode)); s->adjvex=j;

s->next=adjlist[i].link; adjlist[i].link=s;

adjlist[j].ind++; /*顶点j的入度加1*/ e++;

scanf(\ }

printf(\邻接表:\

for(i=0;i

printf(\

32