Undirected graphs anhtt-fit@mail.hut.edu.vn dungct@it-hut.edu.vn Undirected graphs A graph G=(V, E) where V is a set of vertices connected pairwise by edges E. Why study graph algorithms? Interesting and broadly useful abstraction. Challenging branch of computer science and discrete math. Hundreds of graph algorithms known. Thousands of practical applications. Communication, circuits, transportation, scheduling, software systems, internet, games, social network, neural networks, … 1 Graph terminology Some graph-processing problems Path: Is there a path between s to t? Shortest path: What is the shortest path between s and t? Cycle: Is there a cycle in the graph? Euler tour: Is there a cycle that uses each edge exactly once? Hamilton tour: Is there a cycle that uses each vertex exactly once? Connectivity: Is there a way to connect all of the vertices? MST: What is the best way to connect all of the vertices? Biconnectivity: Is there a vertex whose removal disconnects the graph? 2 Graph representation (1) Maintain a list of the edges Not suitable for searching Edge List Structure Edge sequence sequence of edge objects Edge object element origin vertex object destination vertex object reference to position in edge sequence Vertex sequence sequence of vertex objects Vertex object element reference to position in vertex sequence 3 Graph representation (2) Maintain an adjacency matrix. Suitable for random accesses to the edges A graph data structure Use a dynamic array to represent a graph as the following typedef struct { int * matrix; int sizemax; } Graph; Define the following API Graph createGraph(int sizemax); void setEdge(Graph* graph, int v1,