本文共 3474 字，大约阅读时间需要 11 分钟。

第一轮在学习数据结构时有意避开了图章节，自我暗示面试不会问。躲还是躲不掉的，学还是要学的。“大话数据结构”结合B站视频学习了一遍。自己将图的邻接矩阵表示方法和邻接表的表示方式以及图的遍历写了一遍，加深印象。

#include
   
    #include
    
     using namespace std;struct Graph {
   	vector
     
       vexs;	vector
      
       
        > arcs;	int numberVexs;	int numberArcs;};class Solution {
   private:	int findIndex(vector
        
         & s, char c) { for (int i = 0; i < s.size(); i++) if (s[i] == c) return i; return -1; } vector
         
           used; void DFS(Graph* G, int index) { used[index] = true; cout << G->vexs[index] << " "; for (int i = 0; i < G->numberVexs; i++) { if (G->arcs[index][i] != INT_MAX && !used[i]) DFS(G, i); } }public: void CreateGraph(Graph* G) { cout << "Input numberVexs and numberArcs: "; cin >> G->numberVexs >> G->numberArcs; cout << "Input char for each vexs: "; for (int i = 0; i < G->numberVexs; i++) { char temp; cin >> temp; G->vexs.push_back(temp); } G->arcs = vector
          
           
            >(G->numberVexs, vector
            
             (G->numberVexs, INT_MAX)); cout << "Input start vex and end vex with weight: " << endl; char begin, end; int weight; for (int k = 0; k < G->numberArcs; k++) { cin >> begin >> end >> weight; int i = findIndex(G->vexs, begin); int j = findIndex(G->vexs, end); _ASSERT(i >= 0 && j >= 0); G->arcs[i][j] = weight; G->arcs[j][i] = weight; } } void DFSTraverGraph(Graph* G) { used = vector
             
              (G->numberVexs, false); for (int i = 0; i < G->numberVexs; i++) { if (!used[i]) DFS(G, i); } }};int main() { Solution sol; Graph* G = new Graph(); sol.CreateGraph(G); sol.DFSTraverGraph(G); return 0;}
             
            
           
          
         
        
       
      
     
    
   

无向图邻接表表示：

#include
   
    #include
    
     using namespace std;struct EdgeNode {
   	int adjvex;	int weight;	EdgeNode* next;	EdgeNode(int a, int w) {
   		adjvex = a;		weight = w;		next = nullptr;	}};struct VertexNode {
   	char data;	EdgeNode* firstedge;};struct GraphAdjList {
   	vector
     
       adjList;	int numberVertexs;	int numberEdges;};class Solution {
   private:	int findIndex(GraphAdjList* G, char c) {
   		for (int i = 0; i < G->numberVertexs; i++)			if (c == G->adjList[i].data) return i;		return -1;	}	vector
      
        used;	void DFS(GraphAdjList* G, int index) {
   		used[index] = true;		cout << G->adjList[index].data << " ";		EdgeNode* ptr = G->adjList[index].firstedge;		while (ptr) {
   			if (!used[ptr->adjvex])				DFS(G, ptr->adjvex);			ptr = ptr->next;		}	}public:	void CreatGraph(GraphAdjList* G) {
   		cout << "Input vertexs numbers and edges numbers: ";		cin >> G->numberVertexs >> G->numberEdges;		G->adjList = vector
       
        (G->numberVertexs);		cout << "Input vertexts context: " << endl;		for (int i = 0; i < G->numberVertexs; i++) {
   			cin >> G->adjList[i].data;			G->adjList[i].firstedge = nullptr;		}		cout << "Input edges contex: " << endl;		for (int k = 0; k < G->numberEdges; k++) {
   			char c1, c2;			int weight;			cin >> c1 >> c2 >> weight;			int i = findIndex(G, c1);			int j = findIndex(G, c2);			_ASSERT(i >= 0 && j >= 0);			EdgeNode* temp1 = new EdgeNode(j, weight);			temp1->next = G->adjList[i].firstedge;			G->adjList[i].firstedge = temp1;			EdgeNode* temp2 = new EdgeNode(i, weight);			temp2->next = G->adjList[j].firstedge;			G->adjList[j].firstedge = temp2;		}	}	void DFSTraverGraph(GraphAdjList* G) {
   		used = vector
        
         (G->numberVertexs, false); for (int i = 0; i < G->numberVertexs; i++) { if (!used[i]) DFS(G, i); } }};int main() { Solution sol; GraphAdjList* G = new GraphAdjList(); sol.CreatGraph(G); sol.DFSTraverGraph(G); return 0;}
        
       
      
     
    
   

转载地址：http://styci.baihongyu.com/