图的表示方法主要有邻接矩阵和邻接表。其中邻接表最为常用，因此这里便以邻接表为例介绍一下图的创建及遍历方法。

 

     创建图用到的结构有两种：顶点及弧

struct ArcNode    {        int vertexIndex;        //该弧指向的顶点位置        struct ArcNode* next;    //指向下一个弧        InfoType info;            //该弧的相关信息，如权重等    };    struct Vertex    {        VertexType data;    //顶点信息        ArcNode* firstArc;    //指向第一条依附该节点弧的指针        ColorType color;    //访问情况    };

　　其中ColorType是一个枚举，遍历的时候才会用到。图的创建比较简单，直接看代码很容易理解，这里不再详细说了。 图的深度和广度遍历直接看算法导论中的两张图就明白了 ：

 

//结点颜色代表遍历情况enum ColorType{    WHITE,    //未访问    GRAY,    //正在访问，邻接点还没访问完    BLACK    //访问完毕};

 

代码:

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 using namespace std;  5   6   7 enum GraphType  8 {      9     UNDIR_UNWEIGHT_GRAPH,        //无向无权图 10     UNDIR_WEIGHT_GRAPH,            //无向带权图 11     DIR_UNWEIGHT_GRAPH,            //有向无权图 12     DIR_WEIGHT_GRAPH            //有向带权图     13 }; 14  15 //结点颜色代表遍历情况 16 enum ColorType 17 { 18     WHITE,    //未访问 19     GRAY,    //正在访问，邻接点还没访问完 20     BLACK    //访问完毕 21 }; 22  23 template
        
          24 class Graph 25 { 26 public: 27     Graph(int vertexNum, GraphType type) :m_vertexNum(vertexNum), m_type(type), m_arcNum(0) 28     { 29         for (int i = 0; i < MAX_VERTEX_NUM; ++i) 30         { 31             m_vertices[i].firstArc = nullptr; 32         } 33     } 34  35     void Create() 36     { 37         switch (m_type) 38         { 39         case UNDIR_UNWEIGHT_GRAPH: 40             CreateUndirUnweightGraph(); 41             break; 42         case UNDIR_WEIGHT_GRAPH: 43             CreateUndirWeightGraph(); 44             break; 45         case DIR_UNWEIGHT_GRAPH: 46             CreateDirUnweightGraph(); 47             break; 48         case DIR_WEIGHT_GRAPH: 49             CreateDirWeightGraph(); 50             break; 51         default: 52             break; 53         } 54     } 55  56     //输出图的信息 57     void Display() 58     { 59         for (int i = 0; i < m_vertexNum; ++i) 60         { 61             cout << "第" << i + 1 << "个结点为" << m_vertices[i].data << " 邻接表为："; 62             ArcNode* node = m_vertices[i].firstArc; 63             while (node) 64             { 65                 cout << "->" << m_vertices[node->vertexIndex].data << "(" << node->info << ")"; 66                 node = node->next; 67             } 68             cout << endl; 69         } 70     } 71  72     void BFS() 73     { 74         for (int i = 0; i < m_vertexNum; ++i) 75         { 76             m_vertices[i].color = WHITE; 77         } 78         cout << "图的广度优先遍历为："; 79         BFS(&m_vertices[0]); 80         cout << endl; 81     } 82  83     void DFS() 84     { 85         for (int i = 0; i < m_vertexNum; ++i) 86         { 87             m_vertices[i].color = WHITE; 88         } 89         cout << "图的深度优先遍历为："; 90         DFS(&m_vertices[0]); 91         cout << endl; 92     } 93 private: 94     struct ArcNode 95     { 96         int vertexIndex;        //该弧指向的顶点位置 97         struct ArcNode* next;    //指向下一个弧 98         InfoType info;            //该弧的相关信息，如权重等 99     };100 101     struct Vertex102     {103         VertexType data;    //顶点信息104         ArcNode* firstArc;    //指向第一条依附该节点弧的指针105         ColorType color;    //访问情况106     };107 108     //最大顶点数109     static const int MAX_VERTEX_NUM = 20;110     Vertex m_vertices[MAX_VERTEX_NUM];    //顶点列表111     int m_vertexNum;    //当前顶点数量112     int m_arcNum;        //当前弧数量113     GraphType m_type;    //图类型：有向无权图、有向带权图、无向无权图、无向无权图114 private:115     //初始化顶点列表116     void InitVertices()117     {118         cout << "请输入每个顶点的关键字" << endl;119         VertexType data;120         for (int i = 0; i < m_vertexNum; ++i)121         {122             cin >> data;123             m_vertices[i].data = data;124         }125     }126     //插入一个表结点127     void Insert(int headVertex, int tailVertex, InfoType info)128     {129         //构造一个邻接表结点，即创建一条弧130         ArcNode* newNode = new ArcNode;131         newNode->info = info;132         newNode->next = nullptr;133         newNode->vertexIndex = tailVertex;134 135         //找到邻接表的最后一个节点136         ArcNode* lastNode = m_vertices[headVertex].firstArc;137         if (lastNode == nullptr)138             m_vertices[headVertex].firstArc = newNode;139         else140         {141             while (lastNode->next)142             {143                 lastNode = lastNode->next;144             }145             lastNode->next = newNode;146         }147         ++m_arcNum;148     }149 150     //创建无向无权图151     void CreateUndirUnweightGraph()152     {153         InitVertices();154         cout << "请分别输入每条边的起始结点:" << endl;155         int head, tail;156         while (cin >> head >> tail)157         {158             //无向图head->tail tail->head插入两次159             Insert(head, tail, 0);160             Insert(tail, head, 0);161         }162     }163     //创建无向有权图164     void CreateUndirWeightGraph()165     {166         InitVertices();167         cout << "请分别输入每条边的起始结点和权值:" << endl;168         int head, tail;169         InfoType weight;170         while (cin >> head >> tail >> weight)171         {172             Insert(head, tail, weight);173             Insert(tail, head, weight);174         }175     }176     //创建有向无权图177     void CreateDirUnweightGraph()178     {179         InitVertices();180         cout << "请分别输入每条边的起始结点值:" << endl;181         int head, tail;182         while (cin >> head >> tail)183         {184             Insert(head, tail,0);185         }186     }187     //创建有向带权图 188     void CreateDirWeightGraph()189     {190         InitVertices();191         cout << "请分别输入每条边的起始结点和权值:" << endl;192         int head, tail;193         InfoType weight;194         while (cin >> head >> tail >> weight)195         {196             Insert(head, tail, weight);197         }198     }199 200     void BFS(Vertex* vertex)201     {202         vertex->color = GRAY;203         queue
         
           vertices;204         vertices.push(vertex);205         while (!vertices.empty())206         {207             Vertex* curVertex = vertices.front();208             vertices.pop();209             cout << curVertex->data << "->";210             ArcNode* node = curVertex->firstArc;211             while (node)212             {213                 Vertex* tmpVertex = &m_vertices[node->vertexIndex];214                 if (tmpVertex->color == WHITE)215                 {216                     tmpVertex->color = GRAY;217                     vertices.push(tmpVertex);218                 }219                 node = node->next;220             }221             curVertex->color = BLACK;222         }223     }224 225     void DFS(Vertex* vertex)226     {227         vertex->color = GRAY;228         stack
          
            vertices;229 vertices.push(vertex);230 while (!vertices.empty())231 {232 Vertex* curVertex = vertices.top();233 vertices.pop();234 cout << curVertex->data << "->";235 ArcNode* node = curVertex->firstArc;236 while (node)237 {238 Vertex* tmp = &m_vertices[node->vertexIndex];239 if (tmp->color == WHITE)240 {241 tmp->color = GRAY;242 vertices.push(tmp);243 }244 node = node->next;245 }246 curVertex->color = BLACK;247 } 248 }249 };250 251 int main()252 {253 int vertexNum;254 cout << "请输入要创建的图的结点数：";255 cin >> vertexNum;256 Graph
           
             g(vertexNum,GraphType::UNDIR_UNWEIGHT_GRAPH);257 g.Create();258 g.Display();259 g.BFS();260 g.DFS();261 }
           
          
         
        
       
      
     

运行结果：(创建的树为算法导论BFS说明图片中的树)