基于邻结矩阵的图的BFS和DFS遍历

// Graph.cpp : Defines the entry point for the console application.

//邻接矩阵

#include "stdafx.h"

// test.cpp : Defines the entry point for the console application.

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <memory.h>

#include <iostream>

#include <queue>

using namespace std;

//图的数组（邻接矩阵）存储

#define MAX_VERTEX_NUM 20 //最大顶点个数

//顶点关系，对无权图，用1(是)或0(否)表示相邻否 

bool visited[20];

typedef struct

{

char* vexs[MAX_VERTEX_NUM];//顶点向量,指针数组，用于存储顶点

int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];////邻接矩阵 .顶点关系，对无权图，用1(是)或0(否)表示相邻否

int vexnum,arcnum;

}MGraph;

int LocateVex(MGraph G, char* u)

{//操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1

  int  i ;

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

 if(strcmp(G.vexs[i],u) == 0) //strcmp的参数必须是const char*

         return i;

  return -1;

}

void CreateFAG(MGraph *G)

{//采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G

int i, j ,k ;

int N = 3; //N表示顶点字符数 在开辟空间时用到

char filename[30];

char va[5];

char vb[5];

FILE* pFile;

    printf("请输入数据文件名:");

scanf("%s",filename); //请输入数据文件名 //D:\\Graph\\1.txt or D:/Graph/1.txt

    pFile = fopen(filename, "r");

//pFile = fopen("1.txt","r");

if(pFile == NULL)

{

printf("fail to read");

getchar();

getchar();

exit(1);

}

fscanf(pFile, "%d", &(*G).vexnum);

fscanf(pFile, "%d", &(*G).arcnum);

for(i = 0; i < G->vexnum; i++){

G->vexs[i] = (char*)malloc(N*sizeof(char));//分配顶点数目

}

for(i = 0; i < G->vexnum; i++){

fscanf(pFile, "%s", G->vexs[i]);

}//存储节点

for(i = 0 ; i < (*G).vexnum; ++i) //初始化邻接矩阵

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

{

(*G).arcs[i][j] = 0;

}

for(k = 0; k < (*G).arcnum; ++k)

{

fscanf(pFile, "%s %s",va,vb);

i = LocateVex(*G, va);

j = LocateVex(*G, vb);

(*G).arcs[i][j] = (*G).arcs[j][i] = 1;//无向图

}

fclose(pFile);

return;

}

//图G中顶点k的第一个邻接顶点

int FirstVex(MGraph G, int k){

if(k >= 0 && k < G.vexnum){// k合理

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

  if(G.arcs[k][i] != 0) return i ;//顶点相连，则返回顶点位置

}

return -1;

}

//图G中顶点i的第j个邻接顶点的下一个邻接顶点

int NextVex(MGraph G, int i, int j){

if( i >= 0 && i <G.vexnum && j >=0 && j < G.vexnum){//i,j合理

for(int k = j+1; k < G.vexnum; k++)

if(G.arcs[i][k] != 0) return k;

}

return -1;

}

//深度优先遍历 test.exe!mainCRTStartup()  Line 371 C

void DFS(MGraph G, int k){

int i ;

visited[k] = true;

printf("%s ", G.vexs[k]);////访问第K个节点

for( i = FirstVex(G,k); i >= 0; i = NextVex(G, k, i))

if(!visited[i]) DFS(G, i);//对K的尚未访问的邻接顶点i递归调用DFS

}

void DFStrieval(MGraph G)

{

int i;

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

{

  if(visited[i] != true)

DFS(G, i);

}

}

//---------广度遍历-------------

void BFS(MGraph G)

{ 

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

{

int k ;

queue<int> SQ; //辅助队列SQ ,存储顶点的位置

if(!visited[n]){//i未访问

visited[n] = true;

printf("%s ", G.vexs[n]);

SQ.push(n);

while(!SQ.empty()){

k = SQ.front();

SQ.pop();

for(int w = FirstVex(G, k); w >= 0; w = NextVex(G, k ,w))

if(!visited[w]){ //w为k的尚未访问的邻接顶点

visited[w] = true;

printf("%s ", G.vexs[w]);

SQ.push(w);

}

}//while

}

}

}

int main(){

MGraph *G;

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

CreateFAG(G);

memset(visited, 0, sizeof(visited));

printf("深度遍历：\n");

//DFS(*G, 1);//从第二个节点开始

DFStrieval(*G);

memset(visited, 0, sizeof(visited));

printf("\n");

printf("广度遍历：\n");

BFS(*G); //从第一个节点开始

getchar();

getchar();

return 0;

}

1.txt

8 9

V0 V1 V2 V3 V4 V5 V6 V7

V0 V1

V0 V3

V0 V4

V1 V2

V1 V4

V2 V5

V3 V6

V4 V6

V6 V7