哈工大数据结构试验3图形结构的运用 - 下载本文

visited[v]=true; Queue[rear++]=v;

cout << G->element[v] << \ while(front!=rear) {

v=Queue[front++];

for(w=0; wn; w++) {

if(!visited[w]&&G->mat[v][w]) {

cout <element[w] << \ visited[w]=true; Queue[rear++]=w; } } } }

void cre2(Adgraph* G) {

int k,i,j;

cin >> G->n >> G->e; for (k=0; kn; k++) {

cin >> G->Ad[k].element; G->Ad[k].firstedge=NULL; }//头结点的初始化 for(k=0; ke; k++) {

cin >> j >> i;

Link* p=new Link; p->v=i;

p->next=G->Ad[j].firstedge;

G->Ad[j].firstedge=p;//在表头插入

p=new Link;//建立无向图,所以还要反过来链接 p->v=j;

p->next=G->Ad[i].firstedge; G->Ad[i].firstedge=p; }

for(i=0; in; i++) {

cout << G->Ad[i].element; Link *m=G->Ad[i].firstedge; while(m!=NULL) {

printf(\ m=m->next; }

printf(\ }//打印邻接表 }

void DFS2(Adgraph* G,int v) {

Link *p;

cout << G->Ad[v].element << \ visited[v]=true;

p=G->Ad[v].firstedge; while(p!=NULL) {

if(!visited[p->v]) DFS2(G,p->v); p=p->next; } }

void DFS2_nonrec(Adgraph* G,int v) {

int STACK[maxlen],top=maxlen; Link *p=NULL;

STACK[--top]=v;//第一个压栈 while(top!=maxlen) {

int w=STACK[top++]; if(!visited[w]) {

cout << G->Ad[w].element << \ visited[w]=true; }

for(p=G->Ad[w].firstedge; p!=NULL; p=p->next) if(!visited[p->v])

STACK[--top]=p->v;//遇到一个没有访问的,压栈,向下搜索 } }

void BFS2(Adgraph* G,int v) {

int Queue[maxlen],front=0,rear=0; struct Link *p=NULL; visited[v]=true; Queue[rear++]=v;

cout << G->Ad[v].element << \ while(front!=rear)

{

v=Queue[front++]; p=G->Ad[v].firstedge;

while(p!=NULL&&!visited[p->v]) {

cout <Ad[p->v].element << \ visited[p->v]=true; Queue[rear++]=p->v; p=p->next; } } }

int main() {

struct Adgraph G2; int i,N;

struct matrix_graph G1;

printf(\邻接矩阵(无向图)\\n2----邻接表(无向图)\\n\ cin >> N; switch(N) {

case 0:

return 0; case 1:

freopen(\ cre1(G1);//建立邻接矩阵 printf(\

for(i=0; i

for(i=0; i

for(i=0; i

for(i=0; i

for(i=0; i

for(i=0; i

freopen(\ cre2(&G2); printf(\

for(i=0; i

for(i=0; i

for(i=0; i

for(i=0; i

for(i=0; i

for(i=0; i

return 0; }