《链式图相关算法实现.doc》由会员分享，可在线阅读，更多相关《链式图相关算法实现.doc（20页珍藏版）》请在金锄头文库上搜索。
1、链式图相关算法C+实现.cpp部分#include#includegraph2.husing namespace std;int main ()graphlist tu1; /切记注意顶点编号从0开始/int ch; cout1:查找指定边权值:endl;cout2:查找指定点的第一个邻接顶点:endl;cout3:查找指定点相对于另一点的邻接顶点:endl;cout4:深度优先遍历endl;cout5:深度优先遍历迭代实现endl;cout6:广度优先遍历endl;cout7:求 Dijakstra 最短路径endl;cout8:插入顶点:endl;cout9:插入边:endl;cout10
2、:删除边:endl;cout请选择:ch;while(ch!=0)switch(ch)case 1:int v1,v2; cout输入两个顶点:v1v2; coutv1和v2权值：tu1.getweight(v1,v2)endl; break;case 2:int v; cout输入顶点:v; coutv的第一个邻接顶点:tu1.getfirstneighbor(v)endl; break;case 3:int v3,v4; cout输入顶点:v3v4; coutv3相对v4的邻接顶点:tu1.getnextneighbor(v3, v4)endl;break;case 4:cout深度优先遍
3、历: ; tu1.DepthFS(); coutendl;break;case 5:cout深度优先遍历迭代实现: ;tu1.DFS(0); coutendl; break;case 6:cout广度优先遍历: ; tu1.BFS(0); coutendl;break;case 7:coutDijakstra 最短路径 ;tu1.Dshortpath(0); break;case 8: int inv; cout插入顶点编号:inv;tu1.insertv(inv);break;case 9:int inv1,inv2,inweight;cout插入边起点，终点，权值:inv1inv2inwe
4、ight; tu1.inserte(inv1,inv2,inweight);break;case 10:int dele1,dele2; cout删除边的顶点:dele1dele2; tu1.dele(dele1,dele2);break;cout还需要什么帮助吗?ch;if(ch=0)cout谢谢使用endl;return 0;.h部分Graph.h#includeusing namespace std;#define maxgraphsize 100#define maxstacksize 100struct edgefriend class graphlist;int veradj;/邻
5、接顶点序号，从0开始编号/int cost;/边的权值/edge * link;/指向下一个边节点的指针/edge()veradj=0;cost=0;link=NULL;edge(int v,int c,edge * l):veradj(v),cost(c),link(l);struct vertexfriend class graphlist;int vername;/顶点名称/edge * adjacent;/边链表的头指针/;class graphlistprivate:vertex * head;int graphsize;public:graphlist() int e,from,t
6、o,weight; head=new vertex maxgraphsize; cout输入邻接表大小:graphsize; for(int i=0;igraphsize;i+) headi.vername=i; headi.adjacent=NULL; ; cout输入边的条数:e; for(i=0;ie;i+) cout输入起点，终点，权值:fromtoweight; edge * p=new edge(); p-veradj=to; p-link=NULL; p-cost=weight; edge * q=headfrom.adjacent; if(q=NULL)headfrom.adj
7、acent=p; else while(q-link!=NULL)q=q-link; q-link=p; graphlist()for(int i=0;ilink;delete p;p=headi.adjacent;delete head;bool graphempty()if(graphsize=0)return true; else return false;bool graphfull()if(graphsize=maxgraphsize)return true; else return false;int vnumber();int enumber();int getweight(in
8、t & v1,int &v2);int * & getneighbor(int & v); int getfirstneighbor(int v);int getnextneighbor(int v1,int v2);int RDFS(int v,int * visited);void insertv(int & v);void inserte(int&v1,int &v2,int weight);void delv(int v);void DepthFS(); void DFS(int v);void BFS(int v);void Dshortpath(int v);void graphl
9、ist:dele(int v1,int v2)/删除一条边/edge * p=headv1.adjacent;edge * t=headv1.adjacent;p=p-link;/if(p=NULL)if(t-veradj=v2)headv1.adjacent=NULL;delete t; else cout无边veradj=v2)headv1.adjacent=t-link;delete t;else while(p-veradj!=v2&p-link!=NULL)t=t-link;p=p-link; if(p-veradj=v2) t-link=p-link; delete p; else
10、 cout边不存在veradj=v2)return p-cost;p=p-link;return 0;int graphlist:getfirstneighbor(int v)if(v=-1)return -1;edge * p=headv.adjacent;if(p!=NULL)return p-veradj;else return -1;int graphlist:getnextneighbor(int v1,int v2) if(v1!=-1&v2!=-1)edge * p=headv1.adjacent;while(p-veradj!=v2&p!=NULL)p=p-link; if(p=NULL)return -1; p=p-link;/指向v2的邻接顶点/ if(p=NULL)return -1;/v2没有邻接顶点/ return p-veradj; return -1;void graphlist:DepthFS()/深度优先遍历/int * visited=new intgraphsize;for(int k=0;kgraphsize;k+)visitedk=0; RDFS(0,vi
