数据结构课程设计(7)

void DFSTraverse(MGraph G,int *visited);//图深度遍历 void graphmenu(); #endif

图的建立与遍历的源文件 #include #include #include\

void InitQueue(SqQueue &Q) {

Q.base=(int*)malloc(maxqsize*sizeof(int)); Q.front=Q.rear=0; }

void EnQueue(SqQueue &Q,int e) {

if((Q.rear-Q.front+1)%maxqsize==0) {

printf(\队列已满。\ return; }

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%maxqsize; }

void DeQueue(SqQueue &Q,int &e) {

if(Q.front==Q.rear) {

printf(\队列以空\ return; }

e=Q.base[Q.front];

Q.front=(Q.front+1)%maxqsize; }

int EmptyQueue(SqQueue Q) {

if(Q.front==Q.rear) return 1; return 0; }

void CreateGraph(MGraph &G,int kind) {

int i; int j; int k; int v1,v2;

29

int point1=-1,point2=-1;

printf(\输入图的顶点数:\\n\ scanf(\ printf(\输入图的弧数:\\n\ scanf(\

printf(\输入图的顶点信息:\\n\ for(i=0;i

scanf(\ }

for(i=0;i

if(i==j)G.arcs[i][j]=0; else G.arcs[i][j]=-1; } if(kind==1) {

for(i=0;i

printf(\输入第%d条弧的弧尾和弧头:\ scanf(\ k=0;

while(k

if(v1==G.vexs[k]) {

point1=k; break; } k++; } k=0;

while(k

if(v2==G.vexs[k]) {

point2=k; break; } k++; }

if(G.arcs[point1][point2]==-1) G.arcs[point1][point2]+=2;

30

else

G.arcs[point1][point2]++; } }

else if(kind==2) {

for(i=0;i

printf(\输入弧的两端顶点信息:\ scanf(\ k=0;

while(k

if(v1==G.vexs[k]) {

point1=k; break; } k++; } k=0;

while(k

if(v2==G.vexs[k]) {

point2=k; break; } k++; }

if(G.arcs[point1][point2]==-1) G.arcs[point1][point2]+=2; else

G.arcs[point2][point1]++; if(G.arcs[point2][point1]==-1) G.arcs[point2][point1]+=2; else

G.arcs[point2][point1]++; } } else {

printf(\输入的图的类型不正确\\n\ return;

31

} }

void PrintGraph(MGraph G) {

int i; int j; int k=0;

for(i=0;i

printf(\ k++;

if(k%G.vexnum==0)putchar('\\n'); } }

void DFS(MGraph G,int *visited,int i) {

int j;

printf(\ visited[i]=1;

for(j=0;j

if(G.arcs[i][j]>0 && visited[j]==0) DFS(G,visited,j); }

void DFSTraverse(MGraph G,int *visited) {

int i;

for(i=0;i

void BFS(MGraph G,int *visited,int i) {

int j,k; SqQueue Q; int e;

int flag=0; InitQueue(Q);

printf(\ visited[i]=1;

for(j=0;j

if(G.arcs[i][j]>0 && visited[j]==0) EnQueue(Q,j);

32

while(!EmptyQueue(Q)) {

DeQueue(Q,e);

printf(\ visited[e]=1;

for(j=0;j

if(G.arcs[e][j]>0 && visited[j]==0) {

k=Q.front;

while(k!=Q.rear) {

if(j==Q.base[k]) {

flag=1; break; }

k=(k+1)%maxqsize; }

if(flag==0) {

EnQueue(Q,j); }

flag=0; } } }

void BFSTraverse(MGraph G,int *visited) {

int i;

for(i=0;i

图的建立与遍历的菜单文件 #include #include #include \void graphmenu() {

MGraph G; int kind,i;

int visited[MAX_VERTEX_NUM];

printf(\ printf(\有向图或无向图：\\n\

33