网站开发无形资产,无锡网站制作启,台商网站建设公司黄页,wordpress 企业门户摘自#xff1a;数据结构——无向图创建邻接表以及深度遍历、广度遍历#xff08;C语言版#xff09; 作者#xff1a;正弦定理 发布时间#xff1a;2020-12-22 20:55:12 网址#xff1a;https://blog.csdn.net/chinesekobe/article/details/111409503 数据结构——无向图… 摘自数据结构——无向图创建邻接表以及深度遍历、广度遍历C语言版 作者正弦定理 发布时间2020-12-22 20:55:12 网址https://blog.csdn.net/chinesekobe/article/details/111409503 数据结构——无向图创建邻接表以及深度遍历、广度遍历 一、邻接表概念二、邻接表实现1准备前提——结构体定义2创建边链表3打印边链表4深度优先遍历5广度优先搜索6全部代码 一、邻接表概念 在无向图中顶点存储在顶点表中以一个顶点为标记指向边链表两者组合在一起称为 邻接表 对无向图的每个顶点vi建立一个单链表第i个单链表中的结点表示依附于顶点vi的边对于有向图则是以顶点vi为尾的弧。这个单链表就称为顶点vi的边表对于有向图则称为出边表边表的头指针和顶点的数据信息采用顺序存储称为顶点表邻接表中存在两种结点顶点表结点和边表结点顶点表结点由顶点域data和指向第一条邻接边的指针firstarc构成边表邻接表结点由邻接点域adjvex和指向下一条邻接边的指针域nextarc构成 如图 二、邻接表实现 具体样例 基本每一步都有注释可认真看并理解 1准备前提——结构体定义 #define MAXSIZE 100//深度遍历标记数组
int DfsVist[MAXSIZE];
//广度遍历标记数组
int BfsVist[MAXSIZE];// 边链表
typedef struct EdgeLink{int Local; // 存放该顶点对应边链表中数据 struct EdgeLink *next; // 边链表节点指针 }Edge,*ELINK;// 顶点表
typedef struct VertexLink{int Vertex; // 存放一条边链表对应的顶点 ELINK FirstNode; // 指向该顶点对应边链表的头节点 }Vertex[MAXSIZE],*VLINK;// 存放顶点和边指向顶点表结构体数组
typedef struct MyGraph{int Vnum; // 存放顶点数 int Enum; // 存放边数 Vertex List; // 边链表对应的顶点表中顶点结构体 }MyGraph;12345678910111213141516171819202122232425262728293031323334
2创建边链表
// 创建边链表
void CreateLink(MyGraph *T)
{int i,j;int v1,v2;ELINK p; // 边链表指针 ELINK q;printf(请输入顶点数和边数(空格隔开):\n);scanf(%d%d,(T-Vnum),(T-Enum));// 初始化顶点表结构体数组 for(i0;iT-Vnum;i){printf(请输入第%d个顶点的信息:\n,i1);scanf(%d,(T-List[i].Vertex)); // 存放顶点在顶点表中 T-List[i].FirstNode NULL; // 让每个顶点表第一个指向边链表的指针为NULL }// 打印顶点坐标和顶点表中顶点数据 printf(---------------------------\n); for(i0;iT-Vnum;i){printf(顶点下标为:%d 顶点数据为: %d\n,i,T-List[i].Vertex); }printf(---------------------------\n);// 插入边链表数据 for(i0;iT-Enum;i){// 因为顶点表为顺序表所以要按顶点顺序输入相连边 printf(请输入两个连接顶点下标(空格隔开):\n);scanf(%d%d,v1,v2);getchar(); q (ELINK)malloc(sizeof(Edge)); // 创建边链表节点分配内存 q-Local v2; // 记录与该顶点连接边的顶点坐标q-next NULL; // 让尾巴指向NULL if(!T-List[v1].FirstNode){ // 判断是否为这个顶点第一个指向的数据 T-List[v1].FirstNode q;}else{// 这个顶点已经指向了一条边以这条边为头节点尾插法 p T-List[v1].FirstNode; // 临时存放头节点 while(p-next) // 让节点指针遍历到尾巴上 {p p-next;}p-next q; // 让新插的节点连接到之前边节点的尾巴上 }q (ELINK)malloc(sizeof(Edge)); // 创建边链表节点分配内存 q-Local v1; // 记录与该顶点连接边的顶点坐标q-next NULL; // 让尾巴指向NULL if(!T-List[v2].FirstNode){ // 判断是否为这个顶点第一个指向的数据 T-List[v2].FirstNode q;}else{// 这个顶点已经指向了一条边以这条边为头节点尾插法 p T-List[v2].FirstNode; // 临时存放头节点 while(p-next) // 让节点指针遍历到尾巴上 {p p-next;}p-next q; // 让新插的节点连接到之前边节点的尾巴上 }} }
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
3打印边链表
// 打印邻接表
void PrintLink(MyGraph *S)
{MyGraph *T S;ELINK Q; // 防止边链表指针指到NULL 用临时指针代替遍历打印 int i;printf(打印邻接表结果如下:\n);for(i0;iT-Vnum;i){Q T-List[i].FirstNode; // 接受每个顶点指向对应边链表的头节点指针 printf(%d---,i);while(1){if(Q NULL) // 指针指到尾巴 NULL{putchar(\n);break;}printf(-------%3d,Q-Local);Q Q-next; }}putchar(\n);
}12345678910111213141516171819202122232425262728
4深度优先遍历
//***************** 深度优先遍历算法—邻接表 *****************//
void DFS_Link(MyGraph *T,int n)
{ int i,j;ELINK q; // 指向边链表节点指针 if(n0 || nT-Vnum){printf(输入有误\n);return; }DfsVist[n] 1; // 遍历一个顶点做下标记 1 printf( %d,T-List[n].Vertex);q T-List[n].FirstNode; //q指向下标为i所对顶点 对应的边链表的第一个边结点 while(q!NULL) { if(DfsVist[q-Local]!1){j q-Local;DFS_Link(T,j);} q q-next;}}
// 初始化深度遍历—邻接表
void Init_DFSLINK(MyGraph *Q)
{int i;for(i0;iQ-Vnum;i){DfsVist[i] 0;}for(i0;iQ-Vnum;i){if(!DfsVist[i]){DFS_Link(Q,i); // 此顶点没有被标记开始递归遍历}}putchar(\n); }12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
5广度优先搜索
// 广度遍历
void BFS(MyGraph *S,int t)
{ELINK P; // 指向顶点所对应的边链表中 int i;int v; // 用来接收边链表对应的顶点// 创建一个数组队列 int Queue[MAXSIZE];int front 0; // 队头 int rear 0; // 队尾 printf(%d ,S-List[t].Vertex); // 输出当前遍历边链表的顶点 BfsVist[t] 1; // 将该顶点作标记rear (rear1)%MAXSIZE; // 入队一个让队尾指向后移一位Queue[rear] t; // 将该顶点入队 while(front ! rear) // 若front rear表明这个顶点在边链表上连接的顶点已经遍历完毕 {front (front1)%MAXSIZE; // 出队 v Queue[front]; // 得到此时遍历到顶点坐标 P S-List[v].FirstNode; // 遍历当前顶点指向边链表中连接的其他顶点// 也就是换个顶点的边链表继续遍历查找剩余顶点 while(P!NULL){if(BfsVist[P-Local] 0){ printf(%d ,P-Local1); // 输出连接边顶点 BfsVist[P-Local] 1; // 作标记,表示这个顶点已经搜索过 rear (rear1)%MAXSIZE; // 将该下标入队 Queue[rear] P-Local; // 把遍历到新的边链表对应的顶点坐标入队 }P P-next; // 遍历这个顶点的边链表 } }
} // BFS广度遍历初始化
void Init_BFS(MyGraph *S)
{int i;for(i0;iS-Vnum;i){BfsVist[i] 0; // 初始化标记符 }for(i0;iS-Vnum;i){if(BfsVist[i]0)BFS(S,i);}}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
6全部代码
#includestdio.h
#includestdlib.h#define MAXSIZE 100//深度遍历标记数组
int DfsVist[MAXSIZE];
//广度遍历标记数组
int BfsVist[MAXSIZE];// 边链表
typedef struct EdgeLink{int Local; // 存放该顶点对应边链表中数据 struct EdgeLink *next; // 边链表节点指针 }Edge,*ELINK;// 顶点表
typedef struct VertexLink{int Vertex; // 存放一条边链表对应的顶点 ELINK FirstNode; // 指向该顶点对应边链表的头节点 }Vertex[MAXSIZE],*VLINK;// 存放顶点和边指向顶点表结构体数组
typedef struct MyGraph{int Vnum; // 存放顶点数 int Enum; // 存放边数 Vertex List; // 边链表对应的顶点表中顶点结构体 }MyGraph;// 创建边链表
void CreateLink(MyGraph *T)
{int i,j;int v1,v2;ELINK p; // 边链表指针 ELINK q;printf(请输入顶点数和边数(空格隔开):\n);scanf(%d%d,(T-Vnum),(T-Enum));// 初始化顶点表结构体数组 for(i0;iT-Vnum;i){printf(请输入第%d个顶点的信息:\n,i1);scanf(%d,(T-List[i].Vertex)); // 存放顶点在顶点表中 T-List[i].FirstNode NULL; // 让每个顶点表第一个指向边链表的指针为NULL }// 打印顶点坐标和顶点表中顶点数据 printf(---------------------------\n); for(i0;iT-Vnum;i){printf(顶点下标为:%d 顶点数据为: %d\n,i,T-List[i].Vertex); }printf(---------------------------\n);// 插入边链表数据 for(i0;iT-Enum;i){// 因为顶点表为顺序表所以要按顶点顺序输入相连边 printf(请输入两个连接顶点下标(空格隔开):\n);scanf(%d%d,v1,v2);getchar(); q (ELINK)malloc(sizeof(Edge)); // 创建边链表节点分配内存 q-Local v2; // 记录与该顶点连接边的顶点坐标q-next NULL; // 让尾巴指向NULL if(!T-List[v1].FirstNode){ // 判断是否为这个顶点第一个指向的数据 T-List[v1].FirstNode q;}else{// 这个顶点已经指向了一条边以这条边为头节点尾插法 p T-List[v1].FirstNode; // 临时存放头节点 while(p-next) // 让节点指针遍历到尾巴上 {p p-next;}p-next q; // 让新插的节点连接到之前边节点的尾巴上 }q (ELINK)malloc(sizeof(Edge)); // 创建边链表节点分配内存 q-Local v1; // 记录与该顶点连接边的顶点坐标q-next NULL; // 让尾巴指向NULL if(!T-List[v2].FirstNode){ // 判断是否为这个顶点第一个指向的数据 T-List[v2].FirstNode q;}else{// 这个顶点已经指向了一条边以这条边为头节点尾插法 p T-List[v2].FirstNode; // 临时存放头节点 while(p-next) // 让节点指针遍历到尾巴上 {p p-next;}p-next q; // 让新插的节点连接到之前边节点的尾巴上 }} }// 打印邻接表
void PrintLink(MyGraph *S)
{MyGraph *T S;ELINK Q; // 防止边链表指针指到NULL 用临时指针代替遍历打印 int i;printf(打印邻接表结果如下:\n);for(i0;iT-Vnum;i){Q T-List[i].FirstNode; // 接受每个顶点指向对应边链表的头节点指针 printf(%d---,i);while(1){if(Q NULL){putchar(\n);break;}printf(-------%3d,Q-Local);Q Q-next; //BUG }}putchar(\n);
}//***************** 深度优先遍历算法—邻接表 *****************//
void DFS_Link(MyGraph *T,int n)
{ int i,j;ELINK q; // 指向边链表节点指针 if(n0 || nT-Vnum){printf(输入有误\n);return; }DfsVist[n] 1; // 遍历一个顶点做下标记 1 printf( %d,T-List[n].Vertex);q T-List[n].FirstNode; //q指向下标为i所对顶点 对应的边链表的第一个边结点 while(q!NULL) { if(DfsVist[q-Local]!1){j q-Local;DFS_Link(T,j);} q q-next;}}
// 初始化深度遍历—邻接表
void Init_DFSLINK(MyGraph *Q)
{int i;for(i0;iQ-Vnum;i){DfsVist[i] 0;}for(i0;iQ-Vnum;i){if(!DfsVist[i]){DFS_Link(Q,i); // 此顶点没有被标记开始递归遍历}}putchar(\n); }// 广度遍历
void BFS(MyGraph *S,int t)
{ELINK P; // 指向顶点所对应的边链表中 int i;int v; // 用来接收边链表对应的顶点// 为了不和广度搜素—邻接矩阵冲突// 创建一个数组队列 int Queue[MAXSIZE];int front 0; // 队头 int rear 0; // 队尾 printf(%d ,S-List[t].Vertex); // 输出当前遍历边链表的顶点 BfsVist[t] 1; // 将该顶点作标记rear (rear1)%MAXSIZE; // 入队一个让队尾指向后移一位Queue[rear] t; // 将该顶点入队 while(front ! rear) // 若front rear表明这个顶点在边链表上连接的顶点已经遍历完毕 {front (front1)%MAXSIZE; // 出队 v Queue[front]; // 得到此时遍历到顶点坐标 P S-List[v].FirstNode; // 遍历当前顶点指向边链表中连接的其他顶点// 也就是换个顶点的边链表继续遍历查找剩余顶点 while(P!NULL){if(BfsVist[P-Local] 0){ printf(%d ,P-Local1); // 输出连接边顶点 BfsVist[P-Local] 1; // 作标记,表示这个顶点已经搜索过 rear (rear1)%MAXSIZE; // 将该下标入队 Queue[rear] P-Local; // 把遍历到新的边链表对应的顶点坐标入队 }P P-next; // 遍历这个顶点的边链表 } }
} // BFS广度遍历初始化
void Init_BFS(MyGraph *S)
{int i;for(i0;iS-Vnum;i){BfsVist[i] 0; // 初始化标记符 }for(i0;iS-Vnum;i){if(BfsVist[i]0)BFS(S,i);}} int main()
{MyGraph *S;S (MyGraph *)malloc(sizeof(MyGraph));// 创建边链表 CreateLink(S);// 打印边链表 PrintLink(S);// 深度遍历Init_DFSLINK(S); // 广度遍历 Init_BFS(S);return 0;
} 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287
运行结果
