图的遍历演示
以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历.
以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集.
*******************************************/
#include<iostream>
# include <string.h>
# include <malloc.h>
# include <conio.h>
using namespace std
int visited[30]
# define MAX_VERTEX_NUM 30
# define OK 1
//typedef int VertexType
typedef int InfoType
typedef struct ArcNode //弧
{
int adjvex
struct ArcNode *nextarc
}ArcNode
typedef struct VNode//表头
{
int data
ArcNode *firstarc
}VNode,AdjList[MAX_VERTEX_NUM]
typedef struct//图
{
AdjList vertices
int vexnum,arcnum
int kind
}ALGraph
void CreateDG(ALGraph &G)
{
int k,i,v1
cout<<endl<<"请输入结点个数: "
cin>>G.vexnum
cout<<"请输入弧的个数: "
cin>>G.arcnum
for(i=1i<=G.vexnumi++)//初使化表头
{
G.vertices[i].data=i
G.vertices[i].firstarc=NULL
}
for(k=1k<=G.vexnumk++) //输入边
{
int v2
cout<<"请输入与结点"<<k<<"相邻的边数:"
cin>>v2
cout<<"请输入与第"<<k<<"个结点相连的结点编号: "
cin>>v1
ArcNode *p
p=(ArcNode*)malloc(sizeof(ArcNode))
if(!p) exit(-1)
p->adjvex=v1
p->nextarc=NULL
G.vertices[k].firstarc=p
for(int i=1i<v2i++)
{
int m
cout<<"请输入与第"<<k<<"个结点相连的结点编号: "
cin>>m
ArcNode *q
q=(ArcNode *)malloc(sizeof(ArcNode))//动态指针
if(!q) exit(-1)
q->adjvex=m //顶点给P
q->nextarc=NULL
p->nextarc=q
p=q
//free(q)
}
//free(p)
}
}
void DFS (ALGraph G,int v )//深度搜索
{
visited[v]=1
cout<<G.vertices[v].data<<" "
ArcNode *x
x=(ArcNode*)malloc(sizeof(ArcNode))
if(!x) exit(-1)
x=G.vertices[v].firstarc
int w
for (xx=x->nextarc)
{ w=x->adjvex
if(visited[w]==0)
DFS(G,w)
}
}
void DFSB (ALGraph G,int v)//深度搜索的边集
{
visited[v]=1
ArcNode *y
y=(ArcNode*)malloc(sizeof(ArcNode))
if(!y) exit(-1)
y=G.vertices[v].firstarc
int u=G.vertices[v].data
int w
for(yy=y->nextarc)
{ w=y->adjvex
if(visited[w]==0)
{
cout<<u<<"--->"<<w<<endl
DFSB(G,w)
}
}
}
typedef struct QNode
{
int data
QNode *next
}QNode,*QueuePtr
typedef struct
{
QueuePtr front
QueuePtr rear
}LinkQueue
void InitQueue (LinkQueue &Q)//建立一个空队列
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))
if(!Q.front) exit(-1)
Q.front->next=NULL
}
void EnQueue (LinkQueue &Q,int e)//进队
{
QNode *p
p=(QNode*)malloc(sizeof(QNode))
if(!p) exit(-1)
p->data=e
p->next=NULL
Q.rear->next=p
Q.rear=p
//free(p)
}
int DeQueue (LinkQueue &Q,int &e)//出队
{
if(Q.front==Q.rear)
return -1
QNode *p
p=(QNode*)malloc(sizeof(QNode))
if(!p) exit(-1)
p=Q.front->next
e=p->data
Q.front->next=p->next
if(Q.rear==p)
Q.rear=Q.front
free(p)
return e
}
int QueueEmpty (LinkQueue Q)//判断队列是否为空
{
if(Q.front==Q.rear)
return 1
return 0
}
void BFS(ALGraph G,int v)//广度搜索
{
int u
LinkQueue Q
InitQueue(Q)
if(visited[v]==0)
{
visited[v]=1
cout<<G.vertices[v].data<<" "
EnQueue(Q,v)
while(QueueEmpty(Q)!=1)
{
DeQueue(Q,u)
ArcNode *z
z=(ArcNode*)malloc(sizeof(ArcNode))
if(!z) exit(-1)
z=G.vertices[u].firstarc
/*
for(int w=z->adjvexw>=0w=z->nextarc->adjvex)
{
if(visited[w]==0)
{
visited[w]=1
cout<<w<<" "
EnQueue(Q,w)
}
}*/
int w
for(zz=z->nextarc)
{ w=z->adjvex
if(visited[w]==0)
{
visited[w]=1
cout<<w<<" "
EnQueue(Q,w)
}
}
}
}
}
void BFSB (ALGraph G,int v)//广度搜索的边集
{
int u
LinkQueue Q
InitQueue(Q)
if(visited[v]==0)
{
visited[v]=1
EnQueue(Q,v)
while(QueueEmpty(Q)!=1)
{
DeQueue(Q,u)
ArcNode *r
r=(ArcNode*)malloc(sizeof(ArcNode))
if(!r) exit(-1)
r=G.vertices[u].firstarc
int w
for(r!=NULLr=r->nextarc)
{ w=r->adjvex
if(visited[w]==0)
{
visited[w]=1
cout<<u<<"--->"<<w<<endl
EnQueue(Q,w)
}
}
}
}
}
int main()
{
int i
ALGraph G
CreateDG(G)
int x
cout<<"请输入结点数:"
cin>>x
cout<<"邻接表为："<<endl
for(int j=1j<=xj++)
{
cout<<G.vertices[j].data<<" "
ArcNode *p
p=(ArcNode*)malloc(sizeof(ArcNode))
if(!p) exit(-1)
p=G.vertices[j].firstarc
while(p)
{
cout<<p->adjvex<<" "
p=p->nextarc
}
cout<<endl
}
cout<<"请输入第一个要访问的结点序号："<<endl
int n
cin>>n
for( i=0i<30i++)
visited[i]=0
cout<<"广度搜索："<<endl
BFS(G,n)
for( i=0i<30i++)
visited[i]=0
cout<<endl
cout<<"边集："<<endl
BFSB(G,n)
for( i=0i<30i++)
visited[i]=0
cout<<"深度搜索："<<endl
DFS(G,n)
for( i=0i<30i++)
visited[i]=0
cout<<endl
cout<<"边集："<<endl
DFSB(G,n)
//system("pause")
return 0
}
前几天上机刚好做了这个,个人感觉很完美,尽管老师说用的是邻接表而不是多重表,太简单,但还不错,界面输入过程比较繁琐,要严格按照提示来输入,是无向图,等级太低,没办法把执行结果粘出来,应该能看懂吧
typedef struct {int vertex[m]int edge[m][m]}gadjmatrix
typedef struct node1{int infoint adjvertexstruct node1 *nextarc}glinklistnode
typedef struct node2{int vertexinfoglinklistnode *firstarc}glinkheadnode
void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ])
{
int i,jglinklistnode *p
for(i=0i<=n-1i++) g2[i].firstarc=0
for(i=0i<=n-1i++) for(j=0j<=n-1j++)
if (g1.edge[i][j]==1)
{
p=(glinklistnode *)malloc(sizeof(glinklistnode))p->adjvertex=j
p->nextarc=g[i].firstarcg[i].firstarc=p
p=(glinklistnode *)malloc(sizeof(glinklistnode))p->adjvertex=i
p->nextarc=g[j].firstarcg[j].firstarc=p
扩展资料：
数据结构算法注意事项。
算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的存储结构实质上是它的逻辑结构在计算机存储器中的实现，为了全面的反映一个数据的逻辑结构，它在存储器中的映象包括两方面内容，即数据元素之间的信息和数据元素之间的关系。
不同数据结构有其相应的若干运算。数据的运算是在数据的逻辑结构上定义的 *** 作算法，如检索、插入、删除、更新和排序等。
数据的运算是数据结构的一个重要方面，讨论任一种数据结构时都离不开对该结构上的数据运算及其实现算法的讨论。
数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）