typedef struct t //node of vertex VertexData data //data domain of vertex EdgeNode firstAdj: //head pointer of edge list 1 VertexNode; typedef struct t // adjacency list of graph VertexNode VexList [NumVertices]; // adjacency int n, ei //the number of vertex and edge 3 AdjGraph
typedef struct { //node of vertex VertexData data; //data domain of vertex EdgeNode * firstAdj; //head pointer of edge list } VertexNode; typedef struct { // adjacency list of graph VertexNode VexList [NumVertices]; // adjacency list int n, e; //the number of vertex and edge } AdjGraph;
The construction algorithm of adjacency list void Create Graph(AdjGraph G)t cin >>Gn>>Ge, // input the number of vertex and edge for( int i=0; i<Gn; i++t cin >>G.VexList[].data; //input the vertex"s information G. VexList[i]. firstAdj=NULL for(i=0;i<e; i++ ){∥ input each edge cin > tail > head > weight EdgeNode p=new EdgeNode p->dest= head; p->cost= weight
The construction algorithm of adjacency list void CreateGraph (AdjGraph G) { cin >> G.n >> G.e; //input the number of vertex and edge for ( int i = 0; i < G.n; i++) { cin >> G.VexList[i].data; //input the vertex’’s information G.VexList[i].firstAdj = NULL; } for ( i = 0; i < e; i++) { //input each edge cin >> tail >> head >> weight; EdgeNode * p = new EdgeNode; p->dest = head; p->cost = weight;
//associate the head of the list(number tail) p->link G.VexList[tail]. firstAd G. VexList[tail].firstAdj=p; p= new Edge Node; p->dest= tail; p->cost= weight //associate the head of the list(number head) p->link G. VexList[head]. firstAdji G VexList[head]. firstAdj= p;
//associate the head of the list(number tail) p->link = G.VexList[tail].firstAdj; G.VexList[tail].firstAdj = p; p = new EdgeNode; p->dest = tail; p->cost = weight; //associate the head of the list(number head) p->link = G.VexList[head].firstAdj; G.VexList[head].firstAdj = p; } }
83 Traversing Graph Start from a certain vertex to visit all of the vertex in the graph, make sure each vertex can only be visited one time. This process can be called Traversing graph There may exist some loop in the graph and the vertex may connect to each vertex We may return to the same vertex which once be visited through some edges In order to avoid this case we can set an array visite dl to sign if or not this vertex was once be visited
◼ Start from a certain vertex to visit all of the vertex in the graph, make sure each vertex can only be visited one time. This process can be called Traversing Graph ◼ There may exist some loop in the graph and the vertex may connect to each vertex ，We may return to the same vertex which once be visited through some edges ◼ In order to avoid this case ，we can set an array visited [ ] to sign if or not this vertex was once be visited 。 §3 Traversing Graph
The original status of visited is 0, once a vertex be visited. we set the value of visited i to 1, to avoid the vertex be visited one more times Two travesing method ◆ Depth first search DFS Depth First Search) ◆ Breadth first search BFS Breadth First Search)
◼ The original status of visited [ ] is 0, once a vertex be visited, we set the value of visited [i] to 1, to avoid the vertex be visited one more times。 ◼ Two travesing method ◆ Depth First Search DFS (Depth First Search) ◆ Breadth First Search BFS (Breadth First Search)