学步园

本博客前面文章已对图有过简单的介绍，本文主要是重点介绍有关图的一些具体操作与应用

阅读本文前，可以先参考本博客 各种基本算法实现小结（四）—— 图及其遍历
  和 
图的一些基本算法

 

无向图——邻接矩阵的深度优先和广度优先算法实现

测试环境：VS2008（C）

#include "stdafx.h"<br /> #include <stdlib.h><br /> #include <malloc.h><br /> #define INFINITY INT_MAX<br /> #define MAX_VEX 20<br /> #define VRType int<br /> #define VertexType char<br /> #define InfoType int<br /> int *visited;<br /> /********************************/<br /> /**** 图的结构定义 ****/<br /> /********************************/<br /> typedef enum<br /> {<br /> DG,<br /> DN,<br /> UDG,<br /> UDN<br /> }GraphKind;<br /> struct _ArcCell<br /> {<br /> VRType adj; /* note weight */<br /> InfoType *info;<br /> };<br /> typedef struct _ArcCell ArcCell, AdjMatrix[MAX_VEX][MAX_VEX];<br /> struct _MGraph<br /> {<br /> VertexType vexs[MAX_VEX];<br /> AdjMatrix arcs;<br /> int vexnum, arcnum;<br /> GraphKind kind;<br /> };<br /> typedef struct _MGraph MGraph;<br /> /********************************/<br /> /**** 栈的结构定义 ****/<br /> /********************************/<br /> struct _node<br /> {<br /> int ivex;<br /> struct _node *next;<br /> };<br /> typedef struct _node node, *pnode;<br /> struct _stack<br /> {<br /> int size;<br /> pnode ptop;<br /> };<br /> typedef struct _stack stack, *pstack;<br /> /********************************/<br /> /**** 堆的结构定义 ****/<br /> /********************************/<br /> struct _queue<br /> {<br /> pnode front;<br /> pnode rear;<br /> };<br /> typedef struct _queue queue, *pqueue;<br /> /********************************/<br /> /**** 栈的实现 ****/<br /> /********************************/<br /> pstack init_stack(int size)<br /> {<br /> pnode pn=NULL;<br /> pstack ps=NULL;<br /> pn=(pnode)malloc(sizeof(node));<br /> ps=(pstack)malloc(sizeof(stack));<br /> pn->ivex=-1;<br /> pn->next=NULL;<br /> ps->size=size;<br /> ps->ptop=pn;<br /> return ps;<br /> }<br /> int empty_stack(pstack ps)<br /> {<br /> if(ps->ptop->next==NULL)<br /> return 1;<br /> else<br /> return 0;<br /> }<br /> void push_stack(pstack ps, int ivex)<br /> {<br /> pnode pn=NULL;<br /> pn=(pnode)malloc(sizeof(node));<br /> pn->ivex=ivex;<br /> pn->next=ps->ptop;<br /> ps->ptop=pn;<br /> }<br /> int pop_stack(pstack ps)<br /> {<br /> int ivex=-1;<br /> pnode pn=NULL;<br /> if(!empty_stack(ps))<br /> {<br /> pn=ps->ptop;<br /> ps->ptop=ps->ptop->next;<br /> ivex=pn->ivex;<br /> free(pn);<br /> }<br /> return ivex;<br /> }<br /> /********************************/<br /> /**** 堆的实现 ****/<br /> /********************************/<br /> queue init_queue()<br /> {<br /> pnode pn=NULL;<br /> queue qu;<br /> pn=(pnode)malloc(sizeof(node));<br /> pn->next;<br /> pn->ivex=-1;<br /> qu.front=qu.rear=pn;<br /> return qu;<br /> }<br /> int empty_queue(queue qu)<br /> {<br /> if(qu.front==qu.rear)<br /> return 1;<br /> else<br /> return 0;<br /> }<br /> void en_queue(queue qu, int ivex)<br /> {<br /> pnode pn=NULL;<br /> pn=(pnode)malloc(sizeof(node));<br /> pn->ivex=ivex;<br /> pn->next=qu.rear->next;<br /> qu.rear=pn;<br /> }<br /> int de_queue(queue qu)<br /> {<br /> int ivex=-1;<br /> pnode pn=NULL;<br /> if(!empty_queue(qu))<br /> {<br /> pn=qu.front;<br /> qu.front=qu.front->next;<br /> ivex=pn->ivex;<br /> free(pn);<br /> }<br /> return ivex;<br /> }<br /> /********************************/<br /> /**** 图的实现 ****/<br /> /********************************/<br /> int LocateVex(MGraph g, char ch)<br /> {<br /> int i;<br /> for(i=1; i<=g.vexnum; i++)<br /> if(ch==g.vexs[i])<br /> return i;<br /> return -1;<br /> }<br /> MGraph Create_UDG()<br /> {<br /> int i, j, w, p1, p2;<br /> char ch1, ch2;<br /> MGraph g;<br /> printf("Enter vexnum arcnum: ");<br /> scanf("%d %d", &g.vexnum, &g.arcnum);<br /> getchar();<br /> for(i=1; i<=g.vexnum; i++)<br /> for(j=1; j<=g.vexnum; j++)<br /> g.arcs[i][j].adj=g.arcs[j][i].adj=INFINITY; /* UDG should define i-j and j-i */<br /> printf("Enter %d vex.../n", g.vexnum);<br /> for(i=1; i<=g.vexnum; i++)<br /> {<br /> printf("vex %d: ", i);<br /> scanf("%c", &g.vexs[i]);<br /> getchar();<br /> }<br /> printf("Enter %d arc.../n", g.arcnum);<br /> for(i=1; i<=g.arcnum; i++)<br /> {<br /> printf("arc %d: ", i);<br /> scanf("%c %c %d", &ch1, &ch2, &w);<br /> getchar();<br /> p1=LocateVex(g, ch1);<br /> p2=LocateVex(g, ch2);<br /> g.arcs[p1][p2].adj=g.arcs[p2][p1].adj=w;<br /> }<br /> return g;<br /> }<br /> int FirstVex(MGraph g, int i)<br /> {<br /> int k;<br /> if(i>=1 && i<=g.vexnum)<br /> for(k=1; k<=g.vexnum; k++)<br /> if(g.arcs[i][k].adj!=INFINITY)<br /> return k;<br /> return -1;<br /> }<br /> int NextVex(MGraph g, int i, int j)<br /> {<br /> int k;<br /> if(i>=1 && i<=g.vexnum && j>=1 && j<=g.vexnum)<br /> for(k=j+1; k<=g.vexnum; k++)<br /> if(g.arcs[i][k].adj!=INFINITY)<br /> return k;<br /> return -1;<br /> }<br /> void DFS(MGraph g, int i)<br /> {<br /> int j;<br /> if(!visited[i])<br /> {<br /> visited[i]=1;<br /> printf("%3c", g.vexs[i]);<br /> for(j=FirstVex(g, i); j>=1; j=NextVex(g, i, j))<br /> if(!visited[j])<br /> DFS(g, j);<br /> }<br /> }<br /> void DFS_Graph(MGraph g)<br /> {<br /> int i;<br /> visited=(int *)malloc((g.vexnum+1)*sizeof(int));<br /> for(i=1; i<=g.vexnum; i++)<br /> visited[i]=0;<br /> for(i=1; i<=g.vexnum; i++)<br /> if(!visited[i])<br /> DFS(g, i);<br /> }<br /> void DFS2_Graph(MGraph g)<br /> {<br /> int i, j, k;<br /> pstack ps=NULL;<br /> ps=init_stack(g.vexnum);<br /> visited=(int *)malloc((g.vexnum+1)*sizeof(int));<br /> for(i=1; i<=g.vexnum; i++)<br /> visited[i]=0;<br /> for(i=1; i<=g.vexnum; i++)<br /> if(!visited[i])<br /> {<br /> visited[i]=1;<br /> printf("%3c", g.vexs[i]);<br /> push_stack(ps, i);<br /> k=i;<br /> while (!empty_stack(ps))<br /> {<br /> for(j=FirstVex(g, k); j>=1; j=NextVex(g, k, j))<br /> {<br /> if(!visited[j])<br /> {<br /> visited[j]=1;<br /> printf("%3c", g.vexs[j]);<br /> push_stack(ps, j); /* push all visited ivex */<br /> k=j; /* newer node */<br /> }<br /> }<br /> k=pop_stack(ps);<br /> }<br /> }<br /> }<br /> void BFS_Graph(MGraph g)<br /> {<br /> int i, j, k;<br /> queue qu;<br /> qu=init_queue();<br /> visited=(int *)malloc((g.vexnum+1)*sizeof(int));<br /> for(i=1; i<=g.vexnum; i++)<br /> visited[i]=0;<br /> for(i=1; i<=g.vexnum; i++)<br /> if(!visited[i])<br /> {<br /> visited[i]=1;<br /> printf("%3c", g.vexs[i]);<br /> en_queue(qu, i);<br /> while (!empty_queue(qu))<br /> {<br /> k=de_queue(qu);<br /> for(j=FirstVex(g, k); j>=1; j=NextVex(g, k, j))<br /> if(!visited[j])<br /> {<br /> visited[j]=1;<br /> printf("%3c", g.vexs[j]);<br /> en_queue(qu, j);<br /> }<br /> }<br /> }<br /> }<br /> /********************************/<br /> /**** 主函数 ****/<br /> /********************************/<br /> int _tmain(int argc, _TCHAR* argv[])<br /> {<br /> MGraph g;<br /> g=Create_UDG();<br /> printf("/nDFS: ");<br /> DFS_Graph(g); /* recursion */<br /> printf("/nDFS: ");<br /> DFS2_Graph(g); /* non recursion */<br /> printf("/nBFS: ");<br /> BFS_Graph(g);<br /> printf("/n");<br /> return 0;<br /> }<br />

运行结果：