Tässä opetusohjelmassa opit vierekkäisyysluettelon. Lisäksi löydät toimivia esimerkkejä vierekkäisyydestä C, C ++, Java ja Python.
Viereisyysluettelo edustaa kaaviota linkitettyjen luetteloiden ryhmänä.
Taulukon hakemisto edustaa kärkeä ja kukin linkitetyn luettelon elementti edustaa muita huippuja, jotka muodostavat reunan kärjen kanssa.
Adjacency List -esitys
Kaavio ja sen vastaava vierekkäisyysluettelon esitys ovat alla.
Adjacency List -esitys
Viereisyysluettelo on tehokas tallennuksen kannalta, koska meidän on tallennettava vain reunojen arvot. Harvaan kaavioon, jossa on miljoonia pisteitä ja reunoja, tämä voi tarkoittaa paljon säästettyä tilaa.
Adjacency-luettelorakenne
Yksinkertaisin vierekkäisyysluettelo tarvitsee solmudatarakenteen kärkipisteen tallentamiseksi ja kaaviotietorakenteen solmujen järjestämiseksi.
Pysymme lähellä kuvaajan perusmäärittelyä - kokoelmia pisteistä ja reunoista (V, E). Yksinkertaisuuden vuoksi käytämme leimaamatonta kuvaajaa toisin kuin leimattua, ts. Pisteet tunnistetaan niiden indekseillä 0,1,2,3.
Kaivetaan tässä pelaaviin tietorakenteisiin.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Älä anna struct node** adjListshukuttaa sinua.
Sanomme vain, että haluamme tallentaa osoittimen struct node*. Tämä johtuu siitä, että emme tiedä kuinka monta pisteitä kaaviossa on, joten emme voi luoda joukkoa Linkitetyt luettelot kääntöhetkellä.
Adjacency List C ++
Se on sama rakenne, mutta käyttämällä C ++: n sisäänrakennettuja STL-tietorakenteita teemme rakenteesta hieman puhtaamman. Voimme myös abstraktoida toteutuksen yksityiskohdat.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Adjacency List Java
Käytämme Java-kokoelmia linkitettyjen luetteloiden ryhmän tallentamiseen.
class Graph ( private int numVertices; private LinkedList adjLists(); )
LinkedList-tyyppi määräytyy sen mukaan, mitä tietoja haluat tallentaa siihen. Merkittyyn kaavioon voit tallentaa sanakirjan kokonaisluvun sijaan
Adjacency List Python
On syytä, että Python saa niin paljon rakkautta. Yksinkertainen sanasto pisteistä ja sen reunoista on riittävä kuva kaaviosta. Voit tehdä itse kärjestä niin monimutkaisen kuin haluat.
graph = ('A': set(('B', 'C')), 'B': set(('A', 'D', 'E')), 'C': set(('A', 'F')), 'D': set(('B')), 'E': set(('B', 'F')), 'F': set(('C', 'E')))
Python-, Java- ja C / C ++ -esimerkkejä
Python Java C C ++ # Adjascency List representation in Python class AdjNode: def __init__(self, value): self.vertex = value self.next = None class Graph: def __init__(self, num): self.V = num self.graph = (None) * self.V # Add edges def add_edge(self, s, d): node = AdjNode(d) node.next = self.graph(s) self.graph(s) = node node = AdjNode(s) node.next = self.graph(d) self.graph(d) = node # Print the graph def print_agraph(self): for i in range(self.V): print("Vertex " + str(i) + ":", end="") temp = self.graph(i) while temp: print(" -> ()".format(temp.vertex), end="") temp = temp.next print(" ") if __name__ == "__main__": V = 5 # Create graph and edges graph = Graph(V) graph.add_edge(0, 1) graph.add_edge(0, 2) graph.add_edge(0, 3) graph.add_edge(1, 2) graph.print_agraph()
// Adjascency List representation in Java import java.util.*; class Graph ( // Add edge static void addEdge(ArrayList am, int s, int d) ( am.get(s).add(d); am.get(d).add(s); ) public static void main(String() args) ( // Create the graph int V = 5; ArrayList am = new ArrayList (V); for (int i = 0; i < V; i++) am.add(new ArrayList()); // Add edges addEdge(am, 0, 1); addEdge(am, 0, 2); addEdge(am, 0, 3); addEdge(am, 1, 2); printGraph(am); ) // Print the graph static void printGraph(ArrayList am) ( for (int i = 0; i < am.size(); i++) ( System.out.println("Vertex " + i + ":"); for (int j = 0; j " + am.get(i).get(j)); ) System.out.println(); ) ) )
// Adjascency List representation in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int); struct Graph ( int numVertices; struct node** adjLists; ); // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create a graph struct Graph* createAGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); int i; for (i = 0; i adjLists(i) = NULL; return graph; ) // Add edge void addEdge(struct Graph* graph, int s, int d) ( // Add edge from s to d struct node* newNode = createNode(d); newNode->next = graph->adjLists(s); graph->adjLists(s) = newNode; // Add edge from d to s newNode = createNode(s); newNode->next = graph->adjLists(d); graph->adjLists(d) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Vertex %d: ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createAGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 0, 3); addEdge(graph, 1, 2); printGraph(graph); return 0; )
// Adjascency List representation in C++ #include using namespace std; // Add edge void addEdge(vector adj(), int s, int d) ( adj(s).push_back(d); adj(d).push_back(s); ) // Print the graph void printGraph(vector adj(), int V) ( for (int d = 0; d < V; ++d) ( cout << " Vertex " << d << ":"; for (auto x : adj(d)) cout < " << x; printf(""); ) ) int main() ( int V = 5; // Create a graph vector adj(V); // Add edges addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 2); printGraph(adj, V); )
