数据结构实验报告--图实验(2)

#include using namespace std; #include\

extern int visited[MaxSize];

template

ALGraph::ALGraph(DataType a[], int n, int e) {

ArcNode * s; int i, j, k;

vertexNum = n; arcNum = e; for(i = 0; i < vertexNum; i++) { adjlist[i].vertex = a[i]; adjlist[i].firstedge = NULL; }

for(k = 0; k < arcNum; k++) { cout << \ cin >> i >> j; s = new ArcNode; s->adjvex = j; s->next = adjlist[i].firstedge; adjlist[i].firstedge = s; } }

template

ALGraph::~ALGraph() {

ArcNode * p = NULL;

for(int i = 0; i < vertexNum; i++) { p = adjlist[i].firstedge; while(p != NULL) { adjlist[i].firstedge = p->next; delete p; p = adjlist[i].firstedge; } } }

template

void ALGraph::DFSTraverse(int v) {

ArcNode * p = NULL; int j; cout << adjlist[v].vertex; visited[v] = 1;

p = adjlist[v].firstedge; while(p != NULL) { j = p->adjvex; if(visited[j] == 0) DFSTraverse(j); p = p->next; } }

template

void ALGraph::BFSTraverse(int v) {

int Q[MaxSize];

int front = -1, rear = -1; ArcNode * p = NULL;

cout << adjlist[v].vertex; visited[v] = 1; Q[++rear] = v; while(front != rear) { v = Q[++front]; p = adjlist[v].firstedge; while(p != NULL) { int j = p->adjvex; if(visited[j] == 0){ cout << adjlist[j].vertex; visited[j] = 1; Q[++rear] = j; } p = p->next; } }

}

ALGraph_main.cpp

#include using namespace std; #include\int visited[MaxSize] = {0};

int main()

{

char ch[] = {'A','B','C','D','E'}; int i;

ALGraph ALG(ch, 5, 6); for(i = 0; i < MaxSize; i++) visited[i] = 0;

cout << \ ALG.DFSTraverse(0); cout << endl;

for(i = 0; i < MaxSize; i++) visited[i] = 0;

cout << \ ALG.BFSTraverse(0); cout << endl; return 0; }

4. 运行与调试

5. 总结与心得

通过该实验，掌握了图的邻接表存储结构