1 #include 
     
        2 #include 
      
         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;    //有向边
       
         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         //插入边
        
          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         //无向图，还要插入边
         
           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
          
            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 <
          
         
        
       
      
     

 

 

 

输出：