无向图邻接表实现代码 以及深度优先遍历

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <new>
  4 #include<queue>
  5 using namespace std;
  6 
  7 typedef char VertexType;
  8 typedef int EdgeType;
  9 const int MAXVEX = 100;
 10 const int INFINITY = 65535;
 11 int  visited[MAXVEX];
 12 class EdgeNode
 13 {
 14 public:
 15     int adjvex;
 16     EdgeType weight;
 17     EdgeNode * next;
 18 };
 19 class VertexNode
 20 {
 21 public:
 22     VertexType data;
 23     EdgeNode *firstedge;
 24 };
 25 
 26 class GraphAdjList
 27 {
 28 public:
 29     VertexNode AdjList[MAXVEX];
 30     int numVertexes,numEdges;//图中当前顶点数和边数
 31 };
 32 
 33 void CreateGraph(GraphAdjList &G)
 34 {
 35     int i,j,k;
 36     EdgeNode *e;
 37     cout<<"输入边数和顶点数"<<endl;
 38     cin>>G.numVertexes>>G.numEdges;
 39     for(i= 0;i!=G.numVertexes;++i)
 40     {
 41         cin>>G.AdjList[i].data;//输入顶点信息
 42         G.AdjList[i].firstedge = NULL;//将边表设置为空表
 43     }
 44     for(k = 0;k<G.numEdges;++k)
 45     {
 46         cout<<"输入边(vi,vj)上的顶点序号:\n";
 47         cin>>i>>j;
 48         //先录入数据i指向j
 49         e = new(nothrow) EdgeNode;
 50         e->adjvex=j;
 51         e->next=G.AdjList[i].firstedge;
 52         G.AdjList[i].firstedge =e;
 53         //再反过来j指向i使用同种方式
 54         e = new(nothrow) EdgeNode;
 55         e->adjvex = i;
 56         e->next=G.AdjList[j].firstedge;
 57         G.AdjList[j].firstedge = e;
 58     }
 59 }
 60 
 61 
 62 
 63 
 64 void DFS(GraphAdjList GL,int i)
 65 {
 66     EdgeNode *p;
 67     visited[i] = true;
 68     cout<<GL.AdjList[i].data<<endl;
 69     p = GL.AdjList[i].firstedge;
 70     while(p)
 71     {
 72         if(!visited[p->adjvex])
 73             DFS(GL,p->adjvex);
 74         p=p->next;
 75     }
 76 }
 77 
 78 void DFSTraverse(GraphAdjList GL)
 79 {
 80     int i;
 81     for(i = 0;i<GL.numVertexes;i++)
 82         visited[i]=false;  //初始化所有的顶点都是未访问的状态
 83     for(i = 0;i!=GL.numVertexes;i++)
 84     {
 85         if(!visited[i])  //如果是连通图,只会执行一次.
 86             DFS(GL,i);
 87     }
 88 }
 89 
 90 
 91 void BFSTraverse(GraphAdjList GL)
 92 {
 93     int i ;
 94     EdgeNode *p;
 95     queue<int> Q;
 96     for(i = 0;i!=GL.numVertexes;i++)
 97         visited[i] = false;
 98     for(i = 0;i!=GL.numVertexes;i++)
 99     {
100         if(!visited[i])
101         {
102             visited[i]= true;
103             cout<<GL.AdjList[i].data<<endl;
104             Q.push(i);
105             while(!Q.empty())
106             {
107                 int i = Q.front();
108                 Q.pop();
109                 p=GL.AdjList[i].firstedge;
110                 while(p)
111                 {
112                     if(!visited[p->adjvex])
113                     {
114                         visited[p->adjvex]=true;
115                          cout<<GL.AdjList[p->adjvex].data;
116                          Q.push(p->adjvex);
117                     }
118                     p=p->next;
119                 }
120             }
121         }
122     }
123 }
124 
125 int _tmain(int argc, _TCHAR* argv[])
126 {
127     GraphAdjList g;
128     return 0 ;
129 }