无向图的 DFS 和 BFS实现（以邻接表存储的图）

  1 #include <iostream>
  2 #include <queue>
  3 
  4 using namespace std;
  5 
  6 #define MaxVertexNum 10
  7 typedef int Vertex;
  8 typedef int WeightType;
  9 typedef char DataType;
 10 
 11 bool Visited[MaxVertexNum] = { false };
 12 
 13 //边的定义
 14 typedef struct ENode
 15 {
 16     Vertex V1, V2;    //有向边<V1,V2>
 17     WeightType Weight;    //权重
 18 }*Edge;
 19 
 20 //邻接点的定义
 21 typedef struct AdjVNode
 22 {
 23     Vertex AdjV;    //邻接点下标
 24     WeightType Weight;    //边权重
 25     struct AdjVNode *Next;    //指向下一个邻接点的指针
 26 }*PtrToAdjVNode;
 27 
 28 //顶点表头结点的定义
 29 typedef struct VNode
 30 {
 31     /* DataType Data;    //存顶点的数据，很多情况下，顶点无数据，此时Data可以不用出现 */
 32     struct AdjVNode *FirstEdge;    //边表头指针
 33 }AdjList[MaxVertexNum];
 34 
 35 //图结点的定义
 36 typedef struct GNode
 37 {
 38     int Nv;        //顶点数
 39     int Ne;        //边数
 40     AdjList G;  //邻接表表示的图
 41 }*LGraph;
 42 
 43 
 44 LGraph BuildGraph(int vertex_num, int edge_num)
 45 {
 46     LGraph Graph = (LGraph)malloc(sizeof(struct GNode));
 47     Graph->Nv = vertex_num;
 48     Graph->Ne = edge_num;
 49     for (int i = 0; i < Graph->Nv; ++i)
 50         Graph->G[i].FirstEdge = NULL;    //初始化所有表头指针为NULL
 51 
 52     Edge E = (Edge)malloc(sizeof(struct ENode));
 53     for (int i = 0; i < Graph->Ne; ++i)
 54     {
 55         printf("请输入第%d条边的起点和终点：", i+1);
 56         cin >> E->V1 >> E->V2;
 57         E->Weight = 1;
 58 
 59 
 60         //这种插入方法将会使下标大的在前，小的在后，所以遍历的时候下标大的会先遍历
 61         //插入边<V1,V2>
 62         PtrToAdjVNode NewNode1 = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 63         NewNode1->AdjV = E->V2;
 64         NewNode1->Weight = E->Weight;
 65         NewNode1->Next = Graph->G[E->V1].FirstEdge;
 66         Graph->G[E->V1].FirstEdge = NewNode1;
 67 
 68         //无向图，还要插入边<V2,V1>
 69         PtrToAdjVNode NewNode2 = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 70         NewNode2->AdjV = E->V1;
 71         NewNode2->Weight = E->Weight;
 72         NewNode2->Next = Graph->G[E->V2].FirstEdge;
 73         Graph->G[E->V2].FirstEdge = NewNode2;
 74     }
 75 
 76     return Graph;
 77 }
 78 
 79 void Visit(LGraph Graph, Vertex V)
 80 {
 81     cout << V << ' ';
 82 }
 83 
 84 void ClearVisited()
 85 {
 86     for (int i = 0; i < MaxVertexNum; ++i)
 87         Visited[i] = false;
 88 }
 89 
 90 void DFS(LGraph Graph, Vertex V)
 91 {
 92     Visit(Graph, V);
 93     Visited[V] = true;
 94 
 95     for (PtrToAdjVNode p = Graph->G[V].FirstEdge; p != NULL; p = p->Next)
 96     {
 97         if (!Visited[p->AdjV])
 98             DFS(Graph, p->AdjV);
 99     }
100 }
101 
102 void BFS(LGraph Graph, Vertex V)
103 {
104     Visit(Graph, V);
105     Visited[V] = true;
106     queue<Vertex> Q;
107     Q.push(V);
108 
109     while(!Q.empty())
110     { 
111         Vertex W = Q.front();
112         Q.pop();
113         for (PtrToAdjVNode p = Graph->G[W].FirstEdge; p != NULL; p = p->Next)
114         {
115             if (!Visited[p->AdjV])
116             {
117                 Visit(Graph, p->AdjV);
118                 Visited[p->AdjV] = true;
119                 Q.push(p->AdjV);
120             }
121         }
122     }
123 }
124 
125 int main()
126 {
127     int nv, ne;
128     cout << "请输入图的顶点数与边数：";
129     cin >> nv >> ne;
130     LGraph Graph = BuildGraph(nv, ne);
131     cout << endl;
132     cout << "请输入遍历起点：";
133     Vertex V;
134     cin >> V;
135     cout << "DFS: ";
136     DFS(Graph, V);
137     ClearVisited();
138     cout <<endl;
139     cout << "BFS: ";
140     BFS(Graph, V);
141 
142 
143     return 0;
144 }
无向图的 DFS 和 BFS实现 （以邻接表存储的图）

输出：

无向图的 DFS 和 BFS实现（以邻接表存储的图）
