Adjacency List

Implementation

• Each vertex has a list with other vertexes that it is connected to and the weights of those connections
• Space: $O(V+E)$
• map<string, vector<pair<string, int>>> graph
  • could also store a map of a map if you won’t have double connections

int no_lines;
string from, to, wt;
map<string, vector<pair<string,int>>> graph;
map<string, vector<pair<string,int>>>::iterator it;
 
cin >> no_lines;
 
for(int i=0;i<no_lines;i++) {
	cin>>from>>to>>wt;
	
	//Creating adjacency list
	graph[from].push_back(make_pair(to,stoi(wt)));
	
	if (graph.find(to)==graph.end()) {
		graph[to] = {};
	}
}
 
//Printing adjacency list
for(it = graph.begin(); it != graph.end(); ++it) {
	cout << it->first << " ->";
	for(int j = 0; j < it->second.size(); j++) {
		cout << " "
			 << it->second[j].first << " "
			 << it->second[j].second << " |";
	    cout <<"\n";
	}
}

Operations

• Connectedness
  • Search the list of the node that you want
  • $O(\text{outdegree}(V))$
• Adjacency
  • Go through the list of the node that you want
  • $O(\text{outdegree}(V))$