# 图的两种构造（邻接矩阵、邻接表）DFS、BFS算法

www.MyException.Cn  网友分享于：2013-11-24  浏览：41次

```#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

#define MAXSIZE 20

bool flag = false;

class MGraph
{
public:
MGraph(int vertex, int side);
~MGraph(){};
void DFSTraverse(int v);
void BFSTraverse(int v);
void PrintMGraph();
private:
int arcd[MAXSIZE][MAXSIZE];
int vertexNum, arcNum;
int visited[MAXSIZE];
};

MGraph::MGraph(int vertex, int arc){
int i, j;
vertexNum = vertex; arcNum = arc;
for(i=0; i<vertexNum; i++){
visited[i] = false;
for(j=0; j<vertexNum; j++)
arcd[i][j] = 0;
}
for(int k=0; k<arcNum; k++){
cin>>i>>j;
arcd[i][j] = 1; arcd[j][i] = 1;
}
}

void MGraph::PrintMGraph(){
for(int i=0; i<vertexNum; i++){
for(int j=0; j<vertexNum; j++){
if(j) printf(" ");
printf("%d", arcd[i][j]);
}
printf("\n");
}
}

void MGraph::DFSTraverse(int v){
if(!flag) {cout<<v; flag = true;}
else cout<<' '<<v;
visited[v] = true;
for(int i=0; i<vertexNum; i++)
if(arcd[v][i] && !visited[i]) DFSTraverse(i);
}

void MGraph::BFSTraverse(int v){
queue<int> q;
cout<<v; visited[v] = true; q.push(v);
while(!q.empty()){
v = q.front();  q.pop();
for(int i=0; i<vertexNum; i++){
if(arcd[v][i] && !visited[i]){
cout<<i; visited[i] = true; q.push(i);
}
}
}
}

int main(int argc, char const *argv[])
{
int vertex, arc;
cin>>vertex>>arc;
MGraph G(vertex, arc);
G.PrintMGraph();
G.DFSTraverse(0);
G.BFSTraverse(0);
return 0;
}
```

```#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

#define MAXSIZE 20

struct ArcNode{
ArcNode *next;
};

struct VertexNode{
ArcNode *firstedge;
};

class ALGraph
{
public:
ALGraph(int vertex, int arc);
~ALGraph(){;}
void DFSTraverse(int v);
void BFSTraverse(int v);
void printALGraph();
private:
int vertexNum, arcNum;
int visited[MAXSIZE];
};

ALGraph::ALGraph(int vertex, int arc){
vertexNum = vertex;		arcNum = arc;
int i, j;
for(int i=0; i<vertexNum; i++){
visited[i] = false;
}
for(int k=0; k<arcNum; k++){
cin>>i>>j;
ArcNode *s = new ArcNode;	s->adjvex = j;
ArcNode *s1 = new ArcNode;	s1->adjvex = i;
}
}

void ALGraph::printALGraph(){
for(int i=0; i<vertexNum; i++){
printf("%d ", i);
while(current){
current = current->next;
}
printf("\n");
}
}

void ALGraph::DFSTraverse(int v){
cout<<v<<' ';	visited[v] = true;
for(ArcNode *p = adjlist[v].firstedge; NULL!=p; p=p->next){
}
}

void ALGraph::BFSTraverse(int v){
queue<int> q;
cout<<v<<' ';	visited[v] = true;	q.push(v);
while(!q.empty()){
v = q.front();	q.pop();
for(ArcNode *p = adjlist[v].firstedge;	NULL!=p; p=p->next){
visited[v] = true;
}
}
}
}

int main(int argc, char const *argv[])
{
int vertex, arc;
cin>>vertex>>arc;
ALGraph g(vertex, arc);
g.printALGraph();
g.DFSTraverse(0);
g.BFSTraverse(0);
return 0;
}```