数据结构(visualc++)用邻接矩阵表示给定无向图并进行深度遍历
《数据结构(visualc++)用邻接矩阵表示给定无向图并进行深度遍历》由会员分享，可在线阅读，更多相关《数据结构(visualc++)用邻接矩阵表示给定无向图并进行深度遍历（27页珍藏版）》请在装配图网上搜索。
1、1.给定无向图，请用邻接矩阵表达法表达该图v4
v5
v3
v2
v1
#include
2、ing u);
int CreateUDN(MGraph &G){
int i,k,j;string v1,v2;
cout<<"请输入顶点数、弧数：";
cin>>G.vexnum>>G.arcnum;
cout<<"输入顶点:";
for(i=0;i 3、arcnum;k++){
cout<<"输入第"< 4、 return i;
}
if (i==G.vexnum){
cout<<"Error u!"< 5、 }
cout< 6、/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,a 7、rcnum;
int kind;
}ALGraph;
void CreateDG(ALGraph &G)
{
int k,i,v1;
cout< 8、for(k=1;k<=G.vexnum;k++) //输入边
{
int v2;
cout<<"请输入与结点"< 9、].firstarc=p;
for(int i=1;i 10、
p->nextarc=q;
p=q;
//free(q);
}
//free(p);
}
}
void DFS (ALGraph G,int v )//深度搜索
{
visited[v]=1;
cout< 11、;
for (;x;x=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(;y;y=y->n 12、extarc)
{ w=y->adjvex;
if(visited[w]==0)
{
cout< 13、.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 (Link 14、Queue &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.fron 15、t==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< 16、)malloc(sizeof(ArcNode));
if(!z) exit(-1);
z=G.vertices[u].firstarc;
/*
for(int w=z->adjvex;w>=0;w=z->nextarc->adjvex)
{
if(visited[w]==0)
{
visited[w]=1;
cout< 17、 w=z->adjvex;
if(visited[w]==0)
{
visited[w]=1;
cout< 18、1)
{
DeQueue(Q,u);
ArcNode *r;
r=(ArcNode*)malloc(sizeof(ArcNode));
if(!r) exit(-1);
r=G.vertices[u].firstarc;
int w;
for(;r!=NULL;r=r->nextarc)
{ w=r->adjvex;
if(visited[w]==0)
{
visited[w]=1;
cout< 19、 }
}
}
}
}
int main()
{
int i;
ALGraph G;
CreateDG(G);
int x;
cout<<"请输入结点数:";
cin>>x;
cout<<"邻接表为："< 20、.firstarc;
while(p)
{
cout< 21、ndl;
BFSB(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<"深度搜索："< 22、e MAX_VEXTEX_NUM 20
#define M 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VEX 23、TEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
typedef struct //构件栈
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack *); //函数申明
int Pop(SqStack *, ElemType *);
void Push(SqStack *,ElemType );
int StackEmpty(SqSt 24、ack *);
void CreatGraph(ALGraph *);
void FindInDegree(ALGraph , int * );
void TopologicalSort(ALGraph );
void InitStack(SqStack *S)//初始化栈
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top=S->base; 25、
S->stacksize=STACK_INIT_SIZE;
}
int Pop(SqStack *S,ElemType *e)//出栈操作
{
if(S->top==S->base)
{return ERROR;}
*e=*--S->top;
//printf("%d\n",e);
// return e;
return 0;
}
void Push(SqStack *S,ElemType e)//进栈操作
{if(S->top-S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S-> 26、stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top = S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}*S->top++=e;
}
int StackEmpty(SqStack *S)//判断栈与否为空
{
if(S->top==S->base)
return OK;
else
return ERROR;}
vo 27、id CreatGraph(ALGraph *G)//构件图
{int m, n, i;
ArcNode *p;
printf("请输入顶点数和边数:");
scanf("%d%d",&G->vexnum,&G->arcnum);
for (i = 1; i <= G->vexnum; i++)
{G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
for (i = 1; i <= G->arcnum; i++) //输入存在边旳点集合
{
printf("\n请输入存在边旳两个顶点旳序号:") 28、;
scanf("%d%d",&n,&m);
while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
{printf("输入旳顶点序号不对旳 请重新输入:");
scanf("%d%d",&n,&m);
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (p == NULL)
{printf("memory allocation failed,goodbey");
exit(1);
}
p->adjvex = m;
p->nextarc = G->vertices[n].fi 29、rstarc;
G->vertices[n].firstarc = p;
}
printf("建立旳邻接表为:\n"); //输出建立好旳邻接表
for(i = 1; i <= G->vexnum; i++)
{
printf("%d",G->vertices[i].data);
for(p = G->vertices[i].firstarc; p; p = p->nextarc)
printf("%3d",p->adjvex);
printf("\n");
}}
void FindInDegree(ALGraph G, int indegree[])/ 30、/求入度操作
{
int i;
for (i = 1; i <= G.vexnum; i++)
{
indegree[i] = 0;
}
for (i = 1; i <= G.vexnum; i++)
{while (G.vertices[i].firstarc)
{indegree[G.vertices[i].firstarc->adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
}
}
}
void TopologicalSort(ALGraph G) //进行拓扑 31、排序
{
int indegree[M];
int i, k, n;
int count = 0;
ArcNode *p;
SqStack S;
FindInDegree(G, indegree);
InitStack(&S);
for (i = 1; i <= G.vexnum; i++)
{
printf("第%d个点旳入度为%d \n", i, indegree[i]);
}
printf("\n");
for ( i = 1; i <= G.vexnum; i++)
{
if (!indegree[i])
Push(&S,i);
}
printf( 32、"进行拓扑排序输出次序为:"); //输出成果
while(!StackEmpty(&S))
{
Pop(&S,&n);
printf("%4d",G.vertices[n].data);
count++;
for (p = G.vertices[n].firstarc; p != NULL; p = p->nextarc)
{
k = p->adjvex;
if (!(--indegree[k]))
{
Push(&S,k);
}
}
}printf("\n");
if (count < G.vexnum)
{
printf("出现错误\n");
}
else
{
printf("排序成功\n");
}
}
int main(void) //主函数
{
ALGraph G;
CreatGraph(&G);
TopologicalSort(G);
system("pause");
return 0;
}
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
