图的遍历演示
以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历.
以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集.
*******************************************/
#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
}
前几天上机刚好做了这个,个人感觉很完美,尽管老师说用的是邻接表而不是多重表,太简单,但还不错,界面输入过程比较繁琐,要严格按照提示来输入,是无向图,等级太低,没办法把执行结果粘出来,应该能看懂吧
根据lz要求，最合适的是floyd算法下面就是根据这个算法写的代码，lz可以自己改成函数
D=[0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 1 1 1
1 0 1 0 1 0
0 0 1 1 0 1
0 0 1 0 1 0]
n=length(D)
for k=1:n
for i=1:n
for j=1:n
if 0<D(i,k) &0<D(k,j)
if D(i,j)==0 &i~=j
D(i,j)=D(i,k)+D(k,j)
else
D(i,j)=min(D(i,j),D(i,k)+D(k,j))
end
end
end
end
end
答案就储存在D矩阵当中，这里
D =
0 1 2 1 2 3
1 0 1 2 2 2
2 1 0 1 1 1
1 2 1 0 1 2
2 2 1 1 0 1
3 2 1 2 1 0
算法为O(n3)的，256^3=2^24 大概等于1600万
效率上完全能够忍受。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）