无向图的邻接表创建以及图的深度和…

男娘i 2022-08-25 05:29 170阅读 0赞

\#define MAXSIZE 20

\#define FALSE 0

\#define TRUE 1

\#include

using namespace std;

typedef int Status;

//…………………………………………队列结构……………………

typedef struct qnode

int data;

struct qnode \*next;

\}qnode,\*queueptr;

typedef struct

queueptr front;

queueptr rear;

\}linkqueue;

//…………………………………………邻接表结构…………………………

typedef struct arcnode//弧结点

int adjvex; //该弧指向的顶点的位置

struct arcnode \*nextarc; //弧尾相同的下一条弧

\}arcnode;

typedef struct vnode//邻接链表顶点头接点

char data;//结点信息

arcnode \*firstarc;//指向第一条依附该结点的弧的指针

\}vnode,adjlist;

//…………………………………………图结构…………………………

typedef struct//图的定义

adjlist vertices;

int vexnum,arcnum; //顶点数，弧的条数

\}algraph;

//无向图

//…………………………………………链队列定义……………………

void InitQueue(linkqueue &q)//初始化队列

q.rear = (queueptr)malloc(sizeof(qnode));

if(!q.front) exit(-1); //分配空间失败

q.front = q.rear; q.front->next = NULL;

Status Queue\_empty(linkqueue q)//判断队为空

if(q.front ==  q.rear) return TRUE;

else return FALSE;

Status EnQueue(linkqueue &q,int e)//入队

queueptr p;

p = (queueptr)malloc(sizeof(qnode)); if(!p) exit(-1); //分配空间失败

p->data = e;  p->next = NULL;

q.rear->next = p;

q.rear = p;

return TRUE;

Status DeQueue(linkqueue &q,int &e)//出队

queueptr p;

if( Queue\_empty(q) ) return FALSE;

p = q.front->next;

e = p->data;

q.front->next = p->next;

if(q.rear == p)  q.rear = q.front;

free(p);

return TRUE;

//…………………………………………邻接表定义……………………

int localvex(adjlist G\_L\[\],char v)//返回V的位置

int i = 0;

//printf("da = ‘%c’ v = ‘%c’\\n",G\_L\[i\].data,v);

while(G\_L\[i\].data != v)

//printf("da = %c ,v = %c",G\_L\[i\].data,v);

\++i;

//printf("i = %d\\n",i);

return i;

void Print\_G\_L( algraph G,adjlist \* G\_L)

cout<<"————————图的邻接表——————"<<endl;

for(int i=0; i

printf(" \[%d\] (%c) : ",i,G\_L\[i\].data);

arcnode \* q = G\_L\[i\].firstarc;

while(q ) \{

printf(" %d",q->adjvex);

q = q->nextarc;

printf("\\n");

Status CreteAdj( algraph &G ,adjlist \*G\_L)//用邻接表存储图

cout<<endl<<"请依次输入图的‘顶点’和‘边’的个数(‘空格’隔开)："; cin>>G.vexnum >>G.arcnum;

for(int i=0; i < G.vexnum; i++)

printf("请输入图的第%d个顶点(大写字母A,B,C...)：",i+1);

cin>>G\_L\[i\].data;

//printf("dat = %c",G\_L\[i\].data);

for(int i=0;i

for(int i=0; i < G.arcnum; i++)

char first\_v,second\_v;

printf("请输入图的第%d条边,两顶点间逗号隔开(如‘A,B’不包括引号）:",i+1);

getchar();

scanf("%c,%c",&first\_v,&second\_v);

//printf("fir = %c, sec = %c",first\_v,second\_v);

int loc1 = localvex( G\_L,first\_v );//第1个顶点下标

int loc2 = localvex( G\_L,second\_v );//第2个顶点下标

//printf("loc1 = %d, loc2 = %d\\n",loc1,loc2);

arcnode \* p = (arcnode \* )malloc(sizeof(arcnode)); if(!p) exit(-1); //first->second边

p->adjvex = loc2; p->nextarc = NULL;

arcnode \* q ;

if( G\_L\[loc1\].firstarc == NULL || G\_L\[loc1\].firstarc->adjvex < p->adjvex)

\{ p->nextarc = G\_L\[loc1\].firstarc;  G\_L\[loc1\].firstarc = p; \}//p插在第一个

else\{ //寻找新非零元在航标中的插入位置

for( q = G\_L\[loc1\].firstarc ; (q->nextarc)&&(q->nextarc->adjvex < p->adjvex ); q = q->nextarc ) ; //循环到合适位置，这是个空循环

p->nextarc = q->nextarc; q->nextarc = p; //完成行插入

\}//else

arcnode \* p2 = (arcnode \* )malloc(sizeof(arcnode)); if(!p2) exit(-1);//second->first边

p2->adjvex = loc1; p2->nextarc = NULL;

if( G\_L\[loc2\].firstarc == NULL || G\_L\[loc2\].firstarc->adjvex < p2->adjvex)

\{ p2->nextarc = G\_L\[loc2\].firstarc;  G\_L\[loc2\].firstarc = p2; \}//p插在第一个

else\{ //寻找新非零元在航标中的插入位置

for( q = G\_L\[loc2\].firstarc ; (q->nextarc)&&(q->nextarc->adjvex < p2->adjvex ); q = q->nextarc ) ; //循环到合适位置，这是个空循环

p2->nextarc = q->nextarc; q->nextarc = p2; //完成行插入

\}//else

return TRUE;

void BFS( algraph G,adjlist G\_L\[\] )//广度优先遍历

int i,e; arcnode \* p;

int visit\[MAXSIZE\];//标志元素是否已被访问过，0：未访问， 1：已访问

linkqueue q;

InitQueue(q);

for(i=0; i != G.vexnum;++i) visit\[i\] = FALSE;

cout<<"广度遍历为：";

for(i=0; i!=G.vexnum; ++i)

if( visit\[i\]==FALSE )

visit\[i\] = TRUE ;

cout<< G\_L\[i\].data;

EnQueue(q , i );

while( !Queue\_empty(q) )

DeQueue(q,e);

for( p = G\_L\[e\].firstarc; p; p = p->nextarc)

if( visit\[p->adjvex\]==FALSE ) //未访问

visit\[p->adjvex\] = TRUE;

cout<<G\_L\[p->adjvex\].data;

EnQueue(q,p->adjvex);

\}//for

\} //while

\} //if

cout<<endl;

return;

void DFS(adjlist G\_L\[\],int v,int visit\[\])

\{// 从顶点v出发，深度优先搜索遍历连通图 G

cout<<G\_L\[v\].data;

visit\[v\] = TRUE;

arcnode \* q = G\_L\[v\].firstarc;

while( q )

if( !visit\[q->adjvex\])

DFS(G\_L,q->adjvex,visit);

q = q->nextarc;

\} // DFS

int main()

algraph G;//图

adjlist G\_L\[MAXSIZE\];//图的邻接表

int visit\[MAXSIZE\] =\{ FALSE \}; //该数组用来标志对应下标的元素是否已被访问，初始 FALSE 未访问

CreteAdj( G ,G\_L);

Print\_G\_L(G,G\_L);

BFS(G,G\_L);

cout<<"深度遍历为：";

DFS(G\_L,0,visit); cout<<endl;

return 0;

无向图的邻接表创建以及图的深度和…

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关数据结构——图-有向图和无向图的邻接表基础

相关无向图邻接多重表的创建 - c语言

相关无向图邻接表的创建 - C语言

相关无向图的邻接表创建以及图的深度和…

相关无向图的邻接表广度优先算法

相关无向图的邻接表深度优先算法

相关无向图的邻接表表示法

相关有向图的邻接矩阵、邻接表和逆邻接表

相关无向图的邻接表

相关深度优先搜索邻接表存储结构下的无向图