图的遍历与最小生成树的实现

{

cout<<

cin>>Vertices[i];

}

for (i=0; i

{

cout<<

输入边的信息（

vi, vj,W

）

：

cin>>vi>>vj>>w;

Edge[vi-1][vj-1]=w;

}

}

3.3.2

创建图的邻接链表

void AdjTWGraph::CreatG(int n,int e)

数据结构与算法课程设计

{

int vi,vj;

DistT w;

numE=e;

numV=n;

cout<<

输入顶 点信息

:

for(int i=0;i

{

}

for(int j=0;j

{

cou t<<

输入边的信息（顶点号

vi

顶点号

vj

边的权值

w

）

：

cin>>vi>>vj>>w;

if(vi<1||vi>numV||vj<1||vj>numV)

cout<<

v1

或

v2< /p>

越

界

出

cout <<

cin>>Vertices[i].data;

错

!

Edge *q=new Edge;

q->dest=vj-1;

q->weight=w;

q->next=NULL; < /p>

if(Vertices[vi-1].adj==NULL)Vertices[vi- 1].adj=q;

else{

Edge *curr=Vertices[vi-1].adj,*pre=NULL;

while(curr!=NULL&&curr->dest

{

}

pre=curr;

curr=curr->next;

数据结构与算法课程设计

}

if(pre==NULL)

{

}

else

{

}

q->next=pre->next;

pre->next=q;

q->next=Vertices[vi-1].adj;

Vertices[vi-1].adj=q;

Edge *p=new Edge;

p->dest=vi-1;

p->weight=w;

p->next=NULL;

if(Vertices[vj -1].adj==NULL)Vertices[vj-1].adj=p;

else{

Edge *curr=Vertices[vj-1].adj,*pre=NULL;

while(curr!=NULL&&curr->dest

{

}

if(pre==NULL)

{

}

else

p->next=Vertices[vj-1].adj;

Vertices[vj-1].adj=p;

pre=curr;

curr=curr->next;

数据结构与算法课程设计

}

}

}

{

}

p->next=pre->next;

pre->next=p;

3.3.3

创建图的十字链表

void Linkedmat::Creat()

{

int m,n,r,c,v,s;

Node *p,*q,*h[10];

cout<<

请输入您要创建的矩阵维数

->

cout<<

行数

:

c in>>m;

cout<<

列数

:< /p>

cin>>n;

s=m>n?m:n;

if(m>n) k=n;

else k=m;

p=new Node;

p->row=m;p->col=n;

hm=p;

h[0]=p;

for(int i=1;i<=s;i++)

{

p=new Node;

p->row=0;p->col=0;

h[i]=p;

数据结构与算法课程设计

}

p->right=p;

p->down=p;

h[i-1]->next=p;

h[s]->next=hm;

cout<

注意

:

cout<<

最大行坐标

:

cout<<

最大列 坐标

:

cout<<

三元组最多个数< /p>

:

cout<<

若输入不在此范围内的数 据将丢失

!

int t;

cout< <

输入非零元素的个数

t=?

cout <<

请输入三元组的格式（以空格分开）

:r

c

v

（回车）

for(int j=0;j

{

}

cout<<

< br>输入三元组

:

cin>>r>>c>>v;

p=new Node;

p->row=r;

p->col=c;

p->val=v;

q=h[r];

while((q->right!=h[r ])&&(q->right->colright;

p->right=q->right;

q->right=p;

q=h[c];

< br>while((q->down!=h[c])&&(q->down->rowdo wn;

p->down=q->down;q->down=p;

数据结构与算法课程设计

}

3.4

图的广度优先遍历

（四号黑体）

3.4.1

图的邻接矩阵的广度优先遍历

void AdjMWGraph::Borad(int v,int visited[])

{

SqQueueq;

cout<

顶点

权值

visited[v]=1;

e(v);

while(!y())

{

v=e();

for(int col=0;col

if(Edge[v][col]>0&&Edge[v] [col]

{

c out<

顶点

权值

visited[col]=1;

e(col);

}

}

}

3.4.2

图的邻接链表的广度优先遍历

< br>

void AdjTWGraph::Borad(int v,int visited[])

{

int vj;

Edge *p;

SqQueueQ;

cout<<

顶点

< br>权值

数据结构与算法课程设计

}

visited[v]=1;

e(v);

while(!y())

{

}

cout<

v=e();

p=Vertices[v].adj;

while(p!=NULL)

{

}

vj=p->dest;

if(visited[vj]==0)

{

}

p=p->next;

cout<<

顶点

权值

visited[vj]=1;

e(vj);

3.5

图的深度优先遍历

（四号黑体）

3.5.1

图的邻接矩阵的深度递归优先遍历

void AdjMWGraph::Depth(int v,int visited[])

{

co ut<<

顶点

权值

visited[v]=1;

for(int col=0;col

{

if(Edge[v][col]==0||Edge[v][col]==MaxW eight)continue;

数据结构与算法课程设计

}

}

if(!visited[col])Depth(col,visited);

3. 5.2

图的邻接矩阵的深度非递归优先遍历

void AdjMWGraph::DepthM()

{

int i,j,k,m;

cout<<

顶点

权值

for(m=0;m

{

i=0;

for(j=0;;)

{

j=j%numV;

if(Edge[i][j]!=0)

{

Edge[i][j]=0;

Edge[j][i]=0;

if(Edge[j][j]==0)

{

for(k=0;k

{

}

if(k==numV)

break;

if(Edge[j][k]==0)

continue;

else

break;

数据结构与算法课程设计

}

}

}

}

}

}

else

cout<<

顶点

权值

i=j;

j++;

if(Edge[i][j]==0)

{

}

if(k==numV)

break;

for(k=0;k

{

if(Edge[i][k]==0)

continue;

else

break;

else

j++;