邻接表-图的遍历-广度和深度优先遍历

数据结构目前学习的基本大概已经完成了，图的讲解也基本结束，本次试验就是图的遍历。

将常用的头文件放在t11.h中

#include"stdio.h"
#include"string.h"
#include"ctype.h"
#include"malloc.h"
#include"stdlib.h" //atoi(),exit();
#include"io.h" //eof()
#include"math.h"

#define TRUE 1
#define FALSE 0
#define OK   1
#define ERROR 0
typedef int Status;
typedef int Boolean;

之后就是数据结构定义了，放在头文件tu.h中
typedef struct tunode     // 定义邻接表中存放下标的结构体
{
     int adjvex;           // 存放当前图标识的位置
     struct tunode *nextarc;        // 链表的next指针
}tunode;
typedef struct vnode        // 定义的存放图标识和邻接表的指针
{
char data;
tunode *firstarc;
}vnode;
typedef struct algraph     // 管理邻接表的信息结构体
{
vnode *vertices;
int vexnum,arcnum;
}algraph;

int *p;        //   全局变量，在深度优先

接下来就是实现功能函数的模块代码了，定义在文件tu.cpp中

void initgraph(algraph &T)          // 图的初始化函数
{
printf("输入图结点的个数和弧的个数:");
scanf("%d%d",&T.vexnum,&T.arcnum);
getchar();
T.vertices=(vnode*)malloc(T.vexnum*sizeof(vnode));     // 开辟vnode类型的空间，将首地址给T.vertices
printf("输入这%d个结点的标识:",T.vexnum);
for(int i=0;i<T.vexnum;i++)         //   输入图结点标识
{
scanf("%c",&(T.vertices+i)->data);
while(' ' == (T.vertices+i)->data)       // 屏蔽空格键
{
   scanf("%c",&(T.vertices+i)->data);
}

(T.vertices+i)->firstarc=NULL;        // 将指针置为空
}
}
void BFS(algraph T,int *q)        // 广度优先遍历
{

for(int i=0;i<T.vexnum;i++)        // 将全局变量初始化为0，这是一个辅助空间
*(p+i)=0;
*q=0;      // 辅助q,将遍历的结果存入
*p=1;      // 已经访问的将其置为1，表示访问过
int k=1;
tunode *next;
for(i=0;i<T.vexnum;i++)   // 循环次数是q中的最大长度
{
next=(T.vertices+(*(q+i)))->firstarc; // 取得此时q中图结点在邻接表中的链表指针
        while(next != NULL)
{
   if(!*(p+next->adjvex))      // 判断该链表结点中对应的下标在p中是否为0
            {
    *(q+k++)=next->adjvex; // 将该图结点对应的下标存入q中
    *(p+next->adjvex)=1;     // 在p中标识此位置已访问
                next=next->nextarc;     // 更新指针直到为空结束
   }
   else
    next=next->nextarc;      // p中对应的为1，该元素访问过，直接获取下一个指针
}
}
printf("广度优先遍历为:\n");
for(i=0;i<T.vexnum;i++)
{
printf("%-3c",(T.vertices+(*(q+i)))->data); // 按q中的顺序取得遍历的值
}
printf("\n");
}

int localvex(algraph &T,char ch)         // 获取图中对应的图标识对应的下标
{
for(int i=0;i<T.vexnum;i++)
{
if(ch == (T.vertices+i)->data)        // 找到后就退出
{
   break;
}
}
return i;            // 返回找到的下标
}
void guanxi(algraph &T,char ch,char ch1)        // 建立邻接表
{
tunode *p;
int i,j;
i=localvex(T,ch);     //获取图标识所对应的位置
j=localvex(T,ch1);
p=(tunode*)malloc(sizeof(tunode));   // 开辟内存空间
p->nextarc=NULL;                  // 结点置为空 www.zzzyk.com
p->adjvex=j;                     // 存放返回的位置
p->nextarc=(T.vertices+i)->firstarc;   // 头结点插入开辟的结点
(T.vertices+i)->firstarc=p;
p=(tunode*)malloc(sizeof(tunode));
    p->nextarc=NULL;
    p->adjvex=i;
    p->nextarc=(T.vertices+j)->firstarc;
    (T.vertices+j)->firstarc=p;
}
int nextvex(algraph T,int v)     // 在递归遍历中寻找v图对应的下一个位置
{
tunode *p,*q;
int k;
if((T.vertices+v)->firstarc != NULL)
{
k=(T.vertices+v)->firstarc->adjvex;
p=(T.vertices+v)->firstarc->nextarc;
q=(T.vertices+v)->firstarc;
free(q);
(T.vertices+v)->firstarc=p;
return k;
}
else
return -1;   // 为空返回-1
}
void DFS(algraph T,int v)
{
*(p+v)=1;
printf("%-3c",(T.vertices+v)->data);
    for(int w=nextvex(T,v);w>=0;w=nextvex(T,w))
{
if(!*(p+w))
   DFS(T,w);
}
}
void DFStraverse(algraph T)
{
for(int i=0;i<T.vexnum;i++)
        *(p+i)=0;

for(i=0;i<T.vexnum;i++)
        if(!*(p+i))
      DFS(T,i);
}

最后就是主函数的初始化及相关的调用了定义文件mian_tu.cpp

#include"t11.h"
#include"tu.h"
#include"tu.cpp"
void main()
{
char ch='y',ch1,ch2;
int *leidui;
algraph G;
initgraph(G);
getchar();
p=(int*)malloc(G.vexnum*sizeof(int));   // 开辟全局变量的空间，将首地址返回
leidui=(int*)malloc(G.vexnum*sizeof(int));   // 作为实参传递给q
while('y' == ch || 'Y' == ch)            // 构建两条边的关系
{
&n

补充：软件开发 , 其他 ,